霍夫曼编码摘录(Huffman coding)

2014/04/13 21:07
阅读数 190

计算机资料处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明霍夫曼树的WPL是最小的。


(一)进行霍夫曼编码前,我们先建立一个霍夫曼树。

  • ⒈将每个英文字母依照出现频率由小排到大,最小在左,如Fig.1

  • ⒉每个字母都代表一个终端节点(叶节点),比较F.O.R.G.E.T五个字母中每个字母的出现频率,将最小的两个字母频率相加合成一个新的节点。如Fig.2所示,发现FO的频率最小,故相加2+3=5。

  • ⒊比较5.R.G.E.T,发现RG的频率最小,故相加4+4=8。

  • ⒋比较5.8.E.T,发现5E的频率最小,故相加5+5=10。

  • ⒌比较8.10.T,发现8T的频率最小,故相加8+7=15。

  • ⒍最后剩10.15,没有可以比较的对象,相加10+15=25。

(二)进行编码

  • 1.给霍夫曼树的所有左链结'0'与右链结'1'。

  • 2.从树根至树叶依序记录所有字母的编码,如Fig.3






展开阅读全文
打赏
0
5 收藏
分享
加载中
更多评论
打赏
0 评论
5 收藏
0
分享
返回顶部
顶部