算法设计与分析

1、算法设计与分析姓名：胡存英班级：计算机应用学号：20070130324指导老师：彭小刚基于LZW算法的文本压缩摘要：介绍了LZW算法，用java语言实现了LZW文本压缩，并对其字典的节点结构进行了改进，减少了运行中的内存使用，提高了压缩解压速度。最后，对改进的算法和原来的算法在四个文本上进行测试，对比分析，实验表明，这一改进算法有一定的提高。关键词：文本压缩；LZW算法；字典； Text Compression Based on LZWAbstract: In this paper, we realize LZW text compression with JAVA, and improve

2、its node structure of dictionary. As a result, the modified algorithm uses less memory in the process of compression and decompression, increases the speed of operation. In the end, we test four different texts using algorithm LZW and modified algorithm respectively. By Comparison Analysis, the resu

3、lt shows that the improved algorithm result in a certain improvement in running speed. Keywords : text compression; LZW algorithm; dictionary;一、引 言 随着计算机数据采集技术的发展，实验数据量由原来的几十Kbs 发展到几百Mbs，甚至到Gbs 量级。针对如此大量的测试数据的传输、存储问题，必须对大量的数据进行压缩。但数据压缩技术在各方面应用时,采用哪种压缩方法,要根据信号类型和应用目的不同等具体需要而定。本文通过分析当今普遍使用的压缩算法后，介绍LZW

4、 压缩技术的算法思想, 并分析了LZW压缩技术的特点,利用java编程实现了改进得LZW 文本数据压缩。最后，对该方法进行了测试。二、压缩算法LZW算法1.LZW的基本原理LZW 编码器采用一种很实用的分析算法，称为贪婪分析算法。在贪婪分析算法中，每一次分析都要检查来自字符流的字符串，从中分解出已经识别的最长的字符串，也就是已经在字典中出现的最长的前缀。用已知的前缀加上下一个输入字符C 也就是当前字符作为该前缀的扩展字符，形成新的扩展字符串缀-符串。这个新的缀-符串是否要加到字典中，还要看字典中是否存有和它相同的缀-符串。如果有，那么这个缀-符串就变成前缀，继续输入新的字符，否则就把这个缀-符

5、串写到字典中生成一个新的前缀，并给一个代码。2.LZW算法编码原理：首先把字母表中的所有字符初始化到字典中，常见的是8位字符，即把字典的前256项初始化为ASCII码。编码器逐个输入字符并累积成一个字符串I,每输入一个字符就被串接在I后面，然后在字典中查找I,只要在字典中找到I,该过程就继续进行。直到在某一点，添加下一个字符X导致搜索失败；字符串I在字典中，而IX却不在，这时编码器：（1）输出指向字符串I的字典指针；（2）在下一个可用的字典词条中，存储字符串IX；（3）把字符串I预置为X。解码原理：解码器和编码器采用同样的方式建立字典。解码器首先把字典的前256项初始化为字母表中的所有字符（2

6、56标准字符）；然后读取输入流（流中含有指向字典的指针），用指针从自己的字典中取回为压缩的字符写入输出流中。在解码的第一步，解码器输入第一个指针并用其取回一个字典词条I。这是一个字符串，被写进解码器的输出流中。需要把符号串IX保存在字典中，它将是下一个从字典中读取的字符串的第一个字符。在其后的每一个解码步骤中，解码器输入下一个指针，从字典中取回下一个字符串J,并把它写进输出流中，同时抽出第一个字符X，并把IX存入下一个可用的字典项中（必须先确认IX不在字典中），然后解码器把I预置为J，可以开始下一步解码。3.字典结构从上面的编码和解码过程中，可以看到：添加到字典中去的每个字符串仅仅有效的增加了

