哈夫曼树与哈夫曼编码及等长编码 哈夫曼树的构造：就是将给定的数据中选择最小的两个权值进行合并，然后重复该操作，构造出一个二叉树。使其带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。 例如：给定几个数值：0.07， 0.19， 0.02， 0.06， 0.32， 0.03， 0.21， 0.01 可以将其扩大一百倍，以方便计算，不会影响哈夫曼树的构造 W={7, 19, 2, 6, 32, 3, 21, 10} 
选择最小的2，3进行合并为5，5 和 6 为最小的再进行合并为 11 ， 重复该操作可以得到该哈夫曼树。 哈夫曼编码： 在进行数据压缩的时候，为了使压缩后的数据文件尽可能短，可采用不定长编码。其基本思想是：为出现次数较多的字符编以较短的编码。为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码，可以利用哈夫曼树来设计二进制编码。 编码的概念： （1）前缀编码：如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称编码是前缀编码。00，001这个就不是前缀编码。其实就是通过这些编码准确得出数据信息，不会混淆。 （2）哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各个支的赋值分别构成一个二进制，该二进制就称为哈夫曼编码 哈夫曼编码性质： （1）哈夫曼编码是前缀编码 （2）哈夫曼编码是最优前缀编码 字母编号出现频率哈夫曼编码等长编码10.0..0.0..0.. 由上面的例子得出该表 如何得出这个哈夫曼编码？以0.07扩大一百倍之后是7为例子讲解： 从叶子结点到根节点：7 ——> 17是左分支，所以赋予0 17 ——> 28是左分支，所以赋予0 28 ——> 60是右分支，所以赋予1 60 ——> 100是右分支，所以赋予1 哈夫曼编码是从根节点到叶子结点：所以0.07的哈夫曼编码是1100. 等长编码就相当于一个从根节点到叶子节点的路径为K的满二叉树，上面列表就是通过一个从根节点到叶子节点的路径为3的满二叉树得来的等长编码，方法和得到哈夫曼编码一样。 
以0.07扩大一百倍后为7来讲解以下; 从叶子结点到根节点： 7——> 26 是左分支，所以赋予0 26 ——>34 是左分支，所以赋予0 34 ——>100是左分支，所以赋予0 等长编码是从根节点到叶子结点，所以等长编码是000 在对多个有序表进行两两合并时，若表长不同，则最坏的情况下总的比较次数依赖于表的合并次序（归并排序），可以借助哈夫曼树的构造思想，依次选择最短的两个表进行合并，这样可以获得最坏的情况下最佳的合并效率
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/45947.html
