基于MATLAB的Lemple-Ziv编码仿真

常金勇，李海增，宋永任

（长治学院 数学系，山西 长治 046011）

1 引言

在寻找信源最优码的过程中出现了许多编码方法，如哈弗曼（Huffman）码，申农-法诺-艾利亚斯（Shannon-Fano-Elias）码等.这些码的构造前提是必须知道信源的统计特性，而在大多数实际情况中信源的统计特性事先是未知的，如对不同的文本，其字符出现的统计特性可能不一样，这就需要一种通用的信源编码方法.LZ（Lempel-Ziv）算法就是目前应用较广的一种通用信源编码.

2 LZ算法

2.1 LZ算法简介

LZ算法是由Lempel和Ziv在20世纪70年代末提出的，它是一种语法解析码，利用信源输出符号自身的信息来进行压缩编码.它能有效地利用信源输出信息字符的频率，重复性和高使用率的冗余度，是一种自适应算法，只须对信源序列进行一次扫描，无需知道信源的先验统计特性，运算时间正比于消息长度.它广泛应用于计算机文件的压缩，在Dos 6.0中作压缩程序.

2.2 LZ算法的一般步骤[1]

设信源发出的消息字符序列为(xi,-∞0和 ρ:0<ρ≤n，使得：

②L是使①成立的最大可能的匹配长度；

③ρ满足0<ρ≤n且使①和②成立的最小数值（也就是使匹配长最大，其匹配开始的位置离x0最近）.设Lmax和ρmin为上述算法找到的数值,则预处理器发送(1,Lmax,ρmin).

2.3 LZ算法的缺点

（1）不能有效利用位置的冗余度.

（2）通常在消息起始段压缩效果差一些，消息列长了之后效果变好，但自适应算法大多数在处理了一定数量的消息后其自适应能力会降低，从而使压缩效率降低.

3 LZ算法的Matlab实现

程序设计主要步骤如下：

（1）定义编码主函数：

%从源文件获得要编码的内容；

%从源文件获得字符并将它与字典中对象做比较.若有，移向下一位字符；否则，%将它加入到字典中；

4 具体实例分析

根据已编好的程序，我们对内容为：“Lempel-Ziv Coding Simulation Based on Matlab”源文件source.txt执行LZ算法得到它的编码结果encode.txt为：

〔1〕叶中行.信息论基础[M].北京：高等教育出版社，2003.

〔2〕陈检，王铁丹，侯迪，等.关于ZL数据压缩算法性能的实验研究[J].计算机应用,1992(5)：5-8.

〔3〕沈世镒,吴忠华.信息论基础与应用[M].北京：高等教育出版社，2004.

〔4〕王忠敏.基于字符串匹配的通用数据压缩算法[J].计算机应用,1995(1),38-40.

〔5〕常炯.信息理论基础[M].北京:清华大学出版社,1993.

〔6〕张伯雄.数据压缩的原理与实践[J].微电子学与计算机,1994(5)：35-38.

〔7〕章照止,林须端.信息论与最优编码[M].上海:上海科学技术出版社,1993.