7、一个新字符X,即对每个不止一个字符的字符串，字典中有一个之比它短一个字符的“母串”，采用树的结构，加进字符串IX只需增加一个X的节点。树的数据结构应该设计成一个节点可以拥有任意个子节点，但无需为其余留任何存储器。一种方法是把树驻留在一个节点数组中，每个数据结构有两个字段：一个字符和一个指向母节点的指针。一个节点没有任何指向其子节点的指针。沿着树从一个节点下行到它的一个子节点，可用一个散列过程实现，该过程把指向节点的指针和子节点的字符散列以生成一个新指针。假设串abc已逐字符输入并分别存储在树的3个节点中，其位置为97、266和284。接下来，编码器只输入下一个字符d，并开始搜索串abcd，或者

8、，更准确地说，搜索一个含有字符d的节点，其母节点的位置是284。编码器把284（指向串abc的指针）和100（d的ASCII码）散列，产生一个指向某个节点的（比如299）指针，然后检查节点299，有三种可能：1该节点没有用过，即字符串abcd还不在字典中，需要加进去。编码器把母指针（284）和ASCII码100存储在该节点中，就把它加进了树中，结果如下： 节点 地址 97 266 284 299 内容 （-：“a”） (97:“b”) (266:“c”) (284:“d”) 表示 “a” “b” “c” “d”2该节点包含284的母指针和d的ASCII码，即字符串abcd已经在树中。编码器就输

9、入下一个字符，比如为e，并在字典树中搜索字符串abcde。3该节点包含其他内容，既有另一个散列（一个指针和一个ASCII码）指向了299，产生“冲突”，最简单的处理冲突的方法是使指针299增加而检查节点300，301，直到找到一个没用过的节点，或找到含有（284：“d”）的节点为止。字典的节点是一个3字段的结构：指向母节点的指针；有散列过程生成的指针（或索引），该节点所含字符的编码（标准ASCII码）。由于有冲突，故第二个字段不能省略。字典的节点结构图1如下：母节点（parent）索引(index)字符（symbol）图1 字典的节点结构因为字典的前256项一开始就被占用了，因此字典的指针必须

10、长于8位，在这里采用16位指针，字典可有64K-65536个词条。但是，这个字典很快就会填满，除非压缩任务极小。如果字典填满了，必须采取相应的措施，或者把最近最少用到的字典短语删掉，或者重新建立字典，我们采用后者。4.哈希函数4.1 哈希函数的构造如果对于函数 y=f(x)以如下特性: x 的值域很大,而y 的值域很小,当 x1 不等于x2时,f(x1)不等于f(x2)的概率很大,这时,f(x) 就称为哈希函数。哈希函数主要用于数据查找。查找的问题描述是：给定一个序列：<x1,x2,.,xi,.xn>，再给定一个数 y，求这样的 i，使得 xi 等于 y. 哈希函数可把原始序列分组

11、，具有相同哈希值的元素在同一个组里3。查找之前，先求 y 的哈希值，然后在这个值的组里找 xi，查找范围小了，速度得以提高。 一个优质哈希函数可以成百倍地提高查找速度。 构造哈希函数的方法很多。若对于关键字集合中的任一个关键字，经哈希函数映象到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的(Uniform)哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。4.2 处理冲突的方法对不同的关键字可能得到同一哈希地址，即Kl!=K2，而f(Kl)=f(K2)，这种现象称冲突。均匀的哈希函数可以减少冲突

12、，但是不能避免。假设哈希表的地址集为0(n-1)，冲突是指由关键字得到的哈希地址为j(0jn-1)的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列Hi ,i=1，2，k，i0,n-1)。即在处理哈希地址的冲突时，若得到的另一个哈希地址H1 仍然发生冲突，则再求下一个地址H2，若H2 仍然冲突，再求得H3。依次类推，直至Hk 不发生冲突为止，则Hk 为记录在表中的地址。通常用的处理冲突的方法有下列几种：开放定址法；再哈希法；链地址法；建立公益区法。4.3 哈希查找给定K 值，根据造表时设定的哈希函数求得哈希地址，若表中此位置

13、上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一地址”，直至哈希表中某个位置为空，或者表中所填记录的关键字等于给定值时为止。在LZW文本压缩中，其中主要的操作为在字典中查找是否存在当前的字符串。字典数组有6553个字典项，查找到某个字符串是否存在以及将未出现的字符串加入到字典中，需要一个效率高的查找方法。这就要求所用到的哈希函数能够尽可能的分布均匀，避免冲突，减少查找的次数。本文中采用以下函数：index =(numx<<8)(numparent)其中，numx为当前的输入字符X的对应的整数值，numparent为当前

