动态文本的解压缩算法设计与实现

王　军

（铜仁学院 信息工程学院，贵州 铜仁 554300 ）

动态文本的解压缩算法设计与实现

王军

（铜仁学院 信息工程学院，贵州 铜仁 554300 ）

针对在文本解压缩过程中对动态数据进行权重统计较为困难这一问题，提出了一种采用三叉链表的解压缩算法。首先采用链表对动态文本中的不同字符进行统计，得到相应字符的权重；在此基础上，再利用三叉链表构造赫夫曼树并对其进行赫夫曼编码；最后采用位运算对赫夫曼编码进行无损的数据压缩和解压。实验表明，该算法运行效率高，实现简单，具有较高的应用价值。

文本；动态数据；三叉树；解压缩

1.引言

作为一种可变字长编码方式，赫夫曼编码可对文本数据进行压缩和解压。然而构造赫夫曼树的权重是已知的，如何对动态数据进行权重的统计是解决文本压缩和解压的关键问题。众所周知，赫夫曼编码是最优的无损编码。对此，文献［1］介绍了动态字符权重的统计方法并且证明了赫夫曼编码的带权路径长度是最短的，利用它对数据进行压缩的效率是很高的。但该方法并未提出如何统计汉字的权重。因为一个汉字在内存中占两个字符，对汉字的统计比较困难。文献［2-4］中赫夫曼树的逻辑结构是用三叉链表来实现，而赫夫曼树的存储结构又是用顺序结构来实现的。为便于理解，在本文中我们采用单链表实现权重的统计，用三叉链表作为赫夫曼树的逻辑结构和存储结构。在上述基础上，根据文献［2-4］的分析，我们进一步实现了针对动态文本（包括汉字）的赫夫曼编码，最终达到了实现无损解压缩的目的。

2.解缩算法的设计思路

2.1.采用单链表实现对文本中的字符进行统计

（1）设计单链表：如图1所示。

图1　统计字符权值

在图1中，h指针指向的结点为头结点，当没有数据进行统计时，h-＞next域为空。这就是单链表的初始状态。结点中的n数据域是用来统计data域中字符的个数，data域用来存放字符，不同结点的data域的字符是不同的。Next域是用来存储下一个结点的地址。文本串中的每一个字符从上到下与单链表中的data域中的字符进行比较，若与某个结点的data域的字符相同，则该结点的n域加1，该字符统计完成，接着统计文本串中的下一个字符。若单链表中的所有结点的data域中都不与正在统计的字符相同，则在最后一个结点的后面插入一个新结点，新结点的data域就是该字符，next域为空，n域为1。重复上述操作，直到文本串中的所有字符统计完成为止。

（2）字符的统计：关键是结点中data域的设计，data域的结构设计为图2所示。

图2　data域的结构

图2中ch0，ch1，ch2都是字符型变量，在读取文本数据时必须按字节读取。若正在统计的数据的ASCII值大于0，说明该字符是英文字符，则字符存入在data域的ch0中；若正在统计的数据的ASCII小于0，说明所统计的字符为汉字或者是中文的标点符号，这时连续读两次，第一次读的字节存入在data 的ch1中，第二次读的字节存入data的ch2中，由ch1、ch2两个字节存放一个汉字。同样在进行数据统计时，若正在统计的数据的 ASCII大于 0，则与data域中的ch0比较，反之则与data域中的ch1，ch2比较。这是统计汉字的关键因素，也是文本压缩统计权重的核心问题。

（3）收集每个数据的权重：从头结点的下一个结点开始，分别从每一个结点中的data域和n域读取相应的数据，n域的值就是相应结点的data域中的数据的权重，直到单链表中的所有结点收集完成为止。这样文本中的所有不同字符的权重都统计完成。

2.2.三叉链表的生成

（1）将统计的字符有权重生成一个带头结点的单链表，如图3所示，其中D域用来存放统计的字符，W 域用来存放对应字符的权重，指针域又包含四个指针，一个指针指向后继，一个指针双亲，一个指针指向左孩子，一个指针指向右孩子。

（2）按照赫夫曼树的构造方法［2］，在H单链表中查找当前权重最小的两个结点，将这两个结点作为一个新结点的左、右孩子，新结点的权重为这两个结点的权重的和。这两个结点的双亲指针分别指向新结点，从单链表中删除这两结点，把新结点插入到H链表的表头后面，重复上述操作，直到H链表为单链表只有一个结点为止。此时，H链表中的第一个结点就是三叉链表的根结点。

