Lempel_Ziv编码的算法实现与应用研究

1、Computer Era No. 1220110引言Lempel-Ziv 编码采用动态无损数据压缩算法对字符串进 行动态编码, 达到压缩文本的目的, 由于算法复杂, 直接实现的 难 度 较 大 , 目 前 尚 无 实 际 应 用 。 国 内 外 作 为 研 究 人 员 将 Lempel-Ziv 编 码 与 霍 夫 曼 (Huffman 编 码 或 香 农 范 诺 (Shannon-Fano 编码结合, 如 ARJ、 PKZip 算法, 虽然能很好地 对数据文件实施压缩, 但由于执行效率较低, 尤其是解码负荷 大、 速度慢, 不能很好地适应需要实时数据压缩的场合。本文 将探索 Lempel-Zi

2、v 编码/解码算法的实现方案, 力图提高编码/解码效率, 并尝试改进算法, 使之能应用于实时数据压缩。1算法概要1.1压缩算法选择一种单字符编码方案, 设置单字符静态编码表; 设置 字符串动态编码表, 初始为空; 设置处理队列, 初始为空。顺序从源文本中提取单字符进队, 每个单字符进队后, 用 队中字符/字符串查表: 若表中有该字符/字符串的编码 (字符编码一定有 , 则 继续提取单字符进队; 若表中无该字符串的编码, 则在动态码表中添加队中 字符串及其编码, 且队中最后一个进队单字符前的字符/字符串 依码表编码并出队。从源文本中提取不到单字符时, 队中字符/字符串依码表编 码, 结束。例如:

3、压缩 ABABABC, 代码为 01332, 单字符/字符串编码 如表 1所示。表 1单字符/字符串编码表单字符静态编码字符 A B C编码 012字符串动态编码 字符串 AB BA ABA ABC编码 34561.2解压算法选择与压缩相同的单字符编码方案, 设置单字符静态编码 表; 设置字符串动态编码表, 初始为空; 设置处理队列, 初始为空。顺序从已压缩的文本中提取代码, 对每个代码作以下处理: 依码表解码 (码表中一定有该代码 , 相应的解码字符/字符串进队; 如果不是第一个代码, 则在动态码表中添加字符串编 码, 编码字符串由队中原有字符/字符串与新进队字符或字符串 的第一个字符连接而

4、得, 然后原有字符串出队。提取不到代码时, 解压结束。2实现方案2.1压缩方案依据上述算法的压缩程序实现方案如图 1所示。 2.2解压方案依据上述算法的解压程序实现方案如图 2所示。Lempel-Ziv 编码的算法实现与应用研究汪志达,邱 斌(宁波职业技术学院,浙江 宁波 315800摘要:探讨了 Lempel-Ziv 编码 /解码算法的实现方案, 力图提高编码 /解码效率, 并进行了算法改进, 使之能更为有效地应用于实时数据压缩。关键词:实时压缩; Lempel-Ziv ; 算法实现; 编码 中图分类号:TP301.6文献标志码:A文章编号:1006-8228(2011 12-06-02Re

5、search on Implementing and Application of Lempel-Ziv AlgorithmWANG Zhi-da, Qiu Bin(Ningbo Polytechnic, Ningbo , Zhejiang 315800, China Abstract :We research the implementing method of Lempel-Ziv encoding/decodingalgorithm, try to raise its efficiency, and improve the algorithm to make it more effici

6、ent in real-time data compression. Key words :real-time compression ; Lempel-Ziv ; algorithm implementing ; encoding收稿日期:2011-9-13作者简介:汪志达 (1964 , 男, 上海人, 副教授, 主要研究方向:算法设计与分析、 数据通信与安全。6计算机时代 2011年 第 12期 图 1压缩程序实现方案 图 2解压程序实现方案3结束语将采用上述方案的程序嵌入网络聊天软件进行实际测试, 当一次的发送/接收数据量在 100K2M时, 传输速率有较明显 的提高, 用户几乎感觉不

7、到延迟。除了应用于一般的实时通信外, 本方案更适用于现在流行 的网络游戏。目前网络游戏普遍存在通信延迟的问题, 尤其是 在线人数较多时, 用户感到很 “卡” , 而网络游戏每次发送/接收 的数据量一般都在 300K 左右, 如果采用动态压缩/解压传输, 应能有效缓解通信延迟的问题。在每次传输的数据量较大的应用中, 可以将压缩过程中生 成的动态码表连同数据一起传送。这样就可以简化解压算法, 提取的所有代码都直接查表解码, 大大提高解压效率。参考文献:1美WilliamA.Shay, 高传善等译. 数据通信与网络教程M.机械工 业出版社,2000.2美MerikeKaeo, 潇湘工作室译. 网络安全性设计M.人民邮电出 版社,2000.3裴礼文. 数学分析中的典型问题与方法M.高等教育出版社,2001. 4Stallings W. Network and In