2017-02-09 2 views
7

Ich habe eine Implementierung aus dem LZW Komprimierungs-/Dekomprimierungsalgorithmus und größtenteils zum Quadrat. Ich habe jedoch ein Problem mit einer der Dateien, die ich testen, festgestellt. Im Folgenden ist der Text fürLempel-Ziv-Welch Dekomprimierung nicht existierender Index

Datei sagte
#include "bits.h" 

int check_endianness(){ 
    int i = 1; 

Der Bereich, der meine Implementierung ist rechts von Räumen steckt immer auf die Gruppe vor int i = 1; Im Folgenden werde ich meine Kompression und Dekompression Schleife jeweils zusammen mit ihrer relativen Debug-Ausgaben aufgenommen haben.

Kompressionsschleife

i=0; 
while(i < input_len && ret == LZW_ERR_OK){ 
    //get next byte 
    char curChar = input_char(f_input, &io_flags); 
    i++; 

    //not necessary to check for stream end here since the while condition does that 
    if(io_flags == STREAM_ERR_READ){ 
     ret = LZW_ERR_READ; 
     break; 
    } 

    seqset(&temp, &curChar, 1); 

    //add bytes to temp until a sequence is found that is not in lookup 
    while(i < input_len && dictionary_has_entry(lookup, temp)){ 
     char curChar = input_char(f_input, &io_flags); 
     i++; 

     //check for errors/end of file 
     if(io_flags != STREAM_ERR_OK){ 
      if(io_flags == STREAM_ERR_READ) 
       ret = LZW_ERR_READ; 
      break; 
     } 

     seqadd(&temp, &curChar, 1); 
    } 

    if(temp.length > 1){ 
     #ifdef DEBUG 
     printf("Adding entry %d: ", lookup->next_value); 
     for(int j = 0; j < temp.length; j++) 
      printf("%.4x ", temp.data[j]); 
     printf("\n"); 
     #endif // DEBUG 
     dictionary_set_entry(lookup, temp, DICT_SET_FOREVER); 
     temp.length--; //if temp.length == 1, then the EOF was probably reached 
     i--; //This is important so that the entire file is read 
    } 

    fseek(f_input, -1, SEEK_CUR); 
    output_short(f_output, dictionary_get_entry_byKey(lookup, temp)->value, STREAM_USE_ENDIAN); 
    #ifdef DEBUG 
    printf("Writing code: %d\n", dictionary_get_entry_byKey(lookup, temp)->value); 
    #endif // DEBUG 
} 

Kompressions Ausgang

Adding entry 297: 007b 000d 
Writing code: 123 
Adding entry 298: 000d 000a 0020 
Writing code: 273 
Adding entry 299: 0020 0020 
Writing code: 32 
Adding entry 300: 0020 0020 0020 
Writing code: 299 
Adding entry 301: 0020 0069 
Writing code: 32 
Adding entry 302: 0069 006e 0074 0020 

Dekompression loop

i=0; 
while(i < input_len && ret == LZW_ERR_OK){ 
    short code; 
    entry *e; 
    code = input_short(f_input, &io_flags, STREAM_USE_ENDIAN); 
    if(io_flags == STREAM_ERR_READ){ 
     ret = LZW_ERR_READ; 
     break; 
    } 

    i += 2; 

    //e should never be NULL 
    printf("Reading code: %d\n", code); 
    e = dictionary_get_entry_byValue(lookup, code); 
    assert(e != NULL); 

    seqset(&temp, e->key.data, e->key.length); 

    //requires a slightly different approach to the lookup loop in lzw_encode 
    while(i < input_len && e != NULL){ 
     code = input_short(f_input, &io_flags, STREAM_USE_ENDIAN); 
     //check for errors/end of file 
     if(io_flags != STREAM_ERR_OK){ 
      if(io_flags == STREAM_ERR_READ) 
       ret = LZW_ERR_READ; 
      break; 
     } 
     i += 2; 
     printf("Reading code: %d\n", code); 

     //e should never be NULL 
     e = dictionary_get_entry_byValue(lookup, code); 
     assert(e != NULL); <------------ This is where it is failing 

     //start adding bytes to temp 
     for(size_t j = 0; j < e->key.length; j++){ 
      seqadd(&temp, &e->key.data[j], 1); 
      if(dictionary_get_entry_byKey(lookup, temp) == NULL){ 

       //sequence not found, add it to dictionary 
       printf("Adding entry %d: ", lookup->next_value); 
       dictionary_set_entry(lookup, temp, DICT_SET_FOREVER); 
       for(int k = 0; k < temp.length; k++) 
        printf("%.4x ", temp.data[k]); 
       printf("\n"); 
       e = NULL; //to escape from while 
       break; 
      } 
     } 
    } 

    //if more than one code was read go back by two bytes 
    if(e == NULL){ 
     i -= 2; 
     fseek(f_input, -2, SEEK_CUR); 
    } 

    //only write up to the characters that made a known sequence 
    temp.length--; 
    for(size_t j = 0; j < temp.length; j++){ 
     output_char(f_output, temp.data[j]); 
     #ifdef DEBUG 
     //printf("%c", temp.data[j]); 
     #endif // DEBUG 
    } 
} 

Dekompression Ausgabe

Reading code: 123 
Reading code: 273 
Adding entry 297: 007b 000d 
Reading code: 273 
Reading code: 32 
Adding entry 298: 000d 000a 0020 
Reading code: 32 
Reading code: 299 
299, 299 <----error output from dictionary (code asked > next value) 
Assertion failed: e != NULL, file lzw.c, line 212 

Jede Hilfe sehr geschätzt werden würde.

Antwort

8

Sie treffen das berüchtigte KwKwK Problem im Lempel Ziv Welch Dekompressionsalgorithmus.

Vom Original-Artikel, A Technique for High-Performance Data Compression, Terry A. Welch, IEEE Computer, Juni 1984, S. 8-19.

Die anomalen Fall tritt ein, wenn eine eingegebene Zeichenkette die Sequenz KwKwK enthält, wobei Kw erscheint bereits in der Kompressor-String-Tabelle. Der Kompressor wird Kw auslesen, CODE (Kw) senden und KwK zu seiner String-Tabelle hinzufügen. Als nächstes wird es KwK analysieren und den gerade generierten CODE (KwK) senden. Der Dekomprimierer, der CODE (KwK) empfangen hat, hat diesen Code noch nicht zu seiner String-Tabelle hinzugefügt, weil er noch kein Erweiterungszeichen für die vorherige Zeichenfolge kennt.

Der Artikel erläutert, wie Sie dieses Problem umgehen können.

+0

Danke! Das war eine ziemlich böse Überraschung, als ich es entdeckte. Wenn also ein unbekannter Code gefunden wird, füge ich einfach das erste Zeichen des vorherigen Codes hinzu. – Marcos

+0

Ich erinnere mich nicht an die Details des Updates, aber es ist in der Tat so etwas. – chqrlie

Verwandte Themen