图3　三叉链表

2.3.赫夫曼编码和压缩

为了能快速找到三叉链表中的每一个结点，用一个向量来存放三叉链表的叶子结点的地址。在2.2中的单链表生成时把每个结点的地址存放在一维向量中，从一维向量中分别取出每个叶子结点的地址，从叶子到根进行遍历，按规定的顺序得到相应的赫夫曼编码，再设计位运算算法把每个编码按位压缩，直到文本中的所有字符都按位压缩得到一个新的文件，从而完成了数据压缩过程。

2.4.解压缩方法的设计

解压算法可通过对上述位运算进行逆操作实现。从压缩文件中顺序读取二进制位，按规定的顺序从根到叶子进行搜索，搜索过程中左孩子或右孩子为空时的结点的D域的字符就是解压后需要的字符，再输出该字符。反复从根到叶子进行搜索，直到把压缩文件的每一个二进制位译码完成为止，从而完成了解压操作。

3.数据结构的设计

4.算法的实现流程

本文算法的的N-S流程图如图4所示。在该图中详细描述了数据压缩和解压的过程。

此外，各函数的原型如下：

（1）void Huffman：：InputFile（）//向文件中输入文本文件

（2）void Huffman：：OutputFile（）//输出文件

（3）void Huffman：：CountCharNum（）//创建动态链表来统计字符的权重

（4）void Huffman：：CreateTree（）//利用单链表创建三叉链表

（5）void Huffman：：code（）//利用三叉链表对各种字符进行赫夫曼编码

（6）void Huffman：：yasuo（）//压缩编码

（7）void Huffman：：jieya（）//解压编码

本文方法已在VC6.0中编译运行（源代码见附件），经过实际运行，可实现对动态文本的无损解压缩操作。

图4　算法的N-S流程图

5.总结

本文设计并实现了一个针对动态文本的解压缩算法。该算法具有如下特点：（1）利用文件指针对源文件和压缩文件的读写［5］，避免了反复输入数据；（2）算法中所使用的数据结构全是链表或动态数组，保证了文本文件的长度不受限制；（3）通过位运算得到二进制串的长度正好是赫夫曼编码中的带权路径长度，而且该编码长度是最短的，所需要的字节数最少，达到了高效压缩的目的。本算法的不足之处在于，目前只能对文本进行解压缩，无法对图形、图片、视频、声音、动画等数据进行处理，下一步拟对这个问题展开研究。

［1］王军.基于赫夫曼编码的数据压缩［J］.中国教育教学杂志，2006，18（11）：16765-16767.

［2］严蔚敏.数据结构［M］.北京：清华大学出版社，2010.

［3］陈宝平.数据结构［M］.北京：清华大学出版社，2012.

［4］邓又明.数据结构［M］.北京：地质出版社，2007.

［5］谭浩强.C程序设计（第三版）［M］.北京：清华大学出版社，2014.

［6］郑丽.C++语言程序设计（第四版）［M］.北京：清华大学出版社，2010.

The Design and Implementation of Compression and Decompression Method for Dynamic Text

WANG Jun
（School of Information Engineering，Tongren University，Tongren，Guizhou 554300，China ）

Due to the difficulty of weight statistic for dynamical data in the compression and decompression process，a compression and decompression method based on trifurcate chain table is proposed in this paper. First，in order to achieve the weight of each character，each different character in dynamical text file was accounted by employing chain table. Then the Huffman tree was constructed and Huffman coding was completed by using trifurcate chain table. Finally，the lossless compression and decompression for Huffman coding was completed by using bit- operation. Experience results reveal that the proposed method has a high application value for the advantages of high efficiency and realized easily in practice.

Text；dynamical data；ternary tree；compression and decompression

TP311.51

A

1673-9639 （2015） 04-0117-03

（责任编辑 毛志）（责任校对 徐松金）（英文编辑 田兴斌）

2015-06-05

本文系贵州省教育厅教学质量与教学改革工程项目（黔高教发［2013］446-9号）研究成果。

王军（1967-），男，贵州德江人，副教授，研究方向：算法与计算机应用技术。