關(guān)于LZW算法的改進(jìn)研究

1、關(guān)于lzw算法的改進(jìn)研究文章來源 畢業(yè)論文網(wǎng) 【摘要】 在分析lzw算法的基礎(chǔ)上，對(duì)lzw算法的缺陷進(jìn)行了探討。并對(duì)lzw算法進(jìn)行了改進(jìn)，大幅度減少了編碼的長度，降低了匹配長度取值變化的影響，完全兼容lzw算法，在平均壓縮率方面有較大的提高，而且對(duì)改進(jìn)的算法進(jìn)行了分析論證。 【關(guān)鍵詞】  數(shù)據(jù)壓縮   lzw算法   緩沖區(qū)        lzw算法的實(shí)質(zhì)是無損壓縮技術(shù)1-3，lzw算法通過對(duì)輸入流進(jìn)行分析，自適應(yīng)地生成一個(gè)包含輸入

2、流中不重復(fù)子串的串表，將每一子串映射為一獨(dú)立的碼字輸出。這樣，它就充分利用了相鄰輸入之間的相關(guān)性，可以取得超過信源一階熵的編碼效率。然而，受緩存容量、計(jì)算復(fù)雜度和計(jì)算速度等因素的限制，串表的長度受到一定限制，且一般信源所具有的局部平穩(wěn)性隨緩存容量加大，編碼效率提高不大。即：它自身固有一定的缺陷與不足，難以滿足人們的需要，對(duì)它進(jìn)行改進(jìn)一直成為人們的研究目標(biāo)之一4-6。為了解決這一問題，本文對(duì)lzw算法進(jìn)行了改進(jìn)，命名為lzwc編碼算法。它兼有l(wèi)zw算法的優(yōu)點(diǎn)，還具有自身的優(yōu)越性。首先對(duì)lzw算法進(jìn)行一些必要的介紹和分析。       &

3、nbsp; 1. lzw算法         lzw算法1由韋爾奇（t.a.welch）于1984年通過對(duì)lz算法的改進(jìn)。開發(fā)出的一種更優(yōu)算法。它是一種基于字典的編碼方法。并且它是lz系列碼中應(yīng)用最廣，變形最多的一種算法。lzw壓縮有3個(gè)重要的對(duì)象：數(shù)據(jù)流、編碼流和編譯表。在編碼時(shí)，數(shù)據(jù)流是輸入對(duì)象，編碼流就是輸出對(duì)象；在解碼時(shí)，編碼流則是輸入對(duì)象，數(shù)據(jù)流是輸出對(duì)象；而編譯表是在編碼和解碼時(shí)都需要借助的對(duì)象。          1.1lzw算法的

4、編碼原理         lzw算法的編碼原理為：對(duì)消息序列xn=x1x2x3…xn從左到右進(jìn)行閱讀，并以此進(jìn)行l(wèi)zw編碼：          (1)對(duì)x1顯然是第一次出現(xiàn)，它的前面也沒有字符，那么他的編號(hào)是1，它的碼元為(1,0, x1)。          (2)對(duì)于x2它可能有兩種情況發(fā)生，即x1=x2或x1≠x2。對(duì)此，有  &n

5、bsp;      如果x1=x2，那么對(duì)于x2不作編碼，而對(duì)x3的編碼位點(diǎn)取2，連接位點(diǎn)則為1，這表示對(duì)x3作第二次編碼，它與第一次編碼的x1相連接。          如果x1≠x2，那么x2的編碼位點(diǎn)取為2，連接位點(diǎn)則為0，這表示對(duì)x2作第二次編碼，它的前面沒有出現(xiàn)過相同的字符。          (3)依照上述步驟遞推，如果對(duì)向量xn=x1x2x3…xn，n&

