医软11大三第一学期第一章参考格式

1、实践与经验树的实现及其在文件压缩中的应用姜龙 2丁光辉 21，2（1. 西南科技大学计算机学院，绵阳 621010； 2. 西南科技大学，绵阳 621010）要： 在信息快速传输和的过程中，数据压缩有着非常重要的作用。 介绍了基于树摘的文本压缩和解压缩的原理与方法，现过程。编码； 文本压缩； 压缩算法并给出了 Huffman 压缩与解压程序算法的实：引 言在数据结构实践课程中，通常会遇到让学生利用编码进行文本压缩和解压缩这样的课题。由于个结构体 Infchar ch；ratio；，取 Inf 中的频率信息0ratio 后，再去查看字符 ch 是哪一个。 这样做的好处是节约了内存，且在后面的压缩

2、中，它也减小了输入文件的大小。因为任意文件实际都是二进制编码的，所以对选定的任意文件以二进制方式读入，一次读入一定的长度，例如 4096 bytes，然后对每一字节进行统计，如此循换，统计出文件中各个字符的频率，以这些频率作上只是给出了树的定义和编码， 因此，很多学生在完成这个课题的时候感觉无从下手。本文将给出利用树进行文本压缩和解压缩的具体实现过程，以供参考。构造要利用树编码对文本文件进行压缩，首先必1为权值，构造树。树结构采构造1.2树的亲孩子表示法，即利树需要的空间为的叶子结点个须知道其字符相应的编码。为了得到文本中字用结构体数组来实现。 一颗2LeafNode-1，其中 LeafNod

3、e 是符出现的频率， 一般的做法是扫描整个文本进行统计，编写程序统计文本中各个字符出现的频率。由于数。给先初始化树，即将上述统计的字符信息赋一个字符的范围在0-255之间，即共有 256 个状态，所以直接向系统静态的申请一个长度为 256 的整数数组，用于存放相应的频率。得到频率后，进行编码，然后将数据输出到文件保存。树的叶子结点，然后循环提取树中权值最小的两个根结点，将它们合并起来，组成一个新的根结点， 直到最后止。树只剩下一个根结点为统计字符信息首先定义一个存放字符频率信息的整数数组 Ar ray。 本文采用了一种默认方案， 即数组中第 N 个数据所对应的就正好是 ASCII 编码为 N

4、的字符频率。如表 1 所示。表 1 字符频率表1.1构建树时， 直接调用堆进行数据筛选，首先查看类 HeapNode，它是一个堆结点类。 在类中，定义了 3 个元素，sum weight（总权值）、sum leaf(此结点现代计算机（总第二九五期）的叶子结点的总数)、本结点在树ition（中的具置）。定义了 3 个重载函数，即按照多关键字规则，给结点一个大小关系，使得后面的程序可以直接对此类进行比较大小。获得编码1.3当使用到 ArrayN这个数组时，就知道它一定是ASCII 编码为 N 这个字符的频率，而无需再去定义一定义一个 HaffCodes 类数组并对其进行初始化。收稿日期：2008作

5、者简介：07 03 修稿日期：2008 10 30（1977 ），绵阳人，讲师，研究方向为图形图像处理技术、算法分析趽趬M O D E R N C OM P U T E R 200811 实践与经验要处理的关键问题是应该给字符编码一个多长的数组， 因为预先不知道字符的最长编码应该是多少，如果只是简单的选择 256 个，太浪费空间，所以最好的/ 将叶子结点的权值存入压缩文件for (x=0; xm iNumOfNode; x+)itoHaffmanTreex.weight, pChar, 10); /将权值转化为 char 型方法是实时计算树的深度，以深度为字符的最长编码长度。 得到存放编码空间

6、后，需要对其每个位z += ( ) strlehar) + 1;置填充字符/0。规定在树中，左分支为 0，右for (w = 0; yz 1; y+)Stringy = pCharw+;Stringz 1 = ; /每个数据用空格隔开y = z;分支为 1，从叶子结点出发，到根结点为止，即到相应字符的编码。压缩文件计算出每个字符的2编码后，即可对应文本文件进行编码，这里就不再详细叙述。上述方法中，每个“0”或“1”实际上占用了一个字节的空间，只起到示意或模拟的作用，如果不进行处理，利用上述方法对文本文件进行压缩，压缩后文件反而更大，根本没有起到真正的压缩作用。下面介绍如何把编码转为真正的二进制

