哈夫曼编码 哈夫曼树 哈夫曼树（Huffman Tree）也是一种特殊的二叉树，这种树的所有叶子结点都带有权值，从中构造出带权路径长度最短的二叉树，即哈夫曼树。 哈夫曼树的定义 设二叉树具有n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和,叫做二叉树的带权路径长度,记作: 
其中,为第i个叶子结点的权值,l为第i个叶子结点的路径长度。如图6.19所示的二叉树, 它的带权路径长度值WPL=1×3+3×3+2×2+4×1=20
如果给定一组具有确定权值的叶子结点· 可以构造出不同的带权二叉树， 它们的带权路径长度并不相同· 我们把其中具有最小带权路径长度的二叉树称为哈夫曼树·.
哈夫曼树的构造 
哈夫曼编码 哈夫曼编码具有广泛的应用， 利用哈夫曼树构造的用于通信的二进制编码称为哈夫曼编码。例如： 有一段电文“ CAST囗TAT囗A囗SA “（ 其中,“ 囗” 表示一个空格） 。统计电文中字母的频度 f(‘C’)=1,f(‘S’)=2,f(‘T’)=3,f(‘囗’)=3,f(‘A’)=4 。 用频度{ 1 ， 2 ， 3 ， 3 ， 4 } 为权值生成哈夫曼树． 并在每个叶子上注明对应的字符。树中从根到每个叶子都有一条路径， 对路径上的各分枝约定指向左子树根的分枝表示“ 0 ” 码， 指向右子树的分枝表示“ 1 ” 码， 取每条路径上的“ 0 ” 或“ 1 ” 的序列作为和各个叶子对应的字符的编码， 这就是哈夫曼编码。对应图6- 22 的哈夫曼树，上述字符编码为：
编码过程：
信源熵 在信息论中，熵（英语：entropy）是接收的每条消息中包含的信息的平均量，又被称为信息熵、信源熵、平均自信息量。这里，“消息”代表来自分布或数据流中的事件、样本或特征。（熵最好理解为不确定性的量度而不是确定性的量度，因为越随机的信源的熵越大。）来自信源的另一个特征是样本的概率分布。这里的想法是，比较不可能发生的事情，当它发生了，会提供更多的信息。由于一些其他的原因，把信息（熵）定义为概率分布的对数的相反数是有道理的。事件的概率分布和每个事件的信息量构成了一个随机变量，这个随机变量的均值（即期望）就是这个分布产生的信息量的平均值（即熵）。熵的单位通常为比特，但也用Sh、nat、Hart计量，取决于定义用到对数的底。 采用概率分布的对数作为信息的量度的原因是其可加性。例如，投掷一次硬币提供了1 Sh的信息，而掷m次就为m位。更一般地，你需要用log2(n)位来表示一个可以取n个值的变量。 在1948年，克劳德·艾尔伍德·香农将热力学的熵，引入到信息论，因此它又被称为香农熵。 熵的计算 当取自有限的样本时，熵的公式可以表示为： 在这里b是对数所使用的底，通常是2,自然常数e，或是10。当b = 2，熵的单位是bit；当b = e，熵的单位是nat；而当b = 10,熵的单位是Hart。 程序实现： 文件结构 核心代码介绍 字频统计code 对每个出现的字节进行统计 构建哈夫曼树code 根据字频表，每次选取频率最小的两个组成一组，然后权值相加放入字频表，再选字频最小的两个。 生成哈夫曼码表 递归的方法找到每个叶子的路径，走左边为0，走右边为1. 总结 在实现字频查找和编码表的生成，都采用直接建表，在对应value位置上赋值，提高了压缩速度。 [3]中生成字频代码如下,需要对每个读取的字符与已有的字频表进行匹配，时间复杂度很高。优化以后，效率提高了近十倍。 结果显示： 对一个文本文件进行编码压缩和解码，如下：
运行结果：
生成文件：（1.txt.data是编码后的输出文件，1.txt.txt是解码文件） 
输入一张bmp图片。
编码压缩后：
大小是原来的48%。 选取了三张图片，对比一下理想信源熵和平均码长 图片1信源熵：3. .平均码长：3. 图片2信源熵：4. .平均码长：4. 图片3信源熵：3. .平均码长：3. 可以看到哈夫曼编码很接近香农熵。 github：https://github.com/zldz/huffmanEncode 参考： [1]数据结构与算法教程-李春葆-125页 [2]https://github.com/FLHonker/HffmanCompress [3]https://github.com/PiggyGaGa/Information-Theory-Source-Coding [4]Matlab霍夫曼编码器
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/82785.html