14、的串I（未加入X）的编码。当出现冲突时，使指针逐渐加一来解决。三、改进的LZW算法在对字典进行查找时，如果其索引为未使用，则表明该节点为未被使用；如果该节点的索引值等于哈希函数值，则字符串在字典中存在。所以字典节点的第二个字段index的作用有两个：一是表征给节点是否被使用过，二是检查是否存在冲突。我们可以去掉第二个字段，将其作用用parent和symbol字段来实现，改进后的字典节点结构为图2：字段数值类型母节点（parent）int字符（symbol）char图2 改进的节点结构我们用parent=65537,表示该节点存储的字符为基本的前256个ASCII码，用式子parent=6553

15、8是否成立,表示该节点是否为已经用过的节点。编码过程如下：Compress() 将所有ASCII插入到字典中，对字典进行初始化； 将I初始化为输入的第一个字母的指针；while 还有输入尚未处理hashcode=Hash(I,x)；While(hashcode.parent!=65538)| !（hashcode.symbol=x |hashcode.parent=I）； If 哈希值节点的parent=65538 将I.parent + I.symbpol l插入到字典中该节点； 将I.parent输出； I.parent置为I.symbol对应的值；Else 输入下一个字符；I置为该节点对

16、应的指针；输出输出流即为压缩后的文本。解码也创建一个相同的字典，其过程相似。解码器首先初始化字典，然后从输入流中读取指针，用每个指针来定位字典中的一个字符。利用parent字段返回树的上层，并按相反的顺序取出字符串中的单个字符，再按正常的顺序，把得到的字符串记录到输出流中。此外，还有将当前字符串的第一个字符与上一个字符串添加到字典中。可见，在解码时，查找字符串无需任何散列，只在添加到字典时，才需要哈希函数定位添加的位置，所以，解码所需的时间一般比压缩时间短。解码过程如下：Decompress() 将所有字母输入到表中； 读入第一个指针I并输出其对应的字符； While 仍有编码字未处理 读入下

17、一个指针J If J对应的字符串在字典中不存在，即该节点为使用 输出I到输出流 将I+firstchar(I)插入到字典的J节点 Else 输出J对应的字符串 将I+firstchar(J对应的字符串)插入到字典中 输出输出流得到原始的文本四、实验结果Canterbury全集是典型用于测试数据压缩程序的一组18个文件，从中选择4个大小不同的文本文件对改进的算法进行测试，测试其压缩率,其性能如下： 文件原始大小压缩大小压缩率Alice.txt141K55.0K60.99%Obj1.txt852K467K45.11%Obj.txt1.31M613K54.47%Bible.txt3.86M1.53M

18、60.14%表1 不同文本的压缩性能表改进的算法，压缩率不变，均高于45%，特别是对于较大的，相关性较强的文件压缩率更高。然后用原来的LZW算法进行测试，对他们的运行时间和内存使用进行对比，其结果如下表：算法文件Alice.txtObj1.txtObj.txtBible.txtLZW压缩时间0.110ms7.859ms11.547ms34.094ms内存使用4.879M8.297M13.172M30.652M改进LZW算法压缩时间0.078ms6.985ms10.500ms33.109ms内存时间3.394M7.398M12.277M29.691M表2 运行时间和内存使用对比表从上表中，可以看出，内存的使用率减少了将近1M，压缩时间也减少了大约1s,特别是对于相关性小的文本，其字典需要不断的更新，所以缩短的时间更多。五、总结LZW算法是一种压缩率较高的无损压缩算法，我们针对其字典结构进行了改进，有效的利用了多余的空间，避免了内存空间浪费。最后将改进的算法与原始的LZW算法进行了比较，实验表明改进的算法缩短了压缩的时间，压缩率并保持不变。但是本程序压缩的时间还是比其他的