LZW减压算法

我正在为一个必须实现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)尚未添加.任何人都可以看到我在哪里出错了因为我
难倒.算法错了吗?

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

-减压

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

有关更多信息,请参阅:Steve Blackstock的this解释. better page,其中包含“icafe” Java图像库GIF编码器和解码器所基于的实际解码器和编码器实现的流程图.

相关文章
相关标签/搜索