赫夫曼编码：理论基础和最佳编码原理

赫夫曼编码完全依据字符出现的概率来构造异字头的平均长度最短的码字，称之为最佳编码。赫夫曼编码将使用次数较多的代码用较短的编码代替，将使用次数较少的代码用较长的编码代替，并且确保编码的唯一可解性。其根本原则是压缩编码的长度(即字符的统计数字×字符的编码长度)最小，也就是权值和最小。

赫夫曼编码是一种无损压缩方法，其一般算法如下。

(1)符号概率:统计信源中各符号出现的概率，按符号出现的概率从大到小排序。

(2)合并概率:提取最小的两个概率并将其相加，合并成新的概率，再将新概率与剩余的概率集合。

(3)更新概率:将合并后的概率集合重新排序，再次提取其中最小的两个概率，相加得到新的概率进而组成新的概率集合。如此重复进行，直到剩余最后两个概率之和为1。

(4)分配码字:分配码字从最后一步开始逆向进行，对于每次相加的两个概率，大概率赋0，小概率赋1，当然也可以反过来赋值，即大概率赋1，小概率赋0；特别地，如果两个概率相等，则从中任选一个赋0，另一个赋1。依次重复该步骤，从第一次赋值开始进入循环处理，直到最后的码字概率和为1时结束。将中间过程中所遇到的0和1按从最低位到最高位的顺序排序，就得到了符号的赫夫曼编码。(www.xing528.com)

赫夫曼编码是最佳的变长编码，其特点如下。

(1)可重复性:赫夫曼编码不唯一。

(2)效率差异性:赫夫曼编码对于不同的信源往往具有不同的编码效率。

(3)不等长性:赫夫曼编码的输出内容不等长，因此给硬件实现带来一定的困难，也在一定程度上造成了误码传播的严重性。

(4)信源依赖性:赫夫曼编码的运行效率往往要比其他编码算法高，是最佳的变长编码，但是，赫夫曼编码以信源的统计特性为基础，必须先统计信源的概率特性才能编码，因此对信源具有依赖性，这也在一定程度上限制了赫夫曼编码的实际应用。