重复符号压缩为什么能引用尚未完全展开的片段:规则练习第26例

  • 2026-11-09
  • 1

重复的地形符号不一定只能逐个存储,也可以引用刚刚解码出的历史字符。一个回溯距离很短、长度更长的引用,会在复制过程中不断使用自己刚追加的字符。

按从左到右的顺序编码,最多回看八个符号、匹配长度最多六。选择最长匹配,同长选距离更近者;长度至少三才写引用,否则写一个原符号。解码引用时逐字符从当前末尾往前指定距离取值并追加。

本例输入与约定

原始符号串为CBDCDCBDCDDDBDCBDCDCBDCDAAAAAA。lit为原符号,ref后依次为回溯距离和复制长度。

完整计算记录

条目 | 解码后的完整前缀 ['lit', 'C'] | C ['lit', 'B'] | CB ['lit', 'D'] | CBD ['lit', 'C'] | CBDC ['lit', 'D'] | CBDCD ['ref', 5, 5] | CBDCDCBDCD ['lit', 'D'] | CBDCDCBDCDD ['lit', 'D'] | CBDCDCBDCDDD ['ref', 6, 3] | CBDCDCBDCDDDBDC ['ref', 3, 3] | CBDCDCBDCDDDBDCBDC ['ref', 5, 6] | CBDCDCBDCDDDBDCBDCDCBDCD ['lit', 'A'] | CBDCDCBDCDDDBDCBDCDCBDCDA ['ref', 1, 5] | CBDCDCBDCDDDBDCBDCDCBDCDAAAAAA

表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。

复核方法与适用范围

每个引用的距离不能超过当时已经输出的字符数,解码后必须与原串逐字符相同。不能先把源片段一次性切片再追加,因为长度大于距离时需要使用本次复制中刚生成的内容。

这是一份简化的字典压缩规则,没有位级打包、文件头或校验。引用条目数变少不自动等于实际文件字节更小;要判断压缩率,还必须说明每种条目的真实编码成本。

练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。