基于哈夫曼树的通信数据编码的简单实现

《基于哈夫曼树的通信数据编码的简单实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于哈夫曼树的通信数据编码的简单实现摘要哈夫曼树是相同个数的带权结点所构成的所有二叉树中带权路径长度WPL最小的二叉树，将其应用于计算机通信中数据编码技术可大大缩短电文代码的长度，且避免了电文代码二义性的产生。本文简要介绍了哈夫曼树的原理、构造方法及其在数据编码中的应用。关键字：哈夫曼树带权路径长度数字通信数据编码概述数据编码技术在计算机数字通信中一直占据着重要的地位。这是因为，在数字通信过程中，往往存在以下几个问题：信息传递的速度和所传递信息的可靠性这对不可调和的矛盾，所传递的数据编码的长度和数据译码容易产生的二义性等。基于以上问题，使得数据编码技术的优劣在很大程度上影响着通信

2、的质量。本文所要介绍的基于哈夫曼树的通信数据编码技术主要以数字通信中所传递的数据编码的长度和数据编码容易产生的二义性这两个问题为着眼点，结合数据结构中哈夫曼树的原理，通过解决上述两个问题来提高数字通信的质量。一、哈夫曼树及其构造方法哈夫曼树又叫最优二叉树，由哈夫曼方法构造而得，是数据结构中树形结构的一种特例。当一棵二叉树由n个带权结点构成时，就存在所谓树的带权路径长度的计算问题，即树中所有结点的带权路径之和。由于n个结点可以构造大量的不同形状的二叉树，加之每个结点的权值可能互不相同，因此所有二叉树的带权路径长度也各不一样。最优二叉树就是在这些二叉树中带权路径最小的二叉树。我们知道

3、，在处理不同的问题时，我们的目标也互不相同，问题处理过程的设计方法也不尽相同。而这些独特的设计方法可能意味着要符合一定的处理要求。比如上述带权路径长度最小的二叉树，以它们为基础，设计的处理方法可能意味着某种代价（如时间、空间等资源）的最小化，于是哈夫曼树在理论上便有了应用价值。事实上，将哈夫曼树应用于数据编码技术中，即把要传递的数据信息（尤其是字符数据）用哈夫曼方法加以编码，可以使原本长度很长的电文代码大大缩短，得到平均长度最短的电文代码，且设计出来的二进制代码可以确保译码的唯一性。哈夫曼树的构造方法并不复杂。它的构造算法的思想有些类似于贪心算法，由哈夫曼最早提出。首先给定n个带

4、权结点，设其权值为{,,……,}，这n个结点各自独立构成了n棵二叉树，并且形成一个森林F={,,……,}，每一棵二叉树都只有一个权值为的根结点，无左右子树。根据哈夫曼方法，首先从森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左右子树，把它们的权值之和作为新二叉树的根结点的权值。然后从森林F中删除已经被选中的两棵二叉树，同时把新构成的二叉树的根结点加入到森林F中。然后从新构成的森林F中再选择两棵根结点权值最小的二叉树以构成新的二叉树，以此类推，直到森林中只含有一棵二叉树为止，此时这棵二叉树即为所求的最优二叉树，即哈夫曼树。直观地看这棵新构成的哈夫曼树，容易发现，权值越大

5、的结点离根结点越近，而权值越小的结点则离根结点越远。这样就可以保证这棵最优二叉树具有最小带权路径长度。这里指出一点，若被选中的具有最小权值的两棵二叉树的根结点的权值之和，与删除被选二叉树后的森林中的一棵或多棵二叉树的根结点的权值相等，则不将这棵新二叉树插入原森林中，以保证构成的最优二叉树的带权路径长度最小。这是与哈夫曼编码中的情况不一致的，因为在哈夫曼编码时若采用这种方法将会导致二进制代码的前缀重码。下面给出一般情况下的例子：有6棵仅有根结点而无左右子树的二叉树，其权值为{7，2，5，3，8，4}，则根据哈夫曼算法可以得到此哈夫曼树为（图1）：容易计算，这棵哈夫曼树的带权路径长度

6、WPL（）=2×4+3×4+4×3+8×2+5×2+7×2=72，是众多二叉树中带权路径长度最小的一棵。当然，通过观察29179412758523也容易发现，最优二叉树也并不唯一。这是因为路径长度相等而权值不同的结点间可以互换位置图1而不影响整棵树的带权路径长度。下面介绍两种特例，将n个带权结点按权值由小到大排列，得到结点权值的序列{,,……,}（≤≤……≤），若≥，则构造而得的哈夫曼树中每一个结点的右孩子均为终端结点。在这种情况下设计出来的每个字的二进制编码的长度均互不相同（代码位数最长的二个字相同）。另一种情况是，若由权值最小两个结点构成的新二叉树的根结点的权值，大于等于原森

7、林中任意两个（或多个）二叉树的权值（通俗地说，各结点权值相对较大且值互相接近），则构造出来的哈夫曼树是一棵完全二叉树。从编码的角度说，最终获得的代码长度最多只有两种，且长度相差仅为1。现给出哈夫曼树的数据结构描述：typedefstructHtnode{intweight;//结点的权值//指向双亲和左右孩子的指针intpar;intleft;intright;}Htnode,*HuffTree;现简要给出构造哈夫曼树算法：typedefchar**Huffcode;HuffTr