霍夫曼树的构造及其在信息编码中的应用

沙洋师范高等专科学校学报2007沙洋师范大学学报2007年第5期霍夫曼树的结构及其在信息编码中的应用任正云*（荆门职业技术学院，湖北荆门448000）摘要: 霍夫曼树是最优的二叉树搜索树，对于加权二叉树，最大的权重最接近根节点，按照这种思路，所有由加权结点组成的二叉树都有权重，路径长度W PL最小的二叉树为关键词: 霍夫曼树结构；数据编码要求；应用中的图形分类: TP393. 07文档标识码: A货号: 1672-0768（ 2007）05- 0031- 03数据编码技术已在计算机数字通信中占有重要地位，在数字通信的过程中，经常出现问题. 问题: 信息传输速度与信息传输的可靠性，传输的数据编码的长度以及数据解码容易产生的歧义性之间存在无法调和的矛盾. 上述问题使得数据编码技术的质量在很大程度上影响通信质量. 数据的编码取决于数据结构. 树结构是一种非常广泛使用的结构. 除了使用树结构来组织各种目录外，许多算法还经常使用数字结构作为中间结构来解决问题和确定对策.

在树结构中，二叉树的应用是最常见的. 在构造加权路径的二叉搜索树中，具有最小加权路径的路径不一定是深度最小的二叉搜索树，而是权重. 叶越大，二叉树离根节点越近. 具有最小叶节点加权路径长度的该二叉搜索树是霍夫曼树. 1. Huffman树及其构造方法Huffman树是最优的二叉搜索树. 构造霍夫曼的过程如下: 给定一组权重WG = {W 1 W 2，W 3 ,, W n}，将权重分配给n个节点，从而生成森林F，使得F有n个树T只有一个根节点，i有权重W； i forest根据根的重量从小到大对森林F中的树木进行分类； ⑶从森林中取出第一棵和第二棵树构成一棵新树，以使新树的根的权重等于两棵树的根的权重之和. 第一个子树是新树的左子树，第二个子树是右子树，并将其添加到目录林F中； ⑷重复步骤⑵，直到森林F中只有一棵⑶树. 在此指出，如果选择权重最小的两个二叉树的根节点的权重之和，则选择*的权重. 删除选定的二叉树之后，林中一棵或多棵二叉树的根节点如果相等，则不会将新的二叉树插入原始林中，以确保最佳二叉树的加权路径长度最小.

这与霍夫曼编码中的情况不一致，因为如果在霍夫曼编码中使用此方法，则会导致二进制代码前缀重新编码. 当处理不同的问题时，我们设定的目标是不同的，问题处理过程的设计方法也不同. 这些独特的设计方法可能意味着满足某些加工要求. 例如，基于上述具有最小加权路径长度的二叉树，基于它们，设计的处理方法可能意味着将某些成本（例如时间，空间和其他资源）最小化，因此霍夫曼树具有理论应用价值. . 实际上，将霍夫曼树应用于数据编码技术，即使用霍夫曼方法对要发送的数据信息（尤其是字符数据）进行编码，可以大大缩短原始的长消息代码，并获得平均的最短消息代码. ，并且设计的二进制代码可以确保解码的唯一性. 下面是一般情况下的一个示例: 设置一组权重WG = {13，8 6 25 36 5 2 ,,,,, 19}霍夫曼树的结构如图1和图1所示. 很容易计算出这棵树. 霍夫曼树加权路径长度W PL = 8 3+ 6 4+ 2 5+ 5 5+ 25 2+ 13 3 + 19 3+ 36 2 = 301，这是许多二叉树中的加权路径接收日期: 2007-03- 19作者简介: 任正云（1963-），男，荆门职业技术学院计算机学院讲师，研究方向: 软件开发.

31任正云最小的树. 当然，通过观察很容易发现最佳二叉树不是唯一的. 这是因为具有相同路径长度和不同权重的节点可以交换位置，而不会影响整个树的加权路径长度. 有两种特殊情况: n个加权节点按从小到大的权重排列以获得一系列节点权重. 构造的霍夫曼树中每个节点的右子节点是终端节点. 点. 在这种情况下，设计的每个字的二进制代码长度互不相同（两个具有最长代码位数的字是相同的）. 在另一种情况下，如果由具有最小权重的两个节点组成的新二叉树的根节点的权重大于或等于原始林中任何两个（或更多）二叉树的权重（通常，每个节点的权重都比较大并且值彼此接近），那么构造的霍夫曼树就是一个完整的二叉树. 从编码的角度来看，最多有两个代码长度，长度的差异仅为1. 2.数据编码技术的要求. 我们知道数据发送方从发送方发送消息代码. 接收后，接收者必须能够将接收到的消息代码转换为原始数据. 发送者和接收者需要使用一套编码技术，即数字编码技术. 以字符数据为例，在数据通信中，通常将要传输的数据转换为二进制字符串0和1进行传输和传递.

