贪心算法应用-哈夫曼编码

  哈夫曼编码应用于数据文件和图像压缩的编码方式。其压缩率通常在20%~90%之间、在进行远距离通信时,通常需要把将要传送的文字转换为由二进制字符组成的字符串,并使要传送的电文总长度尽可能的短。显然只要将点文章出现次数多的字符采用尽可能短的编码,就可以减少要传送的电文总长度。

哈夫曼编码的核心思想:

(1)每一个字符用一个0,1串作为其代码,并要求任意一个字符的代码都不是其他字符代码的前缀。

(2)用字符在文件中出现的频率来建立一个用0,1串表示各字符的最优表示方式,即使出现频率高的字符获得较短编码,出现频率较低的字符获得较长编码。

(3)将字符在文件中出现的频度值作为一颗二叉树的叶子节点的权值,并通过构造一颗哈夫曼树得到最优前缀码。

哈夫曼树的构建

哈夫曼树又称为最优二叉树。它是由n个带权叶子节点构成的所有二叉树中,带权路径长度最小的二叉树(即树中所有叶子节点的带权路径长度之和)。显然,寻找哈夫曼编码的过程就是构造哈夫曼树的过程。

构造哈夫曼树的步骤

1)用给定的n个权值{w1,w2……w3}对应的n个节点构成n颗二叉树的森林 F={T1,T2……Tn},其中每一颗二叉树Ti都只有一个权值为Wi的根节点,其左右子树为空。

2)在森林F中选择两颗根结点权值最小的二叉树,作为一颗新二叉树的左右子树,标记新二叉树的根结点权值为其左右子树的根结点权值之和。

3)从F中删除被选出的那两颗二叉树,同时把新构成的二叉树加入到森林F中。

4)重复第二、三操作,直到森林中只含有一颗二叉树为止,此时得到的这颗二叉树就是哈夫曼树。

哈夫曼树中没有度为1的结点,且具有n个字符的哈夫曼树的结点总数为2n-1个,因此可以使用顺序存储结构来实现哈夫曼算法。将结点信息存储在一个2n-1个的一维数组中。当构造完哈夫曼树后,求每一个字符的编码过程就是走一条从叶子结点到根结点的路径。译码的过程需要走一条从根结点到叶子结点的路径。因此,哈夫曼树的结点结构中一个包含其孩子结点和父节点的信息。

拥抱明天! 不给自己做枷锁去限制自己。 别让时代的悲哀,成为你人生的悲哀。
原文地址:https://www.cnblogs.com/dd2hm/p/7228353.html