算法设计与分析概要

《算法设计与分析概要》由会员分享，可在线阅读，更多相关《算法设计与分析概要（8页珍藏版）》请在金锄头文库上搜索。

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

2、A, and improve 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 Anal

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

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

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

6、X。解码原理：解码器和编码器采用同样的方式建立字典。 解码器首先把字典的 前256项初始化为字母表中的所有字符（ 256标准字符）；然后读取输入流（流中 含有指向字典的指针） ，用指针从自己的字典中取回为压缩的字符写入输出流中。在解码的第一步，解码器输入第一个指针并用其取回一个字典词条 I 。这是 一个字符串，被写进解码器的输出流中。需要把符号串IX保存在字典中，它将是 下一个从字典中读取的字符串的第一个字符。 在其后的每一个解码步骤中， 解码 器输入下一个指针， 从字典中取回下一个字符串 J, 并把它写进输出流中， 同时抽 出第一个字符X,并把IX存入下一个可用的字典项中（必须先确认IX不在

7、字典中）， 然后解码器把I预置为J,可以开始下一步解码。3. 字典结构从上面的编码和解码过程中，可以看到：添加到字典中去的每个字符串仅仅 有效的增加了一个新字符X,即对每个不止一个字符的字符串，字典中有一个之比 它短一个字符的“母串”，采用树的结构，加进字符串IX只需增加一个X的节点。 树的数据结构应该设计成一个节点可以拥有任意个子节点，但无需为其余留任何 存储器。一种方法是把树驻留在一个节点数组中，每个数据结构有两个字段：一 个字符和一个指向母节点的指针。一个节点没有任何指向其子节点的指针。沿着 树从一个节点下行到它的一个子节点，可用一个散列过程实现，该过程把指向节 点的指针和子节点的字符散

8、列以生成一个新指针。假设串abc已逐字符输入并分别存储在树的3个节点中，其位置为97、266和 284。接下来，编码器只输入下一个字符d，并开始搜索串abcd，或者，更准确地 说，搜索一个含有字符d的节点，其母节点的位置是284。编码器把284 （指向串 abc的指针）和100（d的ASCII码）散列，产生一个指向某个节点的（比如 299） 指针，然后检查节点299,有三种可能：1该节点没有用过，即字符串abcd还不在字典中，需要加进去。编码器把 母指针（284）和ASCII码100存储在该节点中，就把它加进了树中，结果如下：节点地址 97266284299内容 （-：“ a”） （97: “

9、b” ） （266:“c” ） （284:“d”）表示abcd2该节点包含284的母指针和d的ASCII码，即字符串abcd已经在树中。编码 器就输入下一个字符，比如为e，并在字典树中搜索字符串abcde。3该节点包含其他内容，既有另一个散列（一个指针和一个 ASCII码）指向 了 299,产生“冲突”，最简单的处理冲突的方法是使指针299增加而检查节点300, 301， ，直到找到一个没用过的节点，或找到含有（284:“ d”）的节点为 止。字典的节点是一个3字段的结构：指向母节点的指针；有散列过程生成的指 针（或索引），该节点所含字符的编码（标准 ASCII码）。由于有冲突，故第二 个字段

10、不能省略。字典的节点结构图1如下：母节点（pare nt ）索引（index）字符（symbol）图1字典的节点结构因为字典的前256项一开始就被占用了，因此字典的指针必须长于8位，在这 里采用16位指针，字典可有64K-65536个词条。但是，这个字典很快就会填满， 除非压缩任务极小。 如果字典填满了， 必须采取相应的措施， 或者把最近最少用 到的字典短语删掉，或者重新建立字典，我们采用后者。4. 哈希函数4.1 哈希函数的构造如果对于函数y=f(x)以如下特性：x的值域很大,而y的值域很小,当x1 不等于x2时,f(x1)不等于f(x2)的概率很大,这时,f(x) 就称为哈希函数。哈希函

