Lempel_Ziv编码的算法实现与应用研究
Computer Era No.122011
0引言
Lempel-Ziv 编码采用动态无损数据压缩算法对字符串进行动态编码，达到压缩文本的目的，由于算法复杂，直接实现的难度较大，目前尚无实际应用。国内外作为研究人员将Lempel-Ziv 编码与霍夫曼（Huffman ）编码或香农—范诺（Shannon-Fano ）编码结合，如ARJ、PKZip 算法，虽然能很好地对数据文件实施压缩，但由于执行效率较低，尤其是解码负荷大、速度慢，不能很好地适应需要实时数据压缩的场合。本文将探索Lempel-Ziv 编码/解码算法的实现方案，力图提高编码/解码效率，并尝试改进算法，使之能应用于实时数据压缩。
1算法概要
1.1压缩算法
选择一种单字符编码方案，设置单字符静态编码表；设置字符串动态编码表，初始为空；设置处理队列，初始为空。
顺序从源文本中提取单字符进队，每个单字符进队后，用队中字符/字符串查表：
⑴若表中有该字符/字符串的编码（字符编码一定有），则继续提取单字符进队；
⑵若表中无该字符串的编码，则在动态码表中添加队中字符串及其编码，且队中最后一个进队单字符前的字符/字符串依码表编码并出队。
从源文本中提取不到单字符时，队中字符/字符串依码表编码，结束。
例如：压缩ABABABC，代码为01332，单字符/字符串编码如表1所示。
表1
单字符/字符串编码表
单字符静态编码
字符A B C
编码012
字符串动态编码字符串AB BA ABA ABC
编码3456
1.2解压算法
选择与压缩相同的单字符编码方案，设置单字符静态编码表；设置字符串动态编码表，初始为空；设置处理队列，初始为空。
顺序从已压缩的文本中提取代码，对每个代码作以下处理：⑴依码表解码（码表中一定有该代码），相应的解码字符/字符串进队；
⑵如果不是第一个代码，则在动态码表中添加字符串编码，编码字符串由队中原有字符/字符串与新进队字符或字符串的第一个字符连接而得，然后原有字符串出队。
提取不到代码时，解压结束。
2实现方案
2.1压缩方案
依据上述算法的压缩程序实现方案如图1所示。2.2解压方案
依据上述算法的解压程序实现方案如图2所示。
Lempel-Ziv 编码的算法实现与应用研究
汪志达，邱斌
(宁波职业技术学院，浙江宁波315800)
摘
要：探讨了Lempel-Ziv 编码/解码算法的实现方案，力图提高编码/解码效率，并进行了算法改进，使之能更为有效地
应用于实时数据压缩。
关键词：实时压缩；Lempel-Ziv ；算法实现；编码中图分类号：TP301.6
文献标志码：A
文章编号：1006-8228（2011）12-06-02
Research on Implementing and Application of Lempel-Ziv Algorithm
WANG Zhi-da,Qiu Bin
（Ningbo Polytechnic,Ningbo ，Zhejiang 315800,China ）
Abstract ：We research the implementing method of Lempel-Ziv encoding/decoding algorithm,try to raise its efficiency,and improve the algorithm to make it more efficient in real-time data compression.Key words ：real-time compression ；Lempel-Ziv ；algorithm implementing ；encoding
收稿日期：2011-9-13
作者简介：汪志达（1964—），男，上海人，副教授，主要研究方向：算法设计与分析、数据通信与安全。
·
·6
计算机时代2011年第12期
选定单字符编码设置字符编码
建立队列初始化队列
建立压缩数据缓冲区
打开数据文件从文件中读入字符EOF （文件结束）
字符进队查表
压缩数据缓冲区的数
剧写入文件
命中
建立动态码表
添加列队中的字符串道动态码表最后入队的单字符前的字符/字符串出队
出队的字符/字符串进行编码编码的信息写入动态码表编码写入压缩数据缓冲区
Y
N
N
Y
图1压缩程序实现方案
选定与压缩时相同的单字符编码
添加单字符码表
建立队列
初始化队列建立解码数据缓冲区
从压缩包中提取代码解码的字符（串）进队列入队的是
第一个代码
建立动态码表
新进队的为字符串
队列中的原有串与新进队的字符串的第一个字符连接队列中的原有的串与新
进队的字符连接
把连接得到的字符串写入动态码表
队列中的原有的串出队
队列中的原有的串写入解码数据缓冲区
解码数据缓冲区的数据写入文件
Y
Y
N
N
图2解压程序实现方案
3结束语
将采用上述方案的程序嵌入网络聊天软件进行实际测试，当一次的发送/接收数据量在100K~2M 时，传输速率有较明显的提高，用户几乎感觉不到延迟。
除了应用于一般的实时通信外，本方案更适用于现在流行的网络游戏。目前网络游戏普遍存在通信延迟的问题，尤其是在线人数较多时，用户感到很“卡”，而网络游戏每次发送/接收的数据量一般都在300K 左右，如果采用动态压缩/解压传输，应
能有效缓解通信延迟的问题。
在每次传输的数据量较大的应用中，可以将压缩过程中生成的动态码表连同数据一起传送。这样就可以简化解压算法，提取的所有代码都直接查表解码，大大提高解压效率。
参考文献：
[1][美]William A.Shay,高传善等译.数据通信与网络教程[M].机械工业出版社,2000.
[2][美]Merike Kaeo,潇湘工作室译.网络安全性设计[M].人民邮电出版社,2000.
[3]裴礼文.数学分析中的典型问题与方法[M].高等教育出版社,2001.[4]Stallings https://www.wendangku.net/doc/9012769194.html,work and Internet Security[M].Englewood Cliffs,NJ:Prentice-Hall.1995.
[5]Schneier B.Applied Cryptograph[M].New York:Wiley.1994.·
·7