c - 如何为 LZW 压缩构建树？

Question

谁能告诉我如何在c中为LZW压缩构建一棵树？是不是类似于 struct tree{ short next[255]; }

Answer 1

LZW 的树更像是一本字典。每个条目由一个代码（索引）和一个字符组成。使用所有字符逻辑初始化树，假设 8 位字符，这些使用代码 0x00 到 0xff。这些可能实际上并没有存储在字典中，只是像它们一样被模拟。

假设每个字典条目由 (code | char) 组成，并且您有一个输入字符串“abcd”，然后 dictionary[100] = ('a' | 'b'), dictionary[101] = (100 | 'c') , 字典 [102] = (101 | 'd')。

请注意，解码器必须使用类似堆栈之类的东西来保存字符串，因为它以相反的顺序获取字符。例如，对于代码 102，它将从 [102] 中检索“d”，然后从 [101] 中检索“c”，然后从 [100] 中检索“b”和“a”。当代码 < 0x100 时，指示字符串的结尾（实际上是开头）。

还有一种特殊情况，解码器接收到的代码将是下一个要放入字典的代码，但它还没有。这由字典[下一个代码] =（上一个代码 | 上一个代码的最后一个字符）处理。必须保存每个解码字符串的前一个代码和最后一个字符以处理这种情况。

通常有控制码，比如说有8个，然后压缩器给每个非控制码加8，解压器从每个非控制码减去8。

压缩流可能包含以大端或小端格式存储的代码。对于大端格式，压缩流中的每个字节都进入工作“寄存器”的低位字节，在拾取新字节之前左移。对于小端格式，压缩流中的每个字节都进入工作“寄存器”的高位部分，“寄存器”在拾取新字节后立即移动。

编码器和解码器都需要一些方法来搜索字典以匹配 (code | char)。某种类型的哈希函数可以在这里提供帮助。硬件实现将使用内容可寻址（关联）存储器。

进行网络搜索以查看是否可以找到实际的代码示例。

LZW 是 LZ78 的衍生产品。请注意，LZ77 及其衍生产品更易于实现，并且在 X86 程序文件的情况下，LZ77“移动窗口”压缩算法做得更好。维基链接LZ77 LZ78。