哈夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码。属于无损压缩编码。哈夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。
Huffman编码过程的几个步骤:
l)将信号源的符号按照出现概率递减的顺序排列。(注意,一定要递减)
2)将最下面的两个最小出现概率进行合并相加,得到的结果作为新符号的出现概率。
3)重复进行步骤1和2直到概率相加的结果等于1为止。
4)在合并运算时,概率大的符号用编码0表示,概率小的符号用编码1表示。
5)记录下概率为1处到当前信号源符号之间的0,l序列,从而得到每个符号的编码。
举个简单例子:
符号 {A,B,C,D,E}
计数 {15,7,6,6,5}
概率 {0.38461538,0.17948718,0.15384615,0.15384615,0.12820513}
在这种情况下,D,E的最低频率和分配分别为0和1,分组结合概率的0.28205128。
A:
B:
C:
D: 0
E: 1
现在最低的一双是B和C,所以他们就分配0和1组合结合概率的0.33333333在一起。
A:
B: 0
C: 1
D: 0
E: 1
这使得BC和DE所以0和1的前面加上他们的代码和它们结合的概率最低。
A:
B: 00
C: 01
D: 10
E: 11
然后离开只是一个和BCDE,其中有前缀分别为0和1,然后结合。
A: 0
B: 100
C: 101
D: 110
E: 111

这使我们与一个单一的节点,我们的算法是完整的。

完成二叉树
1.为每个符号建立一个叶子节点,并加上其相应的发生频率
2.当有一个以上的节点存在时,进行下列循环:
1)把这些节点作为带权值的二叉树的根节点,左右子树为空
2)选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3) 把权值最小的两个根节点移除
4) 将新的二叉树加入队列中.
3. 最后剩下的节点暨为根节点,此时二叉树已经完成

参考链接: http://blog.csdn.net/abcjennifer/article/details/8020695

标签: none

添加新评论