0

我很难理解 LZW 算法。我正在检查维基百科（http://en.wikipedia.org/w/index.php?title=Lempel-Ziv-Welch&oldid=245292660）上提供的伪代码，解压器代码中有一部分我不明白：

      else if (k == currSizeDict)
          entry = w + w[0];

有人可以向我解释会发生这种情况的情况吗？

4

1 回答 1

2

这个问题在这里解释得很好：https ://www.cs.duke.edu/csed/curious/compression/lzw.html 。基本思想是，由于 LZW 只需要压缩字符串和包含所有字母表元素的字典（而不是包含所有编码模式的字典），因此有必要在解码时动态重建更复杂模式的所有编码。这会导致可能遇到字典中没有的编码。有趣的是，正如上面的链接所指出的，只有当编码的字符串以相同的字符开头和结尾时才会发生这种情况。

于 2015-03-28T18:44:36.097 回答