地形符号变长编码怎样减少总位数：六种地形符号的合并编码（实例18）

若地图中某些地形出现得多，让它们使用较短的二进制码，可能比全部使用同样长的编号更省位。关键是码字之间不能互相当作前缀，否则连续读取时会产生歧义。

先确定规则与输入

本例有六种符号A至F，每次把权重最小的两棵树合并，左支记零、右支记一，父权重等于两者之和。同权按节点建立编号决定顺序，叶子编号零到五，父节点依次增加。

A到F的频次[26, 3, 30, 21, 22, 31]

逐项算出过程

合并节点1和3，权重3与21，得到节点6、权重24；该步使这两个子树内所有符号的码长各增加一。

合并节点4和6，权重22与24，得到节点7、权重46；该步使这两个子树内所有符号的码长各增加一。

合并节点0和2，权重26与30，得到节点8、权重56；该步使这两个子树内所有符号的码长各增加一。

合并节点5和7，权重31与46，得到节点9、权重77；该步使这两个子树内所有符号的码长各增加一。

合并节点8和9，权重56与77，得到节点10、权重133；该步使这两个子树内所有符号的码长各增加一。

码表{'A': '00', 'C': '01', 'F': '10', 'E': '110', 'B': '1110', 'D': '1111'}。符号数据共336位，固定三位编号需要399位，相差63位；这里尚未计入保存码表的开销。

复核时看什么

检查每个符号只对应一个码字，任意码字都不是另一个的前缀。频次乘码长再求和，应等于所有合并步骤新增的权重之和；也可以用全子集划分计算最小可能成本作独立比较。

练习时可以先遮住结果，沿用相同输入独立记录中间状态，再逐项比较。发现不同后先定位最早分歧，确认边界包含方式、编号起点、更新顺序以及是否提前取整。最后结果一致也不表示每个中间步骤都正确，因此保留过程记录有助于看清原因。

适用范围

这里只比较符号数据本身的位数，不包含码表、长度头和字节对齐。短地图可能因这些额外结构而没有空间收益。变长编码也没有隐藏内容的作用，不能当作加密方法。