若地图中某些地形出现得多,让它们使用较短的二进制码,可能比全部使用同样长的编号更省位。关键是码字之间不能互相当作前缀,否则连续读取时会产生歧义。
先确定规则与输入
本例有六种符号A至F,每次把权重最小的两棵树合并,左支记零、右支记一,父权重等于两者之和。同权按节点建立编号决定顺序,叶子编号零到五,父节点依次增加。
A到F的频次[2, 26, 22, 5, 2, 33]
逐项算出过程
合并节点0和4,权重2与2,得到节点6、权重4;该步使这两个子树内所有符号的码长各增加一。
合并节点6和3,权重4与5,得到节点7、权重9;该步使这两个子树内所有符号的码长各增加一。
合并节点7和2,权重9与22,得到节点8、权重31;该步使这两个子树内所有符号的码长各增加一。
合并节点1和8,权重26与31,得到节点9、权重57;该步使这两个子树内所有符号的码长各增加一。
合并节点5和9,权重33与57,得到节点10、权重90;该步使这两个子树内所有符号的码长各增加一。
码表{'F': '0', 'B': '10', 'A': '11000', 'E': '11001', 'D': '1101', 'C': '111'}。符号数据共191位,固定三位编号需要270位,相差79位;这里尚未计入保存码表的开销。
复核时看什么
检查每个符号只对应一个码字,任意码字都不是另一个的前缀。频次乘码长再求和,应等于所有合并步骤新增的权重之和;也可以用全子集划分计算最小可能成本作独立比较。
练习时可以先遮住结果,沿用相同输入独立记录中间状态,再逐项比较。发现不同后先定位最早分歧,确认边界包含方式、编号起点、更新顺序以及是否提前取整。最后结果一致也不表示每个中间步骤都正确,因此保留过程记录有助于看清原因。
适用范围
这里只比较符号数据本身的位数,不包含码表、长度头和字节对齐。短地图可能因这些额外结构而没有空间收益。变长编码也没有隐藏内容的作用,不能当作加密方法。
