Nieistniejący indeks dekompresji Lempela-Ziv-Welcha

Question

Mam implementację z algorytmu kompresji/dekompresji LZW i w większości mam to do kwadratu. Jednak napotkałem problem z jednym z plików, które testuję. Poniżej znajduje się tekst do wspomnianego pliku

#include "bits.h" 

int check_endianness(){ 
    int i = 1; 

obszar, który moja realizacja jest utknięcie na to grupa przestrzeni tuż przed int i = 1; Poniżej mam włączone mój kompresji i dekompresji odpowiednio pętlę wraz z ich względnych wyjść debugowania.

pętli kompresji

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 
} 

wyjście kompresji

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 

pętla dekompresji

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 
    } 
} 

wyjście dekompresja

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 

Każda pomoc będzie mile widziane.

Answer 1

Uderzyłeś w niesławny problem KwKwK w algorytmie dekompresyjnym Lempel Ziv Welch.

Z oryginalnego artykułu, A Technique for High-Performance Data Compression, Terry A. Welch, IEEE Computer, czerwiec 1984, str 8-19.

Nieprawidłowy przypadek występuje wtedy, gdy ciąg znaków wejściowy zawiera sekwencję KwKwK, gdzie Kw już pojawia się w tabeli ciągów sprężarek. Sprężarka zanalizuje Kw, wyśle ​​KOD (Kw) i doda KwK do swojej tabeli łańcuchów. Następnie przeanalizuje KwK i wyśle ​​właśnie wygenerowany CODE (KwK). Dekompresor, po otrzymaniu CODE (KwK), nie dodaje jeszcze tego kodu do swojej tabeli łańcuchów, ponieważ nie zna jeszcze znaku rozszerzenia dla poprzedniego ciągu.

W tym artykule wyjaśniono, jak obejść ten problem.