Huffman编码流程
Huffman解码流程
打开文本文件统计文件长度 初始化节点 构建哈夫曼树 计算左右分支权值大小,进行无重复前缀编码 哈夫曼编码位操作压缩存储 YES NO 压缩文件成功! 压缩文件失败 计算压缩率% 图3 编码流程 打开压缩文件读取原文件长度进行文件定位 根据哈夫曼编码的长短,对节点进行排序 通过哈夫曼编码的长短,依次解码,从原来的位存储还原到字节存储 在单字节内对相应位置补0 NO YES 解压压缩文件成功! 解压缩文件失败! 图4 解码流程
四、 上机调试
以下是我在上机过程中遇到的一些问题及解决方案
开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就
huffman编码是采用等长编码还是采用不等长问题，采用不登长编码要避免译码的二义性或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“…01…”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。
为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的 huffman树的问题。
基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些语法错误,修正后编译通过。
五、 使用说明
用户进行本程序前，首先要在起工程文件下建立一个待压缩的文本文档，例如：huffman.txt，文档内已有内容，且文档大小大于5K。 运行程序如下图所示
图5 程序主菜单
压缩：
在命令行下输入1对文件进行压缩，根据提示输入刚刚建的文本文件（huffman.txt），和要生成的压缩文件名称，按回车确认进行压缩。
图6 压缩文本
成功执行完毕后如下图所示。
图7 压缩完毕
恢复：
在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称
和恢复后的文件名称，按回车确定，成功执行后如下图所示。
图7 文件恢复完毕
对比：
在命令行下输入3对恢复后的文件和原文件对比，根据提示输入要对比的文件，按回车确认，成功执行后如下图所示。
图8 文件恢复完毕
六、 测试结果
程序功能满足设计要求，测试未发现明显bug，详细可参见 五使用说明。
七、 参考书目
【1】 吴国凤.C/C++程序设计（第2版）【M】.高等教育出版社，2009年9月 【2】 郑莉等. c++语言程序设计（第三版）【M】.北京：清华大学出版社，2003年12月