基于MATLAB的Lemple-Ziv編碼仿真

常金勇，李海增，宋永任

（長(zhǎng)治學(xué)院 數(shù)學(xué)系，山西 長(zhǎng)治 046011）

1 引言

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

2 LZ算法

2.1 LZ算法簡(jiǎn)介

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

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

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

②L是使①成立的最大可能的匹配長(zhǎng)度；

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

2.3 LZ算法的缺點(diǎn)

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

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

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

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

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

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

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

4 具體實(shí)例分析

根據(jù)已編好的程序，我們對(duì)內(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ù)壓縮算法性能的實(shí)驗(yàn)研究[J].計(jì)算機(jī)應(yīng)用,1992(5)：5-8.

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

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

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

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

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