基于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.