# 霍夫曼编码怎样让常见符号更短

By DUSK

Topic: Physics & Chemistry

[Open the interactive Jig](https://ask.jig.com/j/xrwgV0Kh3Z4e)

## Guide

### 1. 常见的符号，配短的码

电脑用0和1保存文字。这里有四个符号A、B、C、D，在一段消息里分别出现5、7、10、15次。霍夫曼编码的想法是：出现越多的符号，码字（代表它的一串0和1）越短。

示意模型：积木大小按出现次数归一化，并非真实尺寸。拖动可旋转视角，滚轮或双指可缩放。

### 2. 每次合并最小的两个

把出现次数最小的两块挂到一个新节点下，新节点记下两者之和。发光的就是下一对。按“下一次合并”：5和7合成12，再合并10和12，最后合并15和22。

三次合并后，按钮变成“重置树”，可以从头再来。若两个次数相同（平局），任选其一都可以。

### 3. 左边记0，右边记1

合并到只剩根节点37，树就长成了。从根往下走，左分支记0，右分支记1。走到某块积木的一路0和1，就是它的码字：D=0，C=10，A=110，B=111。

把某处的0和1对调，或平局时换个选法，会得到不同的码字，但平均长度同样短。

### 4. 前缀码：谁也不是谁的开头

码字只挂在树叶上，所以没有哪个码字是另一个码字的开头，这叫前缀码。选一个符号，或直接点积木，看它从根出发的路径。

常见的D只走一步；少见的A和B要走三步，比固定2位还长一位。

### 5. 编码，再沿着树解码

把消息DDCDAB逐个换成码字，连起来是11位：00100110111。解码时从根出发，读到0往左、读到1往右，碰到积木就写下一个符号，再回到根。不用分隔符，也不会读错。

同一消息用固定2位编码要12位。动画已放慢，便于观看。

### 6. 平均每个符号约1\.92位

按5、7、10、15的比例，37个符号用霍夫曼码共71位，平均约1\.92位；固定2位要74位。一句话：越常见的符号码字越短，平均就更省位。

这里不计码表（树）本身的存储开销，即琥珀色的“\+?”段；数据很少时它可能抵掉节省。霍夫曼编码不是加密，也不保证每种输入都变短。长度条按位数比例绘制，仅示意。