c - 如何构建 LZW 压缩树？

Question

谁能告诉我如何用 c 语言构建 LZW 压缩树？是不是像 结构树{ 短下一个[255]； }

Answer 1

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

假设每个字典条目由 (code | char) 组成，并且您有一个输入字符串“abcd”，则字典[100] = ('a' | 'b'), 字典[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 .