在编码过程中，由于这些字符串仅由01组组成，并且可能要传输许多字符，因此许多字符必须由两个以上的二进制代码组成才能彼此区分. 然后出现一对矛盾: 如果使用固定长度编码，即每个字符的二进制代码数相同，则消息代码变得非常冗长；如果使用可变长度编码，则每个字符的二进制代码的位数是不同的，即长度不同，在接收到消息后很难拆分较长的二进制消息代码，以确定它是单个字符还是二进制. 多个字符的组合，因为位数较少的代码可能是位数较大的代码前缀，即解码不是唯一的. 因此，我们受到霍夫曼树的启发，将霍夫曼树应用于数据编码，不仅可以使消息代码的平均长度最短，而且可以使编码满足前缀编码的条件，以确保解码无歧义. 3.霍夫曼树在通信数据编码中的应用当霍夫曼树用于信息编码时，权重可以用作某个符号的频率. 当应用于判断过程时，可以认为是某数据的出现. 频率. 使用霍夫曼树的结构时，权重是搜索频率. 频率越大，根节点越近. 测试或判断的结果被视为两个方向. 选择其中一个分支进行进一步的判断和测试，最后获得特定数据的属性. 例如，要完成一批正整数的分类，要求如下: ⑴Ai20属于第一类，出现频率为2 /c 哈夫曼树编码，18; 32霍夫曼树的构造及其在信息编码中的应用⑵20 100属于第四类，频率为7/18，.

给出的每个数字都需要判断它是否属于第n个类别. 可以以一般的逻辑顺序获得判断过程一. 如图2所示，此判断过程将获得最长的平均执行时间. 50属于第二类，发生频率为4 /. 图2对上述判断方法进行了稍许修改，即霍夫曼树的构造原理组织了判断过程. 如图3所示，判断过程的平均执行时间最短. 图3从图3可以看出，只有一个判断，即节点的权重为7/18，才能获得频率最高的第四种数据（7/18）. 该节点最接近下一个节点. ， 另一个例子. 要发送英文单词car care ear area ,,,,, core race Rear arr，每个不同的字符都会出现，并且每个，. 出现字符. 在此示例中，总共有5个字符出现在不同的时间，它们是a-8 c- 4 e-6 o ,,,-1，r- 10.使用每个字符出现的次数作为它们代表的二叉树的根，根据霍夫曼算法构造了霍夫曼树（图4）. 如果将左侧子树的路径指定为0，并将右侧子树的路径记录为1，则可以获得每个字符的以下二进制编码: 10 c 001: ，: ，e 01 o 000 r 11然后我们可以得到这些单词的代码，例如: ，: ，: ，rear代码为11011011. 由于霍夫曼代码是前缀代码，所以很容易将这些二进制代码分开以将它们彼此区分开.

这完成了编码任务. 沙洋师范学院学报，沙洋师范学院学报2007年第5期图4最后，简要给出霍夫曼编码算法: hc =（H uffC ode）m alloc（n * sizeo f（char））: * //分配器的标头指针ch =（字符）m allo c（n sizeof（字符））: //当* *编码ch前的空格ch [n-1] ='0;' \ for（i = 1 i <= n i ++）;; {f = ht [k]. 标准k =我;开始= n-1; //编码终止符的位置做{if（ht [f] left = k）ch [--start] = 0'';否则ch [--start] = 1''f = ht [f]. 标准k =; f}时（！= 0）; f for（j = start-1 j> = 0 j--）;; ch [j] =; ''hc [i] =（字符）ma llo c（（m-start）* sizeo f *（char））; //为第i个Huffman码分配空间n = 0; for（j = 0 j

每个叶节点的长度不超过m. 4.结论霍夫曼编码在数据编码中的应用是各种技术中使用的霍夫曼树的典型特征. 此外，霍夫曼树的加权路径长度最小，这使其可应用于其他特定决策. 例如在多个城市之间铺设通信电缆. 当我们遇到一些特定的应用问题时，对霍夫曼树的原理和应用的研究可以为我们提供启发和解决方案. 参考文献[1]耿国华等. 用C语言描述数据结构[M]. 西安: 西安电子科技大学出版社c 哈夫曼树编码，2002 2. ，[2]陈明. 实用数据结构基础[M]. 北京: 清华大学出版社，陈明，2002 8. [3]周月山，陈立民. 数据结构[M]. 西安: 西安电子科技大学出版社，2005年，第2期. （主编: 陈如一）数字化编译中的Huff and ree及其用法mREN Zheng-yun（Jingm约翰内斯堡技术学院（448000），男，艾伯卡斯特·哈夫里（Abstrac T Huff an ree）是最好的二元搜索法. : 米m，最紧要的是根据想法，用正确的方法构成了基本的条件，并将最短的载荷长度p正确地用于了数字化通信. 计算机通讯的桩技术，它可以有效地缩短电视的时长. Key word的Huffree姿势数字编辑软件: m m33

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-162533-1.html