常金勇，李海增，宋永任

（長治學院 數(shù)學系，山西 長治 046011）

1 引言

在尋找信源最優(yōu)碼的過程中出現(xiàn)了許多編碼方法，如哈弗曼（Huffman）碼，申農(nóng)-法諾-艾利亞斯（Shannon-Fano-Elias）碼等.這些碼的構(gòu)造前提是必須知道信源的統(tǒng)計特性，而在大多數(shù)實際情況中信源的統(tǒng)計特性事先是未知的，如對不同的文本，其字符出現(xiàn)的統(tǒng)計特性可能不一樣，這就需要一種通用的信源編碼方法.LZ（Lempel-Ziv）算法就是目前應用較廣的一種通用信源編碼.

2 LZ算法

2.1 LZ算法簡介

LZ算法是由Lempel和Ziv在20世紀70年代末提出的，它是一種語法解析碼，利用信源輸出符號自身的信息來進行壓縮編碼.它能有效地利用信源輸出信息字符的頻率，重復性和高使用率的冗余度，是一種自適應算法，只須對信源序列進行一次掃描，無需知道信源的先驗統(tǒng)計特性，運算時間正比于消息長度.它廣泛應用于計算機文件的壓縮，在Dos 6.0中作壓縮程序.

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

設(shè)信源發(fā)出的消息字符序列為(xi,-∞0和 ρ:0<ρ≤n，使得：

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

③ρ滿足0<ρ≤n且使①和②成立的最小數(shù)值（也就是使匹配長最大，其匹配開始的位置離x0最近）.設(shè)Lmax和ρmin為上述算法找到的數(shù)值,則預處理器發(fā)送(1,Lmax,ρmin).

2.3 LZ算法的缺點

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

（2）通常在消息起始段壓縮效果差一些，消息列長了之后效果變好，但自適應算法大多數(shù)在處理了一定數(shù)量的消息后其自適應能力會降低，從而使壓縮效率降低.

3 LZ算法的Matlab實現(xiàn)

程序設(shè)計主要步驟如下：

（1）定義編碼主函數(shù)：

%從源文件獲得要編碼的內(nèi)容；

%從源文件獲得字符并將它與字典中對象做比較.若有，移向下一位字符；否則，%將它加入到字典中；

4 具體實例分析

根據(jù)已編好的程序，我們對內(nèi)容為：“Lempel-Ziv Coding Simulation Based on Matlab”源文件source.txt執(zhí)行LZ算法得到它的編碼結(jié)果encode.txt為：

〔1〕葉中行.信息論基礎(chǔ)[M].北京：高等教育出版社，2003.

〔2〕陳檢，王鐵丹，侯迪，等.關(guān)于ZL數(shù)據(jù)壓縮算法性能的實驗研究[J].計算機應用,1992(5)：5-8.

〔3〕沈世鎰,吳忠華.信息論基礎(chǔ)與應用[M].北京：高等教育出版社，2004.

〔4〕王忠敏.基于字符串匹配的通用數(shù)據(jù)壓縮算法[J].計算機應用,1995(1),38-40.

〔5〕常炯.信息理論基礎(chǔ)[M].北京:清華大學出版社,1993.

〔6〕張伯雄.數(shù)據(jù)壓縮的原理與實踐[J].微電子學與計算機,1994(5)：35-38.

〔7〕章照止,林須端.信息論與最優(yōu)編碼[M].上海:上海科學技術(shù)出版社,1993.