【摘 要】 在分析LZW算法的基礎上，對LZW算法的缺陷進行了探討。並對LZW算法進行了改進，大幅度減少了編碼的長度，降低了匹配長度取值變化的影響，完全相容LZW算法，在平均壓縮率方面有較大的提高，而且對改進的算法進行了分析論證。
【關鍵詞】 數據壓縮 LZW算法 緩衝區
LZW算法的實質是無損壓縮技術[1-3]，LZW算法透過對輸入流進行分析，自適應地生成一個包含輸入流中不重複子串的串表，將每一子串映射爲一獨立的碼字輸出。這樣，它就充分利用了相鄰輸入之間的相關性，可以取得超過信源一階熵的編碼效率。然而，受快取容量、計算複雜度和計算速度等因素的限制，串表的長度受到一定限制，且一般信源所具有的局部平穩性隨快取容量加大，編碼效率提高不大。即：它自身固有一定的缺陷與不足，難以滿足人們的需要，對它進行改進一直成爲人們的研究目標之一[4-6]。爲了解決這一問題，本文對LZW算法進行了改進，命名爲LZWC編碼算法。它兼有LZW算法的優點，還具有自身的優越性。首先對LZW算法進行一些必要的介紹和分析。
1. LZW算法
LZW算法[1]由韋爾奇（h）於1984年透過對LZ算法的改進。開發出的一種更優算法。它是一種基於字典的編碼方法。並且它是LZ系列碼中應用最廣，變形最多的一種算法。LZW壓縮有3個重要的對象：數據流、編碼流和編譯表。在編碼時，數據流是輸入對象，編碼流就是輸出對象；在解碼時，編碼流則是輸入對象，數據流是輸出對象；而編譯表是在編碼和解碼時都需要藉助的對象。
1.1LZW算法的編碼原理
LZW算法的編碼原理爲：對消息序列xn=x1x2x3…xn從左到右進行閱讀，並以此進行LZW編碼：
(1)對x1顯然是第一次出現，它的前面也沒有字元，那麼他的編號是1，它的碼元爲(1,0, x1)。
(2)對於x2它可能有兩種情況發生，即x1=x2或x1≠x2。對此，有
①如果x1=x2，那麼對於x2不作編碼，而對x3的編碼位點取2，連接位點則爲1，這表示對x3作第二次編碼，它與第一次編碼的x1相連接。
②如果x1≠x2，那麼x2的編碼位點取爲2，連接位點則爲0，這表示對x2作第二次編碼，它的前面沒有出現過相同的字元。
(3)依照上述步驟遞推，如果對向量xn=x1x2x3…xn，n<m，我們已經得到它的編碼：C={(i,li, xji),i=1,2, …, k }.
對上式的C滿足的條件:對每一個i有且只有一對(i,li)，使li<i<ji成立。那麼C構成一LZW樹。由樹的構造可知，對每個點i，它的枝li是唯一的。因此，樹C的全部枝爲li，i=0，1，…,k 確定，而且每個li與xn中的子向量xαi對應。
(4)如向量xn中的編碼C及相應的樹確定，那麼我們就可讀xn+1,xn+2,…, xn+k,並對它們繼續進行編碼，如果有一個i≦k使xαi=(xn+1,xn+2,…, xn+k)成立，而且對任何i≦k都有：xαi≠( xn+1,xn+2,…, xn+k，xn+k+1)成立。那麼：
①不對字元xn+1,xn+2,…, xn+k進行編碼。
②對xn+k+1作它的編碼爲（K+1,i, xn+k+1）。
以此類推，就可以完成對xn的編碼C。
2.2 LZW算法的原理
LZW算法透過編碼表來組織輸人字元串，並把它們轉換成一定長度的編碼。LZW算法有一個重要的特性稱作前綴性，即如果一個字元串在編碼表上，那它的前綴串也在編碼表上。例如:A、B爲兩個不同的字元串，AB組成一新的字元串，A爲B的前綴串，如果B在編碼表中，則一定在編碼表中。
LZW透過編碼表識別源輸人字元序列，透過向編碼表中增加新的字元串，從而識別更多、更長的字元序列。但由於前綴性的約束，這種識別一般每次只在原來的基礎上增加一個字元，依次進行。同時，由於編碼算法沒有很強的分析功能，使它不知道哪些字元序列將來出現的概率較大，所以它具有一定的盲目性。例如，有一個長度爲n的字元序列，LZW編碼表要完全識別它，則至少需要該序列部分或全部重複出現n次。但是，當一個較長的字元串重複出現兩次，我們就能夠容易識別它，而且這樣的字元串再次出現的概率是非常大的。基於這樣一種認識，本文在LZW算法的基礎上，構造了一種新的編碼算法，我們把新算法稱爲LZWC編碼算法，一般情況下它對數據的壓縮率比LZW算法有大幅度提高。新算法在最差的情況下可退化成標準的LZW算法。下面對LZWC算法的原理進行詳細的介紹。
2 LZWC算法
LZWC算法的基本原理是針對源輸人數據中不同特點的數據序列，採用不同的編碼器分別編碼。數據序列的分類則是根據它的特點，透過對原始數據序列的分析來完成。
LZWC算法共有兩個編碼器，它們是：
(1） 重複編碼器（RepeatCorder），簡稱RC。
(2） LZW編碼器。
RC對輸入流中重複的數據進行編碼，剩下的數據由則由LZW編碼器進行編碼。RC編碼器和LZW編碼器的.編碼透過LZW編碼器的編碼表統一起來。
2.1 LZWC算法的編碼及原理
LZWC的算法過程如下：
對消息序列xn=x1x2x3…xn從左到右進行閱讀，並以此進行LZWC編碼：
(1） 輸入流中的數據x1，x2，…，xn依次經過前緩衝區。
(4） 假如還有數據進入緩衝區，則轉1），繼續此過程。
(5） 否則，結束編碼過程。