LZW减压算法

Question

我正在为一个必须实现LZW压缩/解压缩的任务编写程序.我正在使用以下算法:

-压缩

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

-减压

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

对于压缩阶段,我只是输出表示字典条目索引的int,起始字典也包含ascii字符(0 - 255).但是当我来到解压缩阶段时,我得到了这个错误,例如,如果我压缩一个只包含"booop"的文本文件,它将通过这些步骤生成输出文件:

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

然后,当我来解压缩文件

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

257(oo)尚未添加.任何人都可以看到我在哪里出错了因为我很难过.算法错了吗？

Answer 1

您的压缩部分是正确且完整的,但解压缩部分不完整.您只包括代码在字典中的情况.由于解压缩过程总是压缩过程的一步,因此解码器有可能找到不在字典中的代码.但由于它只落后一步,它可以确定编码过程接下来会添加什么并正确输出解码后的字符串,然后将其添加到字典中.要像这样继续您的解压缩过程:

-减压

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

然后,当您解压缩文件并查看257时,您会发现它不在字典中.但是你知道前面的条目是'o',它的第一个字符也是'o',把它们放在一起,你得到"oo".现在输出oo并将其添加到字典中.接下来你得到代码112并确定你知道它是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

见:这个由史蒂夫·布莱克斯托克说明以获取更多信息.一个更好的网页与在其上的实际的解码器和编码器实现流程图"iCafe咖啡厅"的Java图片库GIF编码器和解码器的基础.