基于Huffman编码的中文字符压缩算法课程设计

语言类综合项目实践报告（嵌入式操作系统课程设计报告）题目全称：中文压缩算法的实现课程名称：语言类综合项目实践（嵌入式操作系统）指导老师：廖勇职称：副教授语言类综合项目实践报告（嵌入式操作系统课程设计报告）本小组成员任务分工情况实验时间：2014年6月20日目录1、课程设计目的 (4)2、课程设计任务 (4)3、中文压缩算法的设计 (4)3.1中文编码格式说明 (4)3.2 哈夫曼编码说明 (5)3.3流程设计 (6)4、中文压缩算法的实现 (7)4.1编码过程 (7)4.1.1字符频率记录和全局存储 (9)4.1.2创建Huffman树 (9)4.1.3创建Huffman字典 (10)4.1.4存入字典 (12)4.1.5存入文本 (12)4.2解码过程 (14)4.2.1恢复Huffman树 (15)4.2.2解码 (17)5、测试 (20)5.1 命令行打开测试 (20)5.2 帮助信息显示 (21)5.3版本信息显示 (21)5.4压缩测试 (22)5.5 解压字符测试 (23)6、总结 (24)7、参考文献 (24)1、课程设计目的中文压缩是指在一定的数据存储空间下，将相对庞大的中文文本数据重组为满足空间要求的数据集合，重组后的数据占用空间更小，之后利用重组的信息可以将原始信息从压缩的数据中提取出来，并且提取出来的数据于原始数据相一致。

在数据传输，数据存储方面有着重大的意义，中文数据压缩减少了数据存储的空间消耗，传输大文件时增加传输速度。

在现实世界中文中压缩有极其广泛的应用，本文提出一种基于Huffman算法的中文压缩算法的实现方式，实现对中文文本的压缩，此压缩算法为中文文本通用简易的压缩算法，有一定的现实应用意义。

2、课程设计任务中文文本压缩算法能在一定的存储空间内实现文本的压缩和解压，整个过程能在一定时间内完成，此过程采取的算法主要是Huffman算法，我们利用Huffman 算法建立相应的数据字典和Huffman树，压缩和解码也主要依靠Huffman树实现。

此中文压缩软件实现几个主要功能为：●能完整读入包含中文的文本文件●将原始中文文本信息进行转化，存储●建立相应本文压缩的信息，以便数据恢复●将压缩数据完整提取出来此压缩算法能将中文文本完整压缩和恢复，平均压缩率在能达到60%。

3、中文压缩算法的设计3.1中文编码格式说明为了适应计算机处理汉字信息的需要，1981年我国颁布了GB2312国家标准。

该标准选出6763个常用汉字（其中，一级常用汉字3755个，二级汉字3008个）和682个非汉字字符，并为每个字符规定了标准代码，以便在不同的计算机系统之间进行汉字文本交换。

GB2312字符集构成一个94行、94列的二维表，行号称为区号，列号称为位号，每一个汉字或符号在码表中的位置用它所在的区号和位号来表示。

为了处理与存储的方便，每个汉字的区号和位号在计算机内部分别用一个字节来表示。

例如，“学”字的区号为49，位号为07，它的区位码即为4907，用2个字节的二进制数表示为： 00110001 00000111区位码无法用于汉字通信，因为它可能与通信使用的控制码（00H~1FH）（即0~31）发生冲突。

ISO2022规定每个汉字的区号和位号必须分别加上32（即二进制数00100000），经过这样的处理而得的代码称为国标交换码，简称交换码，因此，“学”字的国标交换码计算为：00110001 00000111+00100000 +00100000----------- --------01010001 00100111用十六进制数表示即为5127H。

由于文本中通常混合使用汉字和西文字符，汉字信息如果不予以特别标识，就会与单字节的ASCII码混淆。

此问题的解决方法之一是将一个汉字看成是两个扩展ASCII码，使表示GB2312汉字的两个字节的最高位都为1。

这种高位为1的双字节汉字编码即为GB2312汉字的机内码，简称为内码。

因此，“学”字的机内码为： 11010001 10100111 用16进制表示即为D1A7H。

最后要指出的是，汉字的输入编码与汉字的机内码是不同范畴的概念。

不管采用什么样的编码输入法（例如拼音、五笔字型等）来输入一个汉字，其机内码都是相同的。

3.2 哈夫曼编码说明哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。

哈夫曼树─即最优二叉树，带权路径长度最小的二叉树, 是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

如下，我们建立一张相应文本原件进行Huffman树的建立和Huffman编码的表格1哈弗曼编码图1Huffman树示例3.3流程设计此压缩软件主要是依靠经典的Huffman算法实现，我们对文件进行压缩和进行压缩测试，然后将压缩的数据进行建立相对应的Huffman树建立进行解压，对解压文本与原始文本进行对比，无误算解压成功，经测试，压缩无误。

压缩算法的基本流程如图（图 2 压缩算法结构图）所示图2压缩算法结构图4、中文压缩算法的实现为了完善功能，实现较容易的扩展性，我们使用增量模型开发本项目，初期预计哈弗曼中文压缩算法一共分成四部分：●编码过程●解码过程●版本管理●帮助文档主要结构如图（图2压缩算法结构图）所示其中主要的部分是解码过程和编码过程。

