Lempel-Ziv-Welch décompression indice inexistant

Question

J'ai une mise en œuvre de l'algorithme de compression/décompression LZW et pour la plupart l'avoir au carré. Cependant, j'ai rencontré un problème avec l'un des fichiers que je suis en train de tester. Ci-dessous le texte pour ledit fichier

#include "bits.h" 

int check_endianness(){ 
    int i = 1; 

La zone que ma mise en œuvre est coincé sur le groupe d'espaces à droite avant int i = 1; Ci-dessous j'ai inclus ma compression et la boucle de décompression respectivement avec leurs sorties de débogage relatives.

boucle de compression

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 
} 

sortie de compression

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 

boucle de décompression

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

sortie de décompression

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 

Toute aide serait grandement appréciée.

Answer 1

Vous rencontrez le fameux problème KwKwK dans l'algorithme de décompression Lempel Ziv Welch.

De l'article original, A Technique for High-Performance Data Compression, Terry R. Welch, IEEE Computer, Juin 1984, pp 8-19.

Le cas anormal se produit chaque fois qu'une chaîne de caractères d'entrée contient la séquence KwKwK, où Kw apparaît déjà dans la table de chaînes du compresseur. Le compresseur analysera Kw, enverra CODE (Kw) et ajoutera KwK à sa table de chaînes. Ensuite, il analysera KwK et enverra le CODE généré juste (KwK). Le décompresseur, à la réception de CODE (KwK), n'a pas encore ajouté ce code à sa table de chaînes car il ne connaît pas encore de caractère d'extension pour la chaîne précédente.

L'article explique comment contourner ce problème.