我正在写一个程序，转让其拥有实现LZW COM pression / DECOM pression。 我用下面的算法是：

I'm writing a program for an assignment which has to implement LZW compression/decompression. I'm using the following algorithms for this:

-com pression

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

-decom pression

-decompression

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

对于COM pression阶段，我只是在整数允许输出重新presenting的索引 字典条目，也开始字典由ASCII字符（0 - 255）。 但是，当我来到DECOM pression阶段，我得到这个错误 例如，如果我COM preSS的文本文件仅包含booop 它会经过这些步骤，以产生一个输出文件：

For the compression stage I'm just outputing ints representing the index for the dictionary entry, also the starting dictionary consists of ascii characters (0 - 255). But when I come to the decompression stage I get this error for example if I compress a text file consisting of only "booop" it will go through these steps to produce an output file:

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

output.txt: 98 111 257 112

然后，当我来到DECOM preSS文件

Then when I come to decompress the file

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

257（OO）尚未尚未加入。任何人都可以看到我要去哪里错在这里，因为我 难住了。是算法错了吗？

257 (oo) hasn't been added yet. Can anyone see where I'm going wrong here cause I'm stumped. Is the algorithm wrong?

推荐答案

您的COM pression部分是正确的，完整的，但DECOM pression一部分是不完整的。你只包括案件时，code是在字典。由于DECOM pression过程总是玉米pression过程后面一个步骤，有当去codeR找到一个code这是不是在字典中的可能性。但因为它是唯一一个落后一步，它可以找出编码过程将增加下一个正确的输出去codeD字符串，然后将其添加到字典中。要继续DECOM pression过程是这样的：

Your compression part is right and complete but the decompression part is not complete. You only include the case when the code is in the dictionary. Since the decompression process is always one step behind the compression process, there is the possibility when the decoder find a code which is not in the dictionary. But since it's only one step behind, it can figure out what the encoding process will add next and correctly output the decoded string, then add it to the dictionary. To continue your decompression process like this:

-decom pression

-decompression

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

然后，当你来到DECOM preSS文件，看到257，你会发现它不存在于字典。但是你知道previous项是O，它的第一个字符是'O'过，把它们放在一起，你会得到面向对象。现在，输出OO并将其添加到字典中。接下来你会得到code 112，并确保你知道它的页。 DONE！

Then when you come to decompress the file and see 257, you find it's not there in the dictionary. But you know the previous entry is 'o' and it's first character is 'o' too, put them together, you get "oo". Now output oo and add it to dictionary. Next you get code 112 and sure you know it's p. DONE!

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

请参阅：这解释史蒂夫·布莱克斯托克了解更多信息。一个更好的页面用流程图的实际德codeR和连接codeR执行上的iCafe咖啡厅的Java图像库GIF EN codeR和德codeR为主。

See: this explanation by Steve Blackstock for more information. A better page with flow chart for the actual decoder and encoder implementation on which the "icafe" Java image library GIF encoder and decoder are based.