霍夫曼编码
霍夫曼编码
霍夫曼编码（Huffman Coding）是一种无损的编码算法，在数据压缩和信息传输领域有广泛的应用。它是由戴维·霍夫曼（David Albert Huffman，1925.08.09-1999.10.17）于1952年所发明（发表于论文《A Method for the Construction of Minimum-Redundancy Codes》）。
1951年，正在麻省理工攻读博士学位的霍夫曼收到了他的老师Robert M. Fano教授（给全班学生）布置的一个选择题：或者努力复习准备期末考试，或者交出一份学期论文——找到使用二进制代码表示数字、字母或者其他符号的最佳编码方法——实际上这正是Fano教授自己正在研究的课题。
霍夫曼不想参加考试，于是选择了挑战论文。挑战的过程无疑是痛苦的，不过幸好时间没有那么长——眼看成功无望，霍夫曼决定“悬崖勒马”，好好复习准备期末考试——奇迹在最后一刻发生了。准备将论文草稿扔进垃圾桶的那一刹那，霍夫曼突然间灵光一现，找到了答案。“突然恍然大悟，犹如闪电一般”，霍夫曼回忆那个时刻，如是说到。
于是，霍夫曼提出了以他名字命名的“霍夫曼编码”。那么，霍夫曼编码究竟是解决什么样的问题呢？简单地说，就是任意多段文字（或者数字、或者其他符号），该用什么编码表示，使得其平均编码长度最短。霍夫曼是怎么做的呢？我们以一个简单的例子，来描述霍夫曼编码的算法。
比如，对于字符串“AABCBADAEACCBDB”（记为S1），最常见、最简单的是编码方式ASCII（American Standard Code for Information Interchange，美国信息交换标准代码）。每个字母占用8个比特（A = 0x41 = 01000001，B = 0x42 = 01000010，...），那么S1将占用120个比特（120 = 15 * 8）。不过，这种编码方式，似乎有点浪费。
换个思路，既然S1中其实只包含5个不同的字母（ABCDE），那么实际上可以用3个比特来编码每个字母：A = 000、B = 001、C = 010、D = 011、E = 100。我们将这种编码方式取名A3码（只是随便取一个名字）。那么，按照A3编码，S1将占用45个比特（45 = 15 * 3）。虽然比ASCII码要好很多，不过这似乎这并不是最短的，而且也没有任何通用性可言。比如，对于S2 = “ABCDEFGHI”，此编码方式就失效了（因为按照这种方式，3个比特无法表达9个不同的字母）。
ASCII码和A3码，都是定长码——每个字母所占用的比特数是相同的（ASCII = 8，A3 = 3），如果换个思路，改成变长码呢？比如这样编码（取名V码）：A = 0（1个比特）、B = 1（1个比特）、C = 01（2个比特）、D = 10（2个比特）、E = 11（2个比特）。按照V码，S1将占用21个比特（21 = 5 * 1 + 4 * 1 + 3 * 2 + 2 * 2 + 1 * 2）。从编码长度来说，这看起来非常不错，但是V码却有个致命问题，那就是歧义性，如图所示。
通过图可以看到，由于歧义性，V码显然不是一种合适的编码方式。不过，饶是如此，它的“变长”编码方式，却有着霍夫曼编码的影子。霍夫曼编码的精髓，正是“变长”+“无歧义”（当然，还包括“无损”）。而且为了使（平均）编码长度最短，霍夫曼编码使得出现频率最高的字母使用最短编码、出现频率最低的字母使用最长编码。
第1步，霍夫曼编码统计各个字母的出现频率（出现次数），然后按照频率大小，从小到大排列。对于S1，霍夫曼编码的统计排序结果，如表所示。
第2步，霍夫曼编码开始构建二叉树。选取最小频率的两个节点（1:E）、(2:D)，并将其频率相加，作为父节点，如图所示。
第3步，将新生成的父节点与原来的节点合并，组成新的霍夫曼编码统计排序表，如表所示。
表中，新生的节点命名为“3”，同时它的“频率”也设置为3。另外，由于E、D已经构建为霍夫曼二叉树的叶子节点，所以，从霍夫曼表中删除。
接下来，重复第2步，得到的霍夫曼二叉树，如图所示。
重复第3步，得到的霍夫曼表，如表所示。
注意，表中新生成的节点“6”（“3”节点和C节点的父节点），按照频率顺序，排在了最后一列。
接下来，继续重复第2步、第3步，所生成的霍夫曼树和霍夫曼表，分别如图和表所示。
仍然是继续重复第2步、第3步，所生成的霍夫曼树和霍夫曼表，分别如图和表所示。
通过表可以看到，只剩下一个节点，那么迭代结束。
迭代结束以后，将图的边，打上标记，左为“0”，右为“1”，如图所示。
按照图，则字母ABCDE就可以得到霍夫曼编码：从根节点开始，到达对应叶子节点的所有路径上“标记”组合，如图和表所示。
通过图或表可以看到，任何一个字母的编码，都不会是另一个字母编码的前缀。这种编码也称为前缀编码（Prefix Encoding）。但是这种称呼，非常令人迷惑：明明不是人家的前缀，偏偏要叫前缀编码。为了消除迷惑呢，这种编码有时候也被称为无前缀编码（Prefix-free Encoding）。迷惑是消除了，但是更加混乱了——前缀编码和非前缀编码，说的竟然是同一回事。
好吧，不纠结其他称呼了，只须记住“霍夫曼编码”这个名字就好，其算法如伪码所示。
# 伪码4-１ 霍夫曼编码算法
S = 待编码对象 # 比如字符集，等等
HuffmanTable = 统计并且按照出现频率排序(S) # 比如[E:1,D:2,C:3,B:4,A:5]
HuffmanTree = [] #霍夫曼二叉树，初始化为空
# 构建霍夫曼树
while(True)
{
if (HuffmanTable.size() <= 1)
{
break;
}
# 构建霍夫曼树
node1, node2 = 从HuffmanTable中选取频率最小的前两个元素
p.value = node1.value + node2.value # 父节点
p.left_son = node1
p.right_son = node2
p.left_edge = 0
p.right_edge = 1
HuffmanTree.add(p)
HuffmanTree.root = p
# 更新霍夫曼表
HuffmanTabel.remove(node1, node2)
HuffmanTable.add&sort(p)
}
# 构建霍夫曼编码
遍历霍夫曼树(HuffmanTree)
针对每个叶子节点，得到霍夫曼编码