4.1编码过程编码的主要流程如图（图3编码流程）所示图3编码流程压缩文件通过对文件的分析和设计，创建哈弗曼字典，再根据字典实现对应代码1 压缩算法实现说明：○1选择压缩功能○2统计字符频率○3创建字典，创建字典分为两步，先创建零散节点，再根据权重调整节点的位置，使之成为一颗标准的哈弗曼树○4回写字典信息：为了在解码过程中重建哈弗曼树，我们需要写入字典信息○5写文件4.1.1字符频率记录和全局存储对读入的文件进行频率测定，测定结果存入全局数组以便后来建立和Huffman树，对每一个字符的频率统计后放在一个相对应的Huffman节点中。

在本项目中，我们将任何的字符都拆分成一个字节为单位处理（双字节字符按照两个字节处理），这样，我们只需要创建28个全局字符数组用于统计字符的频率，按照每个字符对应的8位无符号数，进行相应的数量加1就会得到我们最终的字符频率4.1.2创建Huffman树利用Huffman节点的频率情况组建Huffman树，Huffman节点中有子节点和父节点之分，父节点是两个权重相对较小的子节点的和，其中不存在字符，只是为创建Huffman树而存在。

本项目中我们采用链表的结构进行哈弗曼的节点连接。

代码2 哈弗曼节点结构说明：○6调整内存对齐格式，32位程序上默认的是4字节对其，我们选择为单字节对齐，为方便后面对内存的直接初始化○7哈弗曼的节点信息，我们使用三链表结构，父指针，左指针和右指针分别指向父节点，左节点和右节点使得整个哈弗曼树节点进行连接○8当前节点的权重○9当前节点对应的字符，叶节点对应的是相应的字符，其他节点无意义，默认为0X0有了上述结构，我们就可以进行相关字符的调整和处理了。

包含单节点的建立，节点的调整。

4.1.3创建Huffman字典从建立的Huffman树的每个叶子往根节点找起，到根节点所经历的每个0或1字符的组合为相应叶子节点的字符编码(由于是倒序查找，要进行逆序组合)。

Huffman字典的流程如图（图4哈弗曼字典流程）所示图4哈弗曼字典流程有了前面创建的Huffman树，我们就可以比较容易实现字典的获取，我们采用的是从叶节点开始向上访问直到根节点，如果当前节点是父节点的左节点，便在字典中尾部粘贴0，否则粘贴0，这样当访问完全部的一条路径，便实现了一个字典的逆序，进一步可以得到字典的编码信息代码3 创建字典说明：○10从叶节点一直访问到根节点，计算一个字符的字典编码○11判断当前字符是根节点的左节点还是右节点○12反转得到的逆序编码，得到真正的编码4.1.4存入字典为方便我们实现解码过程，我们需要将字典信息写入压缩后的文件的首部，为方便区分字典和后续的编码信息，我们创建一个表，在文件的首部填写有效索引的个数（单位为字节，因为最多为28）再将字典按照表格的形式写入文件中，表格2填写字典的结构4.1.5存入文本在将每个字符新对应的编码进行重新组合，在此过程中药应注意到，由于我们在转化时为了方便时以0或1 的字符进行编码，而不是一个位的0或1进行编码，此时会先将8个0或1字符转化为1个ASCII字符，然后存入用户指定的文档中。

代码4 写文本说明：○13我们写入文本的单位是1字节，所以在写入文本之前要先将编码截取成字节为单位的编码○14由于哈弗曼编码的不定长性，我们最后一个有效编码不能保证为一字节，为此，我们要做位扩展○15帮助区分最后一个单位编码的有效位4.2解码过程在解码过程中，我们要恢复字典信息，再根据字典信息逆推出整个Huffman 树，从而得到解码的依据。

解码的流程如图（图5解码流程）所示图5解码流程为方便我们能够直观的了解字符的显示问题和验证恢复效果，我们直接将解码的信息打印到显示终端上。

整个解码过程的实现如代码（代码5 解码的实现）所示代码5 解码的实现说明：○16恢复字典信息○17恢复Huffman树○18解码4.2.1恢复Huffman树我们根据已经读取的Huffman字典逆推恢复Huffman树代码6 恢复Huffman树的实现说明：○19最多循环28个○20根据前文规定，左子树为0，又子树为1○21如果当前的节点为叶节点，说明此部分还没有建立完善，我们要创建桥梁节点，用于连接所有节点4.2.2解码利用建立好的Huffman树和读入的文本文件中的字符信息，每次解码过程都从树的顶点开始，每找到一个树的叶子节点就代表一个字符解析成功，此时注意由于我们是拆分的中文编码，所以此时当一个字符大ASCII码大于128时就代表一个中文字符出现，次字符将和接下来的字符组合代表一个中文字符。

验证解码是否成功：将源文档和解码出现的文档进行对比，验证是否压缩解压成功。

解码过程的主要流程如图（图6解码流程）所示图6解码流程解码实现如代码（代码7 解码实现）所示代码7 解码实现说明：○22中文的第一字节大于0XA0，依据此项作为判断○23中文字符存放在一个3字节的数组中，为方便显示，我们适当调整顺序○24到达文本的最后一个字符○25判断当前为0是指针移到左节点，为1时移到右节点○26如果一个字节处理完，加载下一个字节5、测试5.1 命令行打开测试我们编译完文件后，在命令行进行测试，打开编译后的exe文件如图（图7命令行打开测试）所示图7命令行打开测试命令行测试成功！能成功打开相应文件。