算法设计与分析概要VIP专享VIP免费

算法设计与分析姓名：胡存英班级：计算机应用学号：20070130324指导老师：彭小刚基于LZW算法的文本压缩摘要：介绍了LZW算法，用java语言实现了LZW文本压缩，并对其字典的节点结构进行了改进，减少了运行中的内存使用，提高了压缩解压速度。最后，对改进的算法和原来的算法在四个文本上进行测试，对比分析，实验表明，这一改进算法有一定的提高。关键词：文本压缩；LZW算法；字典；TextCompressionBasedonLZWAbstract:Inthispaper,werealizeLZWtextcompressionwithJAVA,andimproveitsnodestructureofdictionary.Asaresult,themodifiedalgorithmuseslessmemoryintheprocessofcompressionanddecompression,increasesthespeedofoperation.Intheend,wetestfourdifferenttextsusingalgorithmLZWandmodifiedalgorithmrespectively.ByComparisonAnalysis,theresultshowsthattheimprovedalgorithmresultinacertainimprovementinrunningspeed.[Keywords]:textcompression;LZWalgorithm;dictionary;一、引言随着计算机数据采集技术的发展，实验数据量由原来的几十Kbs发展到几百Mbs，甚至到Gbs量级。针对如此大量的测试数据的传输、存储问题，必须对大量的数据进行压缩。但数据压缩技术在各方面应用时,采用哪种压缩方法,要根据信号类型和应用目的不同等具体需要而定。本文通过分析当今普遍使用的压缩算法后，介绍LZW压缩技术的算法思想,并分析了LZW压缩技术的特点,利用java编程实现了改进得LZW文本数据压缩。最后，对该方法进行了测试。二、压缩算法—LZW算法1.LZW的基本原理LZW编码器采用一种很实用的分析算法，称为贪婪分析算法。在贪婪分析算法中，每一次分析都要检查来自字符流的字符串，从中分解出已经识别的最长的字符串，也就是已经在字典中出现的最长的前缀。用已知的前缀加上下一个输入字符C也就是当前字符作为该前缀的扩展字符，形成新的扩展字符串——缀-符串。这个新的缀-符串是否要加到字典中，还要看字典中是否存有和它相同的缀-符串。如果有，那么这个缀-符串就变成前缀，继续输入新的字符，否则就把这个缀-符串写到字典中生成一个新的前缀，并给一个代码。2.LZW算法编码原理：首先把字母表中的所有字符初始化到字典中，常见的是8位字符，即把字典的前256项初始化为ASCII码。编码器逐个输入字符并累积成一个字符串I,每输入一个字符就被串接在I后面，然后在字典中查找I,只要在字典中找到I,该过程就继续进行。直到在某一点，添加下一个字符X导致搜索失败；字符串I在字典中，而IX却不在，这时编码器：（1）输出指向字符串I的字典指针；（2）在下一个可用的字典词条中，存储字符串IX；（3）把字符串I预置为X。解码原理：解码器和编码器采用同样的方式建立字典。解码器首先把字典的前256项初始化为字母表中的所有字符（256标准字符）；然后读取输入流（流中含有指向字典的指针），用指针从自己的字典中取回为压缩的字符写入输出流中。在解码的第一步，解码器输入第一个指针并用其取回一个字典词条I。这是一个字符串，被写进解码器的输出流中。需要把符号串IX保存在字典中，它将是下一个从字典中读取的字符串的第一个字符。在其后的每一个解码步骤中，解码器输入下一个指针，从字典中取回下一个字符串J,并把它写进输出流中，同时抽出第一个字符X，并把IX存入下一个可用的字典项中（必须先确认IX不在字典中），然后解码器把I预置为J，可以开始下一步解码。3.字典结构从上面的编码和解码过程中，可以看到：添加到字典中去的每个字符串仅仅有效的增加了一个新字符X,即对每个不止一个字符的字符串，字典中有一个之比它短一个字符的“母串”，采用树的结构，加进字符串IX只需增加一个X的节点。树的数据结构应该设计成一个节点可以拥有任意个子节点，但无需为其余留任何存储器。一种方法是把树驻留在一个节点数组中，每个数据结构有两个字段：一个字符和一个指向母节点的指针。一个节点没有任何指向其子节点的指针。沿着树从一个节点下行到它的一个子节点，可用一个散列过程实现，该过程把指向节点的指针和子节点的字符散列以生成一个新指针。假设串abc已逐字符输入并分别存储在树的3个节点...