6、lt;m，我們已經(jīng)得到它的編碼：c=(i,li, xji),i=1,2, …, k .         對(duì)上式的c滿足的條件:對(duì)每一個(gè)i有且只有一對(duì)(i,li)，使li<i<ji成立。那么c構(gòu)成一lzw樹。由樹的構(gòu)造可知，對(duì)每個(gè)點(diǎn)i，它的枝li是唯一的。因此，樹c的全部枝為li，i=0，1，…,k 確定，而且每個(gè)li與xn中的子向量xαi對(duì)應(yīng)。          (4)如向量xn中的編碼c及相應(yīng)

7、的樹確定，那么我們就可讀xn+1,xn+2,…, xn+k,并對(duì)它們繼續(xù)進(jìn)行編碼，如果有一個(gè)ik使xαi=(xn+1,xn+2,…, xn+k)成立，而且對(duì)任何ik都有：xαi≠( xn+1,xn+2,…, xn+k，xn+k+1)成立。那么：         不對(duì)字符xn+1,xn+2,…, xn+k進(jìn)行編碼。         對(duì)xn+k+1作它的編碼為（k+1,i,

8、xn+k+1）。         以此類推，就可以完成對(duì)xn的編碼c。         2.2 lzw算法的原理         lzw算法通過編碼表來組織輸人字符串，并把它們轉(zhuǎn)換成一定長度的編碼。lzw算法有一個(gè)重要的特性稱作前綴性，即如果一個(gè)字符串在編碼表上，那它的前綴串也在編碼表上。例如:a、b為兩個(gè)不同的字符串，ab組成一新的字符串，a為b的前綴串，如果b在編碼表中，則一定在編碼

9、表中。         lzw通過編碼表識(shí)別源輸人字符序列，通過向編碼表中增加新的字符串，從而識(shí)別更多、更長的字符序列。但由于前綴性的約束，這種識(shí)別一般每次只在原來的基礎(chǔ)上增加一個(gè)字符，依次進(jìn)行。同時(shí)，由于編碼算法沒有很強(qiáng)的分析功能，使它不知道哪些字符序列將來出現(xiàn)的概率較大，所以它具有一定的盲目性。例如，有一個(gè)長度為n的字符序列，lzw編碼表要完全識(shí)別它，則至少需要該序列部分或全部重復(fù)出現(xiàn)n次。但是，當(dāng)一個(gè)較長的字符串重復(fù)出現(xiàn)兩次，我們就能夠容易識(shí)別它，而且這樣的字符串再次出現(xiàn)的概率是非常大的。基于這樣一種認(rèn)識(shí)，本文在lzw

10、算法的基礎(chǔ)上，構(gòu)造了一種新的編碼算法，我們把新算法稱為lzwc編碼算法，一般情況下它對(duì)數(shù)據(jù)的壓縮率比lzw算法有大幅度提高。新算法在最差的情況下可退化成標(biāo)準(zhǔn)的lzw算法。下面對(duì)lzwc算法的原理進(jìn)行詳細(xì)的介紹。         2  lzwc算法         lzwc算法的基本原理是針對(duì)源輸人數(shù)據(jù)中不同特點(diǎn)的數(shù)據(jù)序列，采用不同的編碼器分別編碼。數(shù)據(jù)序列的分類則是根據(jù)它的特點(diǎn)，通過對(duì)原始數(shù)據(jù)序列的分析來完成。    

11、;     lzwc算法共有兩個(gè)編碼器，它們是：         (1） 重復(fù)編碼器（repeatcorder），簡稱rc。         (2） lzw編碼器。         rc對(duì)輸入流中重復(fù)的數(shù)據(jù)進(jìn)行編碼，剩下的數(shù)據(jù)由則由lzw編碼器進(jìn)行編碼。rc編碼器和lzw編碼器的編碼通過lzw編碼器的編碼表統(tǒng)一起來。         2.1  lzwc算法的編碼及原理         lzwc的算法過程如下：         對(duì)消息序列xn=x1x2x3…xn從左到右進(jìn)行閱讀，并以此進(jìn)行l(wèi)zwc編碼：