霍夫曼编码基本原理

背景

霍夫曼编码是最短的一种编码方式，霍夫曼读研的时候的老师给他们两个选择，发表一篇能用最简洁的方法编码或者老老实实准备考试。霍夫曼选择了第一个，灵光一现设计出了霍夫曼编码。

基本原理

先统计每个字母出现的概率，按照出现的大小排队，把最小的两个概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个相加，依次类推，直到最后变成1。将路线上左右两边按照高路线是1，低路线是0编好。然后自上往下依次写路线上的0|1值。最终形成霍夫曼编码。

过程如下：

• 下面是每个字母出现的概率

• 霍夫曼树生成过程

• 最终得到的编码

本篇文章来至：学新通