重复的地形符号不一定只能逐个存储,也可以引用刚刚解码出的历史字符。一个回溯距离很短、长度更长的引用,会在复制过程中不断使用自己刚追加的字符。
按从左到右的顺序编码,最多回看八个符号、匹配长度最多六。选择最长匹配,同长选距离更近者;长度至少三才写引用,否则写一个原符号。解码引用时逐字符从当前末尾往前指定距离取值并追加。
原始符号串为DBCAADBCAABBCDDBCAADBCAADDDDDD。lit为原符号,ref后依次为回溯距离和复制长度。
条目 | 解码后的完整前缀 ['lit', 'D'] | D ['lit', 'B'] | DB ['lit', 'C'] | DBC ['lit', 'A'] | DBCA ['lit', 'A'] | DBCAA ['ref', 5, 5] | DBCAADBCAA ['lit', 'B'] | DBCAADBCAAB ['lit', 'B'] | DBCAADBCAABB ['lit', 'C'] | DBCAADBCAABBC ['lit', 'D'] | DBCAADBCAABBCD ['lit', 'D'] | DBCAADBCAABBCDD ['lit', 'B'] | DBCAADBCAABBCDDB ['lit', 'C'] | DBCAADBCAABBCDDBC ['lit', 'A'] | DBCAADBCAABBCDDBCA ['lit', 'A'] | DBCAADBCAABBCDDBCAA ['ref', 5, 6] | DBCAADBCAABBCDDBCAADBCAAD ['ref', 1, 5] | DBCAADBCAABBCDDBCAADBCAADDDDDD
表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。
每个引用的距离不能超过当时已经输出的字符数,解码后必须与原串逐字符相同。不能先把源片段一次性切片再追加,因为长度大于距离时需要使用本次复制中刚生成的内容。
这是一份简化的字典压缩规则,没有位级打包、文件头或校验。引用条目数变少不自动等于实际文件字节更小;要判断压缩率,还必须说明每种条目的真实编码成本。
练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。