霍夫曼树
霍夫曼树 是由美国计算机科学家大卫·霍夫曼（David Albert Huffman）（又译为哈夫曼、赫夫曼）在1952年发明霍夫曼编码所用到的特殊二叉树。为了纪念他的成就，于是就叫 霍夫曼树，他的编码方法称为 霍夫曼编码。
从二叉树中一个节点到另一个节点之间的分支构成两个节点之间的路径，路径上的分支数目称做路径长度。树的路径长度就是从树根到每一节点的路径长度之和。
在带有权重的节点中，节点带权的路径长度是从该节点到树根之间的路径长度与节点上权的乘积。树的带权路径长度是树中所有叶子节点的带权路径长度之和。其中带权路径长度最小的二叉树称做 霍夫曼树，也称为 最优二叉树。
构建霍夫曼树
1.先把有权值的叶子节点按照从小到大的顺序排列成一个有序序列。
2.取前两个最小权值的节点作为一个新节点（T1）的两个子节点，注意相对较小的是左节点，稍大点的是右节点。
3.把 T1 2个子节点的和，加入到剩余有序序列中，按第二步的规则构建新的节点。
4.重复第三步，直到连上所有节点为止。这棵树便是 霍夫曼树。
霍夫曼编码
按照需要编码的字符集的权值来构造一棵 霍夫曼树。规定霍夫曼树的左分支代表 0，右分支代表 1，则从根节点到叶子节点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是 赫夫曼编码。
比如现在有一段内容“ACBDEDABDA”需要传输。假设一个字母占 3 位，A=000,B=001,C=010,D=011,E=100。那么这段内容的编码是 000010001011100011000001011000（占 30 位）。
假设 ABCDE 的权重分别为 32,20,10,30,8。那么构建好霍夫曼树后 A=11,B=01,C=001,D=10,E=000。霍夫曼树编码内容是 1100101100001011011011（占 22 位）。
构建好的霍夫曼树
image
根据霍夫曼树转换的编码
image
根据上面例子，用霍夫曼编码，节省了 8 位。说明数据被压缩了，节约了大约 27% 的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。
编码中非0即1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。
在解码时，还是要用到霍夫曼树，即发送方和接收方必须要约定好同样的霍夫曼编码规则。
总结
霍夫曼树 是根据权重来构建的二叉树，我们也称为 最优二叉树。
它的主要作用是用来编码，也可以用来压缩数据。也可用来编码之后传送给第三方，提升安全性和节省网络资源，然后在根据双方约定好的 霍夫曼树 进行解码，可以做到无损编码和无错解码。
PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。
网友评论