LZW algorithme de décompression

Je suis en train d'écrire un programme pour une mission qui a pour mettre en œuvre la compression LZW/décompression.
Je suis en utilisant les algorithmes suivants pour cela:

-compression

w = NIL;
   while ( read a character k )
       {
         if wk exists in the dictionary
         w = wk;
         else
         add wk to the dictionary;
         output the code for w;
         w = k;
       }

-décompression

read a character k;
   output k;
   w = k;
   while ( read a character k )    
  /* k could be a character or a code. */
        {
         entry = dictionary entry for k;
         output entry;
         add w + entry[0] to dictionary;
         w = entry;
        }

Pour l'étape de compression, je suis juste outputing ints représentant l'index de la
entrée de dictionnaire, à partir du dictionnaire se compose de caractères ascii (0 - 255).
Mais quand je viens à l'étape de décompression, j'obtiens cette erreur
par exemple, si je compresser un fichier texte composé de seulement "booop"
il faudra passer par ces étapes pour produire un fichier de sortie:

w       k       Dictionary          Output

-       b       -                   -
b       o       bo (256)            98 (b)
o       o       oo (257)            111 (o)
o       o       -                   -
oo      p       oop (258)           257 (oo)
p       -       -                   112 (p)

output.txt:
98
111
257
112

Puis quand je viens pour décompresser le fichier

w       k          entry        output       Dictionary
        98 (b)                  b   
b       111 (o)    o            o             bo (256)
o       257 (error)

257 (oo) n'a pas encore été ajouté. Quelqu'un peut-il voir où je vais mal ici parce que je suis
perplexe. L'algorithme de mal?

Pouvez-vous nous montrer le code réel, parce que pseudocode est toujours ambigu.
Le problème est-il résolu?
Oui j'ai mis en œuvre les modifications apportées à l'algorithme et il fonctionne.

OriginalL'auteur clintbeastwood | 2012-05-04

7

De compression est la partie qui est juste et complète, mais la procédure de décompression de la partie n'est pas complète. Vous devez inclure seulement le cas lorsque le code est dans le dictionnaire. Depuis le processus de décompression est toujours un temps de retard sur le processus de compression, il est possible lorsque le décodeur de trouver un code qui n'est pas dans le dictionnaire. Mais puisque c'est seulement un pas en arrière, il peut comprendre ce que le processus d'encodage va ajouter de la prochaine correctement et de sortie décodé chaîne, puis l'ajouter au dictionnaire. Pour continuer votre processus de décompression comme ceci:

-décompression
```
read a character k;
   output k;
   w = k;
   while ( read a character k )    
  /* k could be a character or a code. */
        {
         if k exists in the dictionary
         entry = dictionary entry for k;
         output entry;
         add w + entry[0] to dictionary;
         w = entry;
         else
         output entry = w + firstCharacterOf(w);
         add entry to dictionary;
         w = entry;
        }
```
Puis, quand vous venez de décompresser le fichier et de voir 257, vous trouvez qu'il n'y est pas dans le dictionnaire. Mais vous savez que l'entrée précédente est " o "et c'est le premier caractère est un" o " trop, de les mettre ensemble, vous obtenez "oo". Maintenant la sortie oo et l'ajouter au dictionnaire. Ensuite, vous obtenez le code 112 et assurez-vous que vous savez que c'est p. FAIT!
```
w       k          entry        output       Dictionary
        98 (b)                  b   
b       111 (o)    o            o             bo (256)
o       257 (oo)                oo            oo(257)
oo      112(p)                  p
```
Voir: cette explication par Steve Blackstock pour plus d'informations. Un meilleure page avec le diagramme de flux pour le décodeur et encodeur de mise en œuvre sur laquelle le "icafe" Java bibliothèque d'images GIF encodeur et le décodeur sont fondées.

Fonctionne comme un charme grâce.

OriginalL'auteur dragon66
1

De http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch etes-vous tomber dans ce cas?

Ce qui se passe si le décodeur reçoit un code Z, ce qui n'est pas encore dans son dictionnaire? Depuis le décodeur est toujours juste un code-behind de l'encodeur, Z peut être dans le codeur du dictionnaire uniquement si le codeur qui vient d'être généré, en émettant le code précédent X pour χ. Ainsi Z les codes de certains ω qui est χ + ?, et le décodeur peut déterminer le caractère inconnu comme suit:
```
1) The decoder sees X and then Z.
2) It knows X codes the sequence χ and Z codes some unknown sequence ω.
3) It knows the encoder just added Z to code χ + some unknown character,
4) and it knows that the unknown character is the first letter z of ω.
5) But the first letter of ω (= χ + ?) must then also be the first letter of χ.
6) So ω must be χ + x, where x is the first letter of χ.
7) So the decoder figures out what Z codes even though it's not in the table,
8) and upon receiving Z, the decoder decodes it as χ + x, and adds χ + x to the table as the value of Z.
```
Cette situation se produit lorsque le codeur rencontres d'entrée de la forme du ccsca, où c est un caractère unique, S est une chaîne de caractères et cS est déjà dans le dictionnaire, mais le scc n'est pas. Le codeur émet le code pour cS, en mettant un nouveau code pour le scc dans le dictionnaire. Ensuite, il voit le scc à l'entrée (à partir de la deuxième c du ccsca) et émet le nouveau code qu'il vient d'être insérée. L'argument ci-dessus montre qu'à chaque fois que le décodeur reçoit un code pas dans son dictionnaire, la situation doit ressembler à ceci.

Bien que d'entrée de la forme du ccsca peut sembler improbable, ce modèle est assez fréquent lorsque le flux d'entrée est marquée par d'importantes répétition. En particulier, les longues chaînes d'un seul caractère (qui sont communes dans les types d'images LZW est souvent utilisé pour coder à plusieurs reprises pour générer des motifs de ce genre.

Pour ce cas précis, la wikipédia chose a sa place, vous avez X+? où X est (o), Z est inconnu pour l'instant si la première lettre est X qui donne à (oo) ajouter (oo) à la table 257. Je vais juste sur ce que j'ai lu sur wikipedia, laissez-nous savoir comment cela s'avère si ce n'est pas la solution.

Merci, j'ai une meilleure compréhension de la façon dont il fonctionne réellement maintenant.

OriginalL'auteur old_timer

Vous devez vous connecter pour publier un commentaire.