毕业设计论文正文参考文献(信息论LZW压缩算法实现).doc

2002级本科毕业设计论文 第 27 页 共 27 页1 引言现代信息论实际上是从本世纪二十年代奈奎斯特(Nyguist)和哈特莱(Hartly)的工作开始的。1924年奈奎斯特发表了“影响电报速率因素的确定”一文，1928年哈特莱发表了“信息传输”一文。他们最早研究了通信系统传输信息的能力，并给出了信息度量方法。1946年柯切尔尼柯夫()发表了“起伏噪声下的潜在抗干扰理论”的学位论文，他根据最小错误概率准则和最小均方误差准则研究了离散消息和连续消息的最佳接收问题。l943年到l949年维纳(Wiener)发表了两篇名著，这是战时关于目标自动予测和武器火力控制方面的研究成果，他根据最小均方误差准则研究信号的过滤问题。1948年香农(Shannon)发表了“通信的数学理论”一篇权威性长文，讨论了信源和信道特性。1949年香农又发表了“噪声中通信”一文。这两篇论文奠定了现代信息论的基础。通常称之为香农信息论，而香农也因此而成为信息论的奠基人。最近十多年来，无论在基本理论方面还是在实际应用方面，信息论都取得了巨大的进展。在香农理论基础上给出的最佳的噪声通信系统模型，近年来正在成为现实，这就是伪噪声编码信系统的迅速发展和实际应用。在噪声中信号过滤与检测基础上发展起来的信号检测理论和在抗干扰编码基础上发展起来的编码理论已成为近代信息论的两个重要分支。此外，象模糊信息，相对信息，主观信息以及智能信息处理，自动化信息控制等大量崭新的课题的研究也相继展开，使信息理论的面貌为之一新，并将大大促进信息科学的发展。2 信息与信息论2.1 信息论的研究内容与其它科学一样，信息论也是从生产实践中总结出来的，反过来又服务于实践，指导实践。信息论虽然主要地是从通信实践中总结出来的，但由于它的许多规律的概括性和综合性，已远远超过通信科学技术的范围，在其它许多科学领域得到应用。因此，信息论的研究范畴极为广泛，除了研究通信的问题以外，还包含诸如数学、文字学、语言学、心理学、神经生理学以及语义学等方面的问题。归纳起来，信息论研究的内容，大致包括以下几个方面。1. 通信的统计现论的研究，主要研究利用统计数学工具分析信息和信息传输的统计规律，其具体内容有：1) 信息的度量，2) 信息速率与熵，3) 信道传输能力信道容量。2. 信源的统计特性，主要包括：1) 文字(如汉字)，字母(如英文)统计特性，2) 语声的参数分析和统计特性，3) 图片及活动图象(如电视)的统计特性，4) 其它信源的统计特性。3. 收信者接收器官的研究，主要包括：1) 人的听觉和视觉器官的特性，2) 人的大脑感受和记忆能力的模拟。这些问题的研究与生物学、生理学、心理学的研究密切相关。4. 编码理论与技术的研究，主要包括：1) 有效性编码：用来提高信息传输效率，它主要是针对信源的统计特性进行编码，所以有时也称为信源编码，2) 抗干扰编码：用来提高信息传输的可靠性，它主要是针对信道统计特性进行编码，所以有时也称为信道编码。5. 提高信息传输效率的研究，主要包括：1) 功率的节约，2) 频带的压缩，3) 传输时间的缩短，即快速传输问题。6. 抗干扰理论与技术的研究，主要包括：1) 各种调制制度的抗干扰性，2) 理想接收机的实现。7. 噪声中信号检测理论与技术的研究，主要包括：1) 信号检测的最佳准则，2) 信号最佳检测的实现。信息论的研究内容极其广泛，它是一门新兴的边缘科学，是当代信息科学的基本的和重要的理论基础。综上所述，信息论的研究范畴可以概括为以下三个方面的内容：1. 狭义信息论：主要研究信息的度量、信道容量以及信源编码等问题。以香农信息论为基本内容，也称为基本信息论。2. 一般信息论：主要研究通信的一般理论，其中包括信号与噪声理论，信号过滤与检测，调制制度，抗干扰编码以及信息处理等问题。因此，一般信息论主要是研究信息传输的基本理论，即通信的基本问题。所以一般信息论也称为通信理论。3. 广义信息论：其内容不仅包括上面所述的两个方面，而且还包括与信息有关的其它领域。如生理学，生物学，遗传工程学等等。广义信息论是指利用狭义信息论观点来研究一切问题的理论。2.2 信息的定义辞海里信息论的词条说：“信息是指对消息接收者来说预先不知道的报道”，这里强调了信息的未知性，近代控制论创始人维纳在控制论一书中指出：“信息就是信息，不是物质，也不是能量。”这里他虽然没有给“信息”下一个明确的定义，但是却指出了“信息”是独立于物质和能量之外的一种客观存在。广义的信息是指一个事物的运动状态以及状态发生变化的方式，从这个意义上讲，信息是一种客观存在，与我们主观是否感觉到它的存在没有关系，所以广义的信息又叫“本体论信息”，是一种纯客观的信息概念。狭义的信息概念只把那些认识主体所能感受到的“某个事物的状态及状态的变化方式”才视为信息。那些接受主体感觉不出来的，或者是感觉到了但不能理解的东西，都不叫信息。例如一些至今仍未能破译的古代文学和符号，因为我们尚不能理解他，所以就不能称之为信息。2.3 信息的特点信息具有以下特点：1. 信息与物质密切相联，但不是物质本身。信息是依附于物质之上的，没有物质和物资的运动，就没有与物质相联系的信息。2. 信息与精神密切相关。人类思维活动基本是跟信息相关的。3. 信息与能量相辅相存。没有了能量，就没有了事物的运动，也就没了信息。4. 信息具有知识的秉性。信息论的创始人香农在他的奠基作通信的数学理论中写道：“信息是能够用来消除不确定性的东西”。信息能够改变人们的知识状态，使人们对某些事物从不知到知之，从知之甚少到知之甚多。5. 信息普遍存在，而且永不枯竭，不断更新。6. 信息可被感知、传递、处理和共享。信息可以被主体直接或间接所感知，被感知的运动状态和状态变化方式可以被记忆（存储）、被转换（重新表达）和被加工处理。另一方面，由于信息只是事物的运动状态和状态变化方式，不是事物本身，因而就可以通过一定的措施使他脱离原来的事物，附着于新的事物（称为载体），这使信息可以被摄取、记录、复制、传输以及被共享的根据。而且这种复制和共享可以重复进行。2.4 信息的度量当我们收到一封信或电报时，便能获得一定的信息，因为在此以前我们并不能肯定其中的一些内容。就是说，信息蕴含于不肯定性中，而不肯定性在概率论中是用随机事件或随机变量来描述的。那么，哪些随机事件(或随机变量)含有较多的信息? 按常识一般认为，就单个事件比较，小概率事件的信息量大。百年不遇的事件，一旦发生，必定令人震惊(通常所谓“爆冷门”，即小概率事件发生)。就诸随机分布比较基本事件个数相同者，以等概分布平均信息量大。比如，预测两个势均力敌者谁取胜，比判定两个实力悬殊的对手不肯定性大。就等概随机场而论，基本事件个数多者，平均信息量大，就是说，三择一比两择一不肯定性大。由上述可见，信息伴随着不肯定性。信息的定量表征必然联系着不肯定性的度量。对一般有限离散概率场的不肯定性可给出下列度量。设是取有限个值的随机变量，则的熵定义为其中对数底可为任何正数，并规定当时, 。因为上式与热力学领域中熵的定义相似，由香农首先引入，所以把它称为香农熵，它是信息的一种基本度量。香农熵的产生，对信息理论的发展有着划时代的意义。对数底决定了熵的单位。比如2，3，10，熵的单位分别为bit，nat，tet，det。各个单位之间由换底公式：来进行转换。3 信源编码及压缩信源编码理论和压缩技术的研究是信息论的一个主要研究方向。下面将就信源编码理论进行简单介绍，并对压缩技术的发展进行简单的叙述。3.1 信源的概念信源就是个概率场。比如，全体汉字及其概率分布(每个字的使用率)；26个英文字母及其概率分布等等，都是信源。确切来说，这是单表或一维信源，实际上各种文字的应用都是以单字或一串字母加上标点符号来表现的。因而把一列随机变量叫做信源，其中每个随机变量取值于某个集合中，称为信源字母集(或消息集)，其中元素个数用表示，通常总假定，就是说，只限于考虑有限离散信源。特别地，若随机变量为独立同分布时，则称之为无记忆信源；若它们构成马氏链，则称为马氏信源。具体分析时，常考虑有限长信源序列，即。一个长样本称为长消息，它是的一个实现。长消息的全体个数为。3.2 编码的概念消息可能是各种符号组成的，但文字、标点及各种代号等，往往不适于存贮与传递，因而总是用一组适当的符号代替消息元。代用符号集称为信号集合或码符集，且假定。通常在数字通信中。总选为某有限域(Galois域)，。长消息的一个码，就是一对映射其中表示码符集的元素的全体有限序列的集合：而表示全体长消息的集合：每个叫作一个码字，称为码字集合(有时也简称为码)。显然特别地，当时，称为二元码。到的分组码，是指映射此码称为定长码(码字等长)。前述一般称为变长码(码字不等长)。3.3 信源编码信源编码是根据信源的统计特性，对信源发出的消息进行编码。一般而言，编码就是用数字形式表示消息的过程。信源编码可分为无失真编码与有失真编码。所谓无失真编码问题就是要求编码能够百分之百恢复原来的数据信息，经编码运算后不丢失任何信息；而有失真编码问题就是允许编码运算有一定的误差发生，在允许误差的条件下，寻找信源的最小“信号体积”。有失真与无失真编码是两种不同类型要求的编码，它们有各自的应用领域。信源的无失真编码，又可分为变长编码与等长编码。就是在从消息到信号的编码过程中，如果消息的长度固定，而信号的长度分固定与不固定两种不同的类型。使用定长码的主要优点是编码运算简单，它可以根据消息与信号的长度自动区分各自所对应的字符。但他的缺点是编码利用率低，影响编码效果。变长码是近代通信技术发展的编码理论技术，近代变长码的编码结构不仅考虑消息发生的概率，而且还利用消息前后字母的关联特性，因此利用变长码可提高编码效率。3.4 数据压缩技术数据压缩技术是编码理论的一个分支和子集。当我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。远在计算机出现之前，著名的Morse电码就已经成功地实践了这一准则。在Morse码表中，每个字母都对应于一个唯一的点划组合，出现概率最高的字母e被编码为一个点“.”，而出现概率较低的字母z则被编码为“-.”。显然，这可以有效缩短最终的电码长度。信息论之父香农第一次用数学语言阐明了概率与信息冗余度的关系。在1948年发表的论文“通信的数学理论”中，香农指出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。这篇伟大的论文后来被誉为信息论的开山之作，香农提出的信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。1948年，香农在提出信息熵理论的同时，也给出了一种简单的编码方法Shannon编码。1952年，R.M.Fano又进一步提出了Fano编码。第一个实用的编码方法是由D.A.Huffman在1952年的论文“最小冗余度代码的构造方法（A Method for the Construction of Minimum Redundancy Codes）”中提出的，后人称之为Huffman编码。1968年前后，P.Elias发展了Shannon和Fano的编码方法，构造出从数学角度看来更为完美的Shannon-Fano-Elias编码。沿着这一编码方法的思路，1976年，J.Rissanen提出了一种可以成功地逼近信息熵极限的编码方法算术编码。1982年，Rissanen和G.G.Langdon一起改进了算术编码。之后，人们又将算术编码与J.G.Cleary和I.H.Witten于1984年提出的部分匹配预测模型(PPM)相结合，开发出了压缩效果近乎完美的算法。Ziv和Lempel于1977年发表题为“顺序数据压缩的一个通用算法(A Universal Algorithm for Sequential Data Compression）”的论文，后人称之为LZ77算法。1978年，二人又发表了该论文的续篇“通过可变比率编码的独立序列的压缩（Compression of Individual Sequences via Variable Rate Coding）”，描述了后来被命名为LZ78的压缩算法。1984年，T. A. Welch发表了名为“高性能数据压缩技术（A Technique for High Performance Data Compression）”的论文，描述了他在Sperry研究中心的研究成果，这是LZ78算法的一个变种，也就是后来非常有名的LZW算法。1990年后，T. C. Bell等人又陆续提出了许多 LZ 系列算法的变体或改进版本。压缩分为有损压缩和无损压缩。常见的无损压缩运算采用的算法有Huffman编码、算术码、LZW编码等。4 LZW压缩算法以色列数学家Ziv和Lemple在IEEE上的两篇文章，提出了两种基于字典的压缩算法，就是被广泛引用的LZ77和LZ78算法，后来分别被改进成为LZSS和LZW，成了很长时间内无失真压缩的主流算法。LZW是Welch在1984年的一篇文章中提出的改进算法。LZW压缩算法最终由Lemple-Ziv-Welch三个人的名字命名。LZW算法广泛用于信源编码技术和数据压缩技术,大家所熟知的GIF图片存储格式以及ZIP压缩文件都采用了经过改进的LZW算法。LZW技术比其它大多数压缩技术都复杂，压缩效率也较高。4.1 LZW的基本原理LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(String Table)。在编码时，数据流是输入对象（图像的光栅数据序列），编码流就是输出对象（存储在GIF文件的图像数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串(String)：由几个连续的字符组成；前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：单个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，也是编码表的映射值；图案：一个字符串，按不定长度从数据流中读出。LZW压缩的原理，就是先提取原始图像数据中的不同图案，基于这些图案创建一个编译表，然后用编译表中的图案索引来替代原始光栅数据中的相应图案，减少原始数据大小。看起来和调色板图像的实现原理差不多，但这里的编译表不是事先创建好的，而是根据原始图象数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表（LZW压缩文件中是不携带编译表信息的），为了更好理解编码和解码原理，我们继续下一小节。4.2 LZW的编码运算LZW编码运算的第一步：初始化一个编译表(String Table)，假设这个编译表的大小是12位的，也就是最多有4096个单位，另外假设我们有32个不同的字符（也可以认为图像的每个像素最多有32种颜色），表示为a，b，c，d，e.，初始化编译表：第0项为a，第1项为b，第2项为c.一直到第31项，我们把这32项就称为根(Root)。开始编译，先定义一个前缀对象Current Prefix，记为.c.，现在它是空的，然后定义一个当前字符串Current String，标记为.c.k，.c.就为Current Prefix，k就为当前读取字符。现在来读取数据流的第一个字符，假如为p，那么Current String就等于.c.p（由于.c.为空，实际上值就等于p），现在在编译表中查找有没有Current String的值，由于p就是一个根，我们已经初始了32个根，当然可以找到，把p设为Current Prefix的值，不做任何事继续读取下一个字符，假设为q，Current String就等于.c.q（也就是pq），看看在编译表中有没有该值，当然。没有，这时我们要做下面的事情：将Current String的值（也就是pq）添加到编译表的第32项，把Current Prefix的值（也就是p）在编译表中的索引输出到编码流，修改Current Prefix为q。继续往下读，如果在编译表中可以查找到Current String的值(.c.k)，则把Current String的值(.c.k)赋予Current Prefix；如果查找不到，则添加Current String的值(.c.k)到编译表，把Current Prefix的值(.c.)在编译表中所对应的索引输出到编码流，同时修改Current Prefix为k ，这样一直循环下去直到数据流结束。来看一个具体的例子,我们假设字符集是0-255的256个字节值，这256个符号组成了一个初始的编译表，分别编号为#0到#255。LZW的压缩编码就从这个编译表开始。对于消息=WED=WE=WEE=WEB=WET我们看如何进行编码。首先编译表中的0-255分别对应了256个编译表中的条目，即字节值0-255，所以消息中的每一单个的字符都在编译表中出现过，或者说都能被检测到，我们一步一步看其输出编码的过程和编译表的变化，设当前位置为原消息中需要确定输出编码的字符所在位置，最初为0，对应字符“=”。第1步，看当前位置以及其后还有多长的字符，作为一个整体是编译表的条目，显然“=”已经在编译表中，而“=W”则不是，这时输出“=”的编码61，同时把“=W”添加到编译表中(见表1),所以编译表的第257个条目为“=W”，令其编号为256，当前位置前移一位，变为1，当前字符为“W”。第2步，从消息的第1个位置开始，“W”已经在编译表中了，而“WE”不是，同样的，输出“W”的编码87，同时把“WE”添加到编译表中，编号为257，当前位置变为2，当前字符为“E”。第3步，从消息的第2个位置开始，“E”已经在编译表中了，而“ED”不是，同样的，输出“E”的编码69，同时把“ED”添加到编译表中，编号为258，当前位置变为3，当前字符为“D”。第4步，从消息的第3个位置开始，“D”已经在编译表中了，而“D=”不是，同样的，输出“D”的编码68，同时把“D=”添加到编译表中，编号为259，当前位置变为4，当前字符为“=”。第5步，从消息的第4个位置开始，“=”和“=W”（256）已经在编译表中了，而“=WE”不是，输出“=W”的编码256，同时把“=WE”添加到编译表中，编号为260，当前位置变为6，当前字符为“E”。第6步，从消息的第6个位置开始，“E”已经在编译表中了，而“E=”不是，输出“E”的编码69，同时把“E=”添加到编译表中，编号为261，当前位置变为7，当前字符为“=”。第7步，从消息的第7个位置开始，“=”、“=W”（256）、“=WE”（260）已经在编译表中了，而“=WEE”不是，输出“=WE”的编码260，同时把“=WEE”添加到编译表中，编号为262，当前位置变为10，当前字符为“E”。第8步，从消息的第10个位置开始，“E”、“E=”（261）已经在编译表中了，而“E=W”不是，输出“E=”的编码261，同时把“E=W”添加到编译表中，编号为263，当前位置变为12，当前字符为“W”。第9步，从消息的第12个位置开始，“W”、“WE”（257）已经在编译表中了，而“WEB”不是，输出“WE”的编码257，同时把“WEB”添加到编译表中，编号为264，当前位置变为14，当前字符为“B”。第10步，从消息的第14个位置开始，“B”已经在编译表中了，而“B=”不是，输出“B”的编码66，同时把“B=”添加到编译表中，编号为265，当前位置变为15，当前字符为“=”。第11步，从消息的第15个位置开始，“=”、“=W”（256）、“=WE”（260）已经在编译表中了，而“=WET”不是，输出“=WE”的编码260，同时把“=WET”添加到编译表中，编号为266，当前位置变为18，当前字符为“T”。第12步，从消息的第18个位置开始，“T”已经在编译表中了，而其后没有了字符，输出“T”的编码84即完成整个的编码过程。整个的编码结果为“61、87、69、68、256、69、260、261、257、66、260、84”(见表2)。4.3 LZW的解码运算数据的解码，其实就是数据编码的逆向过程，要从已经编译的数据（编码流）中找出编译表，然后对照编译表还原图像的光栅数据。压缩过程中建立起来的庞大字典不需要传递给LZW的解码程序，这是LZW效率的一个主要方面。编码（Code）前缀（Prefix）61=66B68D69E84T87W256=W257WE258ED259D=260=WE261E=262=WEE263E=W264WEB265B=266=WET当前字符序列输出编码新短语(添至编译表)=WED=WE=WEE=WEB=WET 61(=)256(=W)WED=WE=WEE=WEB=WET 87(W)257(WE)ED=WE=WEE=WEB=WET 69(E)258(ED)D=WE=WEE=WEB=WET 68(D)259(D=)=WE=WEE=WEB=WET 256(=W)260(=WE)E=WEE=WEB=WET 69(E)261(E=)=WEE=WEB=WET 260(=WE)262(=WEE)E=WEB=WET 261(E=)263(E=W)WEB=WET 257(WE)264(WEB)B=WET 66(B)265(B=)=WET 260(=WE)266(=WET)T 84(T)表1 编码生成的编译表表2 编码过程示意表首先，还是要初始化编译表。压缩文件的数据的第一个字节存储的就是LZW编码的编码大小（若是图像文件等于图像的位数），根据编码大小，初始化编译表的根条目（从“0”到“2的编码大小次方-1”），然后定义一个当前编码Current Code，记作code，定义一个Old Code，记作old。读取第一个编码到code，这是一个根编码，在编译表中可以找到，把该编码所对应的字符输出到数据流，old=code；读取下一个编码到code，这就有两种情况：在编译表中有或没有该编码，我们先来看第一种情况：先输出当前编码code所对应的字符（串）到数据流，然后把old所对应的字符（串）当成prefix .，当前编码code所对应的字符（串）的第一个字符当成k，组合起来当前字符串Current String就为.k，把.k添加到编译表，读下一个编码；我们来看看在编译表中找不到该编码的情况，回想一下编码情况：如果数据流中有一个p.p.pq这样的字符串，p.在编译表中而p.p不在，编译器将输出p.的索引而添加p.p到编译表，下一个字符串p.p可以在编译表中找到而p.pq不在编译表，同样将输出p.p的索引值而添加p.pq到编译表，这样看来，解码器总比编码器“慢一步”，当我们遇到p.p所对应的索引时，我们不知道该索引对应的字符串（在解码器的编译表中还没有该索引，事实上，这个索引将在下一步添加）。这时需要用猜测法：现在假设上面的p.所对应的索引值是#58，那么上面的字符串经过编译之后是#58#59，我们在解码器中读到#59时，编译表的最大索引只有#58，#59所对应的字符串就等于#58所对应的字符串(也就是p.)加上它的第一个字符(也就是p)，也就是p.p。事实上，这种猜测法是很准确。如下例(表3)中的800（ABCDA）。 当前字符序列输出编码新短语ABCD387(ABC)500(ABCD)ABCDA500(ABCD)800(ABCDA)ABCDAY800(ABCDA)801(ABCDAY)表3 一个编码过程的片断对于这种情形，因为第二列是输出的编码序列，也就是压缩的结果，解码的算法会看到这样的编码序列：，387，500，800，。我们看到在解码的过程中（见表4），读进编码500时，确定输出ABCD，将短语799（A）添加到字典，当读进编码800时，发现编码为800的短语还没有添加到字典中，于是解码就进行不下去了，因为字典中的条目800是我们处理完当前短语才能确定的。当前编码当前短语（输出）字典中新的短语500ABCD799（A）800?800（）表4 解码过程中的意外唯一出现这种问题的情形是字典中新的短语就是当前编码对应的短语，而当前短语的最后一个字母，实际上也是它的第一个字母，也就是上次编码对应短语的第一个字母，所以短语800的第一个字母，同时也是上次短语的第一个字母，因而，我们可以很容易地推断800编码的断语是ABCDA，最后的一个字符应当就是第一个字符A。来看一个解码运算具体的例子,对于我们上一小节编码得到的编码流“61、87、69、68、256、69、260、261、257、66、260、84”进行解码运算。首先初始化编译表，字符集是0-255的256个字节值，这256个符号组成了一个初始的编译表，分别编号为#0到#255。设当前位置为编码流中需要确定输出的编码所在位置，最初为0，对应编码“61”。第1步，看当前位置对应的编码是否已存在于编译表中，显然“61”已经在编译表中，这时输出编码“61”对应的字符“=”。当前位置前移一位，变为1，当前编码为“87”。第2步，看当前位置对应的编码是否已存在于编译表中，显然“87”已经在编译表中，这时输出编码“87”对应的字符“W”。同时把“=W”添加到编译表中(见表5)，编号为256，当前位置前移一位，变为2，当前编码为“69”。第3步，看当前位置对应的编码是否已存在于编译表中，显然“69”已经在编译表中，这时输出编码“69”对应的字符“E”。同时把“WE”添加到编译表中，编号为257，当前位置前移一位，变为3，当前编码为“68”。第4步，看当前位置对应的编码是否已存在于编译表中，显然“68”已经在编译表中，这时输出编码“68”对应的字符“D”。同时把“ED”添加到编译表中，编号为258，当前位置前移一位，变为4，当前编码为“256”。第5步，看当前位置对应的编码是否已存在于编译表中，显然“256”已经在编译表中，这时输出编码“256”对应的字符“=W”。同时把“D=”添加到编译表中，编号为259，当前位置前移一位，变为5，当前编码为“69”。第6步，看当前位置对应的编码是否已存在于编译表中，显然“69”已经在编译表中，这时输出编码“69”对应的字符“E”。同时把“=WE”添加到编译表中，编号为260，当前位置前移一位，变为6，当前编码为“260”。第7步，看当前位置对应的编码是否已存在于编译表中，显然“260”已经在编译表中，这时输出编码“260”对应的字符“=WE”。同时把“E=”添加到编译表中，编号为261，当前位置前移一位，变为7，当前编码为“261”。第8步，看当前位置对应的编码是否已存在于编译表中，显然“261”已经在编译表中，这时输出编码“261”对应的字符“E=”。同时把“=WEE”添加到编译表中，编号为262，当前位置前移一位，变为8，当前编码为“257”。第9步，看当前位置对应的编码是否已存在于编译表中，显然“257”已经在编译表中，这时输出编码“257”对应的字符“WE”。同时把“E=W”添加到编译表中，编号为263，当前位置前移一位，变为9，当前编码为“66”。第10步，看当前位置对应的编码是否已存在于编译表中，显然“66”已经在编译表中，这时输出编码“66”对应的字符“B”。同时把“WEB”添加到编译表中，编号为264，当前位置前移一位，变为10，当前编码为“260”。第11步，看当前位置对应的编码是否已存在于编译表中，显然“260”已经在编译表中，这时输出编码“260”对应的字符“=WE”。同时把“B=”添加到编译表中，编号为265，当前位置前移一位，变为11，当前编码为“84”。第12步，看当前位置对应的编码是否已存在于编译表中，显然“84”已经在编译表中，这时输出编码“84”对应的字符“T”。同时把“=WET”添加到编译表中，编号为266。而其后没有了编码，此时即完成整个的解码过程。整个的解码结果为“=WED=WE=WEE=WEB=WET”(见表6)。编码（Code）前缀（Prefix）61=66B68D69E84T87W256=W257WE258ED259D=260=WE261E=262=WEE263E=W264WEB265B=266=WET当前编码当前短语(输出)新短语(添至编译表)61=87W256(=W)69E257(WE)68D258(ED)256=W259(D=)69E260(=WE)260=WE261(E=)261E=262(=WEE)257WE263(E=W)66B264(WEB)260=WE265(B=)84T266(=WET)表5 解码生成的编译表表6 解码过程示意表5 LZW压缩的程序实现以上对LZW编码压缩算法的理论进行了简要的介绍，下面将对LZW压缩方法进行由理论到实际的转化。在Microsoft Visual C+ 6.0 的开发环境下，编写一个简单的程序，使其能够进行基于LZW编码压缩算法的压缩与解压缩，并对压缩前后的文件大小进行统计。5.1 程序实现的目标编制一个基于对话框的程序，对选择的文件能识别是否是压缩文件（此处所说的“压缩文件”，如无特殊说明，一般特指采用本文所编压缩程序进行压缩操作所得到扩展名为“.lzw”的压缩文件），若是压缩文件，可选择进行解压缩操作，若是非压缩文件，可选择进行压缩操作。对于解压操作要读取文件头，显示压缩文件和原文件大小并粗略统计压缩率：对于压缩操作同样要统计并显示压缩前后的文件大小及压缩率。压缩操作会生成扩展名为“.lzw”的同名压缩文件，解压“.lzw”文件会生成与压缩前文件同名的文件，与欲解压的“.lzw”文件的文件名没有关系。若已有同名文件存在，会提示是否覆盖。当压缩或解压缩完成时有对话框提示操作完成。5.2 程序的具体实现对于LZW编码压缩的理论，前面已经有了初步的介绍，根据前文所述的编码与解码的理论，可以编写程序主体部分的流程图。图1为编码程序段的流程图，图2为解码程序段的流程图。据此，可以编写实现压缩与解压缩的函数伪代码。编码过程的伪代码如下所示：Initialize String Table;.c. = Empty;.c.k = First Character in CharStream;while (.c.k != EOF )if ( .c.k is in the StringTable).c. = .c.k;Elseadd .c.k to the StringTable;Output the Index of .c. in the StringTable to the CodeStream;.c. = k;k = Next Character in CharStream;Output the Index of .c. in the StringTable to the CodeStream;初始化编译表初始化CurrentPrefix(赋值为空)读取第一个字符，赋值给当前字符串（.C.k，CurrentPrefix+k）文件结束在编译表中能找到CurrentPrefix将当前字符串添加到编译表输出CurrentPrefix的编码CurrentPrefix = kCurrentPrefix = 当前字符串k = 读取下一字符真假真假图1 编码程序段的流程图初始化编译表初始化CurrentCode(赋值为第一个编码)并输出相应字符串OldCode = CurrentCode ; CurrentCode = 读取下一编码文件结束在编译表中能找到CurrentCode输出CurrentCode对应的字符串将OldCode+“CurrentCode的首字母”添加到编译表OldCode = CurrentCode ;输出OldCode+“OldCode的首字母”并添加其至编译表k = 读取下一字符真假真假图2 解码程序段的流程图解码过程的伪代码如下所示：Initialize String Tab