Lemp-Ziv-Welch解凍不在インデックス

Question

私はLZW圧縮/解凍アルゴリズムを実装していません。しかし、私がテストしているファイルの1つに問題が発生しました。以下は、私はそれらの相対的なデバッグ出力とともに、それぞれの私の圧縮と解凍のループが含まれている以下のファイル

#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

Lempel Ziv Welch圧縮解除アルゴリズムで、悪名高いKwKwK問題が発生しました。元の記事、A Technique for High-Performance Data Compression、テリーA.ウェルチ、IEEEコンピュータ、1984年6月、頁から

8-19：。

入力された文字列は、シーケンスKwKwK、キロワットが含まれていたときに異常なケースが発生しました既にコンプレッサー文字列テーブルに表示されます。コンプレッサーはKwを解析し、CODE（Kw）を送信し、KwKをその文字列テーブルに追加します。次に、KwKを解析し、ちょうど生成されたCODE（KwK）を送信します。デコンプレッサーは、CODE（KwK）を受け取っても、以前の文字列の拡張文字をまだ認識していないため、そのコードを文字列テーブルに追加していません。

この記事では、この問題を回避する方法について説明します。