哈夫曼编码课程设计.pdf

课程设计说明书(论文)用纸

摘要

哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩通常在

20%~90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用

0,1 串表示各字符的最优表示方式。

哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然，还有编

码和译码部分。本系统的前端开发工具是 Visual C++6.0。具有输入字符集大小

及权值大小，构造哈夫曼树，并对用户输入的字符串进行编码以及译码还有退出

四种功能。本程序经过测试后，功能均能实现，运行稳定。

课程设计说明书(论文)用纸

4 算法实现..........................................................4

5 测试分析 ..........................................................7

结 论..............................................................9

参考文献............................................................9

课程设计说明书(论文)用纸

1 问题描述

哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造

平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG 中

就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概

率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根

据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方

哈夫曼的编/译码器。

哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度

的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则

编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫

描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上

标的 0，1 相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出

了一个字符。再回到树根，从二进位串的下一位开始继续译码。软件运行环境及

开发工具是 Visual C++6.0。