11、数 主 要 用 于 数 据 查 找 。 查 找 的 问 题 描 述 是 ： 给 定 一 个 序 列 ： ，再给定一个数 y ，求这样的 i ，使得 xi 等于 y. 哈希函数可把原始序列分组，具有相同哈希值的元素在同一个组里 3 。查找之前， 先求 y 的哈希值，然后在这个值的组里找 xi ，查找范围小了，速度得以提高。 一个优质哈希函数可以成百倍地提高查找速度。构造哈希函数的方法很多。 若对于关键字集合中的任一个关键字， 经哈希函 数映象到地址集合中任何一个地址的概率是相等的， 则称此类哈希函数为均匀的 (Uniform) 哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的 地址”

12、 ，以便使一组关键字的哈希地址均匀分布在整个地址区间中， 从而减少冲 突。4.2 处理冲突的方法对不同的关键字可能得到同一哈希地址，即 KI!=K2，而f(Kl)=f(K2)，这种 现象称冲突。 均匀的哈希函数可以减少冲突， 但是不能避免。 假设哈希表的地址 集为0(n-1)，冲突是指由关键字得到的哈希地址为j(0 j n-1)的位置上已存 有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列 Hi ,i=1，2,，k，i 0,n-1)。即在处理哈希地址的冲突时，若得到的另一个哈希地址 H1 仍然发生冲突，则再 求下一个地址H2,若H2仍

13、然冲突，再求得H3o依次类推，直至Hk不发生冲突为 止，则Hk为记录在表中的地址。通常用的处理冲突的方法有下列几种：开放定址法；再哈希法；链地址法； 建立公益区法。4.3 哈希查找给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根 据造表时设定的处理冲突的方法找“下一地址”，直至哈希表中某个位置为空， 或者表中所填记录的关键字等于给定值时为止。在LZW文本压缩中，其中主要的操作为在字典中查找是否存在当前的字符串。 字典数组有 6553个字典项，查找到某个字符串是否存在以及将未出现的字符串加 入到字典中， 需要

14、一个效率高的查找方法。 这就要求所用到的哈希函数能够尽可 能的分布均匀，避免冲突，减少查找的次数。本文中采用以下函数：其中，numx为当前的输入字符X的对应的整数值，numparent为当前的串I (未 加入X)的编码。当出现冲突时，使指针逐渐加一来解决。三、改进的LZV算法在对字典进行查找时，如果其索引为未使用，则表明该节点为未被使用；如 果该节点的索引值等于哈希函数值，则字符串在字典中存在。所以字典节点的第 二个字段index的作用有两个：一是表征给节点是否被使用过，二是检查是否存 在冲突。我们可以去掉第二个字段，将其作用用pare nt和symbol字段来实现，改进后 的字典节点结构为图

15、2：字段数值类型母节点(pare nt)int字符(symbol)char图2改进的节点结构我们用parent=65537,表示该节点存储的字符为基本的前256个ASCII码，用 式子parent=65538是否成立,表示该节点是否为已经用过的节点。编码过程如下：Compress()将所有ASCII插入到字典中，对字典进行初始化；将I初始化为输入的第一个字母的指针；while还有输入尚未处理hashcode=Hash(l,x)；While(hashcode.parent!=65538)|! ( hashcode.symbol=x|hashcode.parent=l )；If 哈希值节点的parent=65538将I.pare nt + I.symbpol l 插入到字典中该节点；将I.parent输出；I.parent置为I.symbol对应的值；Else输入下一个字符；I置为该节点对应的指针；输出输出流即为压缩后的文本。解码也创建一个相同的字典，其过程相似。解码器首先初始化字典，然后从 输入流中读取指针，用每个指针来定位字典中的一个字符。 利用parent字段返回 树的上层，并按相反的顺序取出字符串中的单个字符， 再按正常的顺序，把得到 的字符串记录到输出流中。此外，还有将当前字符串的第一个字符与上一个字符串添加到字典中。可见，在解码时，查找字