Демпресс Lempel-Ziv-Welch отсутствует.

Question

У меня есть реализация от алгоритма сжатия/декомпрессии LZW и по большей части он отстроен в квадрат. Однако я столкнулся с проблемой с одним из файлов, которые я тестирую. Ниже приводится текст для указанного файлу

#include "bits.h" 

int check_endianness(){ 
    int i = 1; 

область, которую моя реализация застрять на это группа пространств перед int i = 1; Ниже я включил мое сжатие и цикл декомпрессии соответственно вместе с их относительными выходами отладки.

цикла сжатия

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 
} 

выход сжатия

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 

декомпрессионной петли

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

выход декомпрессия

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 

Любая помощь будет оценена.

Answer 1

Вы попали в печально известную проблему KwKwK в алгоритме декомпрессии Lempel Ziv Welch.

Из оригинальной статьи, A Technique for High-Performance Data Compression, Терри А. Уэлч, IEEE Computer, июнь 1984 года, стр 8-19:.

Аномальный случай имеет место каждый раз, когда входная строка символов содержит последовательность KwKwK, где Kw уже отображается в таблице строк компрессора. Компрессор будет разбирать Kw, отправлять CODE (Kw) и добавлять KwK в свою таблицу строк. Затем он проанализирует KwK и отправит только что созданный код (KwK). Декомпрессор при получении CODE (KwK) еще не добавил этот код в свою строковую таблицу, поскольку он еще не знает символ расширения для предшествующей строки.

В статье объясняется, как обойти эту проблему.