文档介绍：学年论文题目: 基于哈弗曼的编码实现学生: 学号: 院(系): 专业: 指导教师: 年月日 1 基于哈弗曼的编码实现摘要: Huffman 编码是一种应用广泛的可变长编码方式,是二叉树的一种特殊转化形式。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。哈弗曼树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。哈弗曼编码的原理是:将使用次数多的代码转换成长度较短的编码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。数据压缩的过程称为编码,解压缩的过程称为译码。哈夫曼编码是一种根据字母的使用频率而设计的变长码,能提高信息的传输效率, 至今仍有广泛的应用。关键词: Huffman 编码,数据压缩,编码,译码,二进制码 Based on the Huffman 's coded A BSTRACT :Huffman coding isa widely used way of variable length coding, isa kind of special transformation form of binary tree. Use Huffman tree seeks municate the binary coding as Huffman encoding. Harvard man in the tree from the root to each leaf has a path, the path branches agreed: "0" refers to the branch of the left subtree said, pointing to the right subtree of branch said "1" code, take each path of "0" or "1" on the sequence as and the corresponding character coding, that is the Huffman encoding. Harvard, coding principle is: will use more code conversion grow shorter encoding, and use fewer can use longer encoding, and keep only solvability of coding. Process known as encoding pression, pression process known as decoding. Huffman encoding isa designed according to the use of letters frequency variable length code, can improve the efficiency of information transmission, there are still widely used. K EYWORDS : Huffman coding, pression, coding, decoding, binary code 2 1 哈弗曼原理通常我们把数据压缩的过程称为编码,解压缩的过程称为译码。本文根据 Huffman 编码原理,在详细设计中, 根据权值和最小的根本原则, 输入要编码的字符集及其它的权值, 再根据节点 Node 类, 建立哈夫曼树,并进行编码,最后输出哈夫曼编码。在完成 Huffman 编码后,利用其构建的哈夫曼编码树来进行译码。与编码过程不同,译码过程中, 将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较,译出一个字符后,循环比较下一个字符的编码,直到所有二进制码全部译出为止。哈夫曼编码方法的具体过程是:首先把信源的各个输出符号序列按概率递降的顺序排列起来, 求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列( 参与求概率之和的这两个序列不再出现在新的排列之中) 。然后,对参与概率求和的两个符号序列分别赋予二进制数字 0和1 。继续这样的操作,直到剩下一个以 1 为概率的符号序列。最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字。哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为 0 层, 叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记