LZ77、LZ78 与 LZW：字典从哪里来，最长匹配怎么找
内容提要
本文比较了LZ77与LZ78两种压缩算法：LZ77以滑动窗口为字典，LZ78增量构建短语表。实测表明，二叉树查找器每位置仅需访问22个候选即可获得完整匹配列表，而哈希链需884个；最优解析比贪心解析小12.7%。LZW的表满策略影响大于算法本身。渐近最优在真实文件上收敛极慢，2²⁴比特后LZ78仍比熵高9.7%。
延伸解读
匹配查找器的选择：二叉树与哈希链的权衡
二叉树查找器每位置仅需22个候选即可获得完整匹配列表，而哈希链需884个候选才能达到98%的覆盖率。但二叉树每个位置都必须遍历树，哈希链则允许在匹配内部跳过查询。在贪心解析下，哈希链每字节仅访问3.06个候选，输出仅比二叉树大1.1%。因此，二叉树更适合需要完整匹配列表的最优解析，而哈希链在快速解析中更高效。
最优解析的收益与代价
在Canterbury语料上，最优解析比贪心解析输出小12.7%，但需要为每个位置计算完整匹配列表，计算成本更高。最优解析通过动态规划精确计算比特代价，能利用距离更近的匹配节省比特。然而，动态Huffman编码下码长与解析相互依赖，最优性不再保证，实践中常用迭代方法如zopfli。
LZW表满策略的显著影响
LZW的表满策略对压缩率影响巨大：12位冻结比16位按压缩比清表大27%。在kennedy.xls上，12位频繁清表几乎与不限表长的LZ78相当，而16位冻结则差很多。compress的按压缩比清表在多数文件上表现最佳，但在某些文件上不如固定间隔清表。表满策略的选择需根据数据特性权衡。
渐近最优在有限数据上的局限
尽管理论上LZ78和LZ77都是渐近最优的，但在2^24比特的合成数据上，LZ78的码长仍比熵高9.7%（p=0.5）和14.7%（p=0.1）。冗余随长度下降缓慢，要将冗余降至1%需要极长的数据，实际文件远达不到。因此，渐近最优性对现实压缩算法的指导意义有限，工程中更关注有限长度下的实际性能。
Q&A
LZ77和LZ78的字典有什么本质区别？
LZ77的字典是滑动窗口内最近W个字节的所有子串，窗口滑过旧串自然消失；LZ78的字典是解析过程中增量构建的短语表，每个新短语等于某个已有短语加一个符号，表满前什么都不忘。
为什么LZ77编码器找最长匹配时，二叉树比哈希链高效那么多？
二叉树按串排序，搜索路径上的节点天然按公共前缀长度和位置新旧排列，每个长度第一次出现就是最近位置，因此平均只需访问22个候选就能得到完整匹配列表；哈希链按时间排列，候选与公共前缀无关，要达到98%的准确率需访问884个候选。
LZW的表满策略对压缩效果影响有多大？
影响比算法本身更大。在Canterbury语料上，12位冻结比16位按压缩比清表大27%；kennedy.xls上12位冻结418,865字节，12位清表269,896字节，几乎等于不限表长的LZ78。
LZ77的最优解析比贪心解析能省多少？
在Canterbury语料上，固定码DEFLATE下，最优解析输出860,197字节，比贪心解析的984,806字节小12.7%。
LZ78和LZW在真实文件上收敛到熵的速度有多慢？
在2^24个独立同分布比特上，LZ78的码长仍比熵高9.7%（p=0.5）和14.7%（p=0.1），LZW略差。要把冗余降到1%，log2 n需200以上，真实文件远达不到。
LZ77和LZ78在工程上分别有哪些代表格式？
LZ77一支包括LZSS、DEFLATE、LZ4、Snappy、LZMA、zstd；LZ78一支包括LZW、compress、GIF。
