贪心算法之哈夫曼编码问题

通常的编码方法有固定长度编码和不等长度编码两种。这是一个设计最优编码方案的问

题,目的是使总码长度最短。这个问题利用字符的使用频率来编码,是不等长编码方法,使

得经常使用的字符编码较短,不常使用的字符编码较长。如果采用等长的编码方案,假设所

有字符的编码都等长,则表示 n 个不同的字符需要 ⎡log n⎤ 位。例如,3 个不同的字符 a、b、⎢⎥

c,至少需要 2 位二进制数表示,a 为 00,b 为 01,c 为 10。如果每个字符的使用频率相等,固定长度编码是空间效率最高的方法。

不等长编码方法需要解决两个关键问题:(1)编码尽可能短

我们可以让使用频率高的字符编码较短,使用频率低的编码较长,这种方法可以提高压缩率,节省空间,也能提高运算和通信速度。即频率越高,编码越短。

(2)不能有二义性
例如,ABCD 四个字符如果编码如下。
A:0。B:1。C:01。D:10。
那么现在有一列数 0110,该怎样翻译呢?是翻译为 ABBA,ABD,CBA,还是 CD?那

么如何消除二义性呢?解决的办法是:任何一个字符的编码不能是另一个字符编码的前缀,即前缀码特性。

1952 年,数学家 D.A.Huffman 提出了根据字符在文件中出现的频率,用 0、1 的数字串表示各字符的最佳编码方式,称为哈夫曼(Huffman)编码。哈夫曼编码很好地解决了上述两个关键问题,被广泛应用于数据压缩,尤其是远距离通信和大容量数据存储方面,常用的JPEG 图片就是采用哈夫曼编码压缩的。 

哈夫曼编码的基本思想是以字符的使用频率作为权构建一棵哈夫曼树,然后利用哈夫曼树对字符进行编码。构造一棵哈夫曼树,是将所要编码的字符作为叶子结点,