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

对于压缩阶段，我只是输出代表索引的整数 字典条目，也是由 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)

输出.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。完成!

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

参见:this Steve Blackstock 的解释以获取更多信息。 better page带有实际解码器和编码器实现的流程图，"icafe" Java图像库是GIF编码器和解码器的基础。