7、，进行真正的文本压缩。先从文件中一次读入一定长度如 4096 bytes，然后对每一字符逐一处理。 读到一个字符，则找出它的编码，将字符编码不够 8 bit 的，读入下一个字符，找其编码，取其适当的位补齐前面不够 8 bit 的编码，然后转换为对应 ASCII 码字符， 然后写入这个字符，超过 8 bit 就分开，写入后继续处理后面的字符。 举例如下：已知：a: 1010 b: 00 c: 10000 d: 1001 e: 11 f:10001 g: 01 h: 1001如果文件中的一段是 “acdef”， 则处理如表 2 所示。outfile.write(String, ( ) strlen

8、(String); /将权值写入 index;char bufferBUFFERLENGTH; string compleCode = ;string binaryStrCode = ; /二进制代码value;/计算 8bits 的 char 值 ( 与 unsigned char区分)char ch; doinfile.read(buffer, BUFFERLENGTH); /以 二 进 制 形 式 读入 BUFFERLENGTH 个字符/将上次循环的补码赋binaryStrCode = compleCode;给 binaryStrCodecompleCode = ;for (i=0; i

9、infile.gcount(); i+)表 2编码处理/buffer 数组不是 unsigned charif (bufferi 0)类型index = 127bufferi;elseindex = bufferi; j = MAXCODECODE 22;如上述， 这样就把编码按真正的二进制编码处理，把 5 个字符压为 3 个字符，这里还应该注意，当读文件到达文件尾时， 一般不能刚好凑够 8 bit 所以需m iHaffmanCode index MAX现代计算机（总第二九五期）for (; jMAXCODE 2; j+)if (m iHaffmanCodeindexj = 0) binary

10、S trCode.append(0);else binaryStrCode.append(1);strLength = ( ) (binaryStrCength() / 8);/有多少个整 8要补上“0”直到够 8 bit。 而补上的 0 的个数为补位数。 压缩文件开头存放补码的信息，接着存放权值以及空格字符的长度，长度后存一个空格，其后存每个叶子结点的权值本压缩的代码段。void权值之间用空格隔开下面是文，。prepressText(CString pCompressTextName)compleSize = ( ) (binaryStrC/本次循环的补码ength() % 8);貋貖財MO

11、 DE RN C OMP U T ER 200811 实践与经验函数转换为 8 个字符（用一个数组一个“0”或一个“1”），然后按，其元素只是树从顶向下查找，for (k=0; k=k; l)if (binaryStrCode.at(l) = 1)value +=实验结果与分析图 1 是利用本文方法对文本文件进行压缩的例子，图 2 是对压缩后的文件进行解压。 实验结果表明，本文方法能够正确处理 doc 文件、tex 文件、exe 文件等，并且有较高的压缩率，其中对 doc 文件的压缩率在 70%左右。4( )(2, k+7 l);/将其 if (value 127) ch =放入压缩文本里面e

12、lse ch = value;127value;outfile.ph);/计 算 压 缩 文m iCompressedTextSize+;件的大小/处理补码size = 8 * strLength; if (size =0; n )if (compleCode.at(n) = 1) value += ()(2, 7 n); if (value 127) ch = 127value;elsech = value;图 2解压结果现代计算机（总第二九五期）结 语5编码是数据压缩领域中最著名的编码方式之一，它通过对象频率出现的不等性，构造最优编解压文件有了上述压缩文件3信息的基础，自然能方便码，达到减

13、小文件大小的目的。目前广泛应用的许多地解压出原来的文件。读出结点数就知道树存其他高效的数据压缩算法（例如算术编码、可编码等）也是在编码的基础上发展起来的，所以， 对于深入理解数据结构、程入部分的总长，方便读出树树（子结点值和权研究编码的值），就能由这些信息重新构造完整的树，和各序设计等学科中的相关课题是十分有益的。个结点的编码。解压时，一个字节，用一个貋貖貢MODE RN C OM PUTE R 200811实践与经验参考文献:技大学3, 2003. 数据结构课程设计案例精编M. 数据结构M.1, 2003M. 陕西:西安电子科:2高一凡. 数据结构算法实现及, 2007Implement o

14、f Huffman Tree and Its Application in FileCompresCAI Mao rong1 ,JIANG Long2, DING Guang hui2 ,Wen hui2（1. Computer Academy，Southwest University of Science and Technology, Mian2. Software Engineering，Southwest University of Science and Technology, Mian621010；621010）Abstract： It is very important to c

15、ompress datahe ratransmisandand storage of information.roduthe principle and method aboomprespresof text based onHuffman tree and presents the implement course of the core algorithm of a Huffman compresandpresprogram.Keywords： Huffman Coding； Text Compres； CompresAlgorithm!（上接第 82 页）参考文献Michelineber

16、 著. 数据挖掘概念与技术机工程与应用,2004,22:177, 刘卫国. 数据挖掘中关联规则挖掘算法比较研1Jiawei Han4译.,，2005：机械工业究J. 计算机工程与设计,2005,5:1265M.,，20052毛国君,华大学. 数据挖掘原理与算法M.：清. 关联规则挖掘综述J. 计算机5,工程,2001,5:31, 尹关联规则的改进算法J. 计算3,.The Improvement of Apriori Algorithm and ItsApplicationerce现代计算机（总第二九五期）XU Xue fei，QING Peng tao（Computer Center of Nanchang University, Nanchang 330031）Abstract： Proes a methodt gives the weight on the element of itemset, during compute the support of the itemset (commodities) and at the same t