哈夫曼编码

霍夫曼编码(Huffman Coding)又译为哈夫曼编码、赫夫曼编码,是一种用于无损数据压缩的熵编码(权编码)算法。由美国计算机科学家大卫·霍夫曼(David Albert Huffman)在1952年发明

霍夫曼树常处理符号编写工作。根据整组数据中符号出现的频率高低,决定如何给符号编码。如果符号出现的频率越高,则给符号的码越短,相反符号的号码越长。假设我们要给一个英文单字"F O R G E T"进行霍夫曼编码,而每个英文字母出现的频率如下图

下面是算法过程:

进行霍夫曼编码前,我们先创建一个霍夫曼树

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

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

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

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

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

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

最后产生的树状图就是霍夫曼树

进行编码:

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

2.从树根至树叶依序记录所有字母的编码

实现方式请参考:

维基-霍夫曼编码

geeksforgeeks-huffman-coding

上一篇: 最小生成树
下一篇: 迪杰斯特拉最短路径
作者邮箱: 203328517@qq.com