哈夫曼编码和译码系统(附源代码).docx

哈夫曼编码和译码系统 哈夫曼编码是一种_variable-length prefix coding_技术，用于压缩数据，提高数据传输效率。该系统主要由三个部分组成：哈夫曼树建立、编码和译码。 一、需求分析 在传送电文时，人们总是希望传送时间尽可能短，这就是要求使电文代码长度尽可能短。哈夫曼编码可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统能够对待传输数据预先编码，在接收端将传来的数据进行译码。 二、概要设计 本程序主要用到了三个算法： （1）哈夫曼树建立、编码：在初始化过程中间，要用输入的字符和权值建立哈夫曼树，并求得哈夫曼编码。 （2）串的匹配：在编码过程中间，要对已经编码过的代码译码，利用循环，将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较。 （3）哈夫曼遍历：在印哈夫曼树的过程中，因为哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出。 三、详细设计及编码实现 构造哈夫曼树的方法如下： 1. 初始化：每个字符就是一个结点，字符的频度就是结点的权。 2. 将结点按频度从小到大排序。 3. 选取频度最小的两个结点，以它们为儿子，构造出一个新的结点；新结点的权值就是它两个儿子的权值之和。 4. 构造之后，从原来的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去。 5. 如果结点序列里只剩下一个结点，表示构造完毕，退出。否则回到第一步。 编码： 1. 上面已经生成了树，接着就该对该树进行编码了。 2. 可以假定，对某个结点而言，其左孩子在当前阶段的编码为 0，右孩子的编码为 1。 3. 这样就可以通过“树的遍历”的方式来生成字符一一编码对照表。 译码： 1. 译码也是个简单的查表--替换过程。 2. 如果利用该种编码发送字符串，则它的“字符一一编码”对应表也必须发送过去，不然对方是不知道怎么解码的。 3. 对给出的一串编码，从左向右，将编码组合起来并查表，“一旦”找到有匹配的字符，则马上将当前的编码替换为对应的字符。 四、实验总结 哈夫曼编码和译码系统的实现可以大大提高信道利用率，缩短信息传输时间，降低传输成本。该系统可以应用于各种领域，例如数据压缩、图像压缩、文本压缩等。