關于LZW算法的改進研究

1、關于LZW算法的改進研究         11-01-09 15:32:00     作者：徐巨峰    編輯：studa090420【摘要】 在分析LZW算法的基礎上，對LZW算法的缺陷進行了探討。并對LZW算法進行了改進，大幅度減少了編碼的長度，降低了匹配長度取值變化的影響，完全兼容LZW算法，在平均壓縮率方面有較大的提高，而且對改進的算法進行了分析論證。 【關鍵詞】  數(shù)據(jù)壓縮  

2、 LZW算法   緩沖區(qū)         LZW算法的實質是無損壓縮技術1-3，LZW算法通過對輸入流進行分析，自適應地生成一個包含輸入流中不重復子串的串表，將每一子串映射為一獨立的碼字輸出。這樣，它就充分利用了相鄰輸入之間的相關性，可以取得超過信源一階熵的編碼效率。然而，受緩存容量、計算復雜度和計算速度等因素的限制，串表的長度受到一定限制，且一般信源所具有的局部平穩(wěn)性隨緩存容量加大，編碼效率提高不大。即：它自身固有一定的缺陷與不足，難以滿足人們的需要，對它進行改進一直成為人

3、們的研究目標之一4-6。為了解決這一問題，本文對LZW算法進行了改進，命名為LZWC編碼算法。它兼有LZW算法的優(yōu)點，還具有自身的優(yōu)越性。首先對LZW算法進行一些必要的介紹和分析。         1. LZW算法         LZW算法1由韋爾奇（T.A.Welch）于1984年通過對LZ算法的改進。開發(fā)出的一種更優(yōu)算法。它是一種基于字典的編碼方法。并且它是LZ系列碼中應用最廣，變形最多的一種算法。LZW壓縮有3個重要的

4、對象：數(shù)據(jù)流、編碼流和編譯表。在編碼時，數(shù)據(jù)流是輸入對象，編碼流就是輸出對象；在解碼時，編碼流則是輸入對象，數(shù)據(jù)流是輸出對象；而編譯表是在編碼和解碼時都需要借助的對象。          1.1LZW算法的編碼原理         LZW算法的編碼原理為：對消息序列xn=x1x2x3xn從左到右進行閱讀，并以此進行LZW編碼：         &#

5、160;(1)對x1顯然是第一次出現(xiàn)，它的前面也沒有字符，那么他的編號是1，它的碼元為(1,0, x1)。          (2)對于x2它可能有兩種情況發(fā)生，即x1=x2或x1x2。對此，有         如果x1=x2，那么對于x2不作編碼，而對x3的編碼位點取2，連接位點則為1，這表示對x3作第二次編碼，它與第一次編碼的x1相連接。       &

6、#160;  如果x1x2，那么x2的編碼位點取為2，連接位點則為0，這表示對x2作第二次編碼，它的前面沒有出現(xiàn)過相同的字符。          (3)依照上述步驟遞推，如果對向量xn=x1x2x3xn，n<m，我們已經得到它的編碼：C=(i,li, xji),i=1,2, , k .         對上式的C滿足的條件:對每一個i有且只有一對(i,li)，使

7、li<i<ji成立。那么C構成一LZW樹。由樹的構造可知，對每個點i，它的枝li是唯一的。因此，樹C的全部枝為li，i=0，1，,k 確定，而且每個li與xn中的子向量xi對應。          (4)如向量xn中的編碼C及相應的樹確定，那么我們就可讀xn+1,xn+2, xn+k,并對它們繼續(xù)進行編碼，如果有一個ik使xi=(xn+1,xn+2, xn+k)成立，而且對任何ik都有：xi( xn+1,xn+2, xn+k，xn+k+1)成立

8、。那么：         不對字符xn+1,xn+2, xn+k進行編碼。         對xn+k+1作它的編碼為（K+1,i, xn+k+1）。         以此類推，就可以完成對xn的編碼C。         2.2 LZW算法的原理 &

9、#160;       LZW算法通過編碼表來組織輸人字符串，并把它們轉換成一定長度的編碼。LZW算法有一個重要的特性稱作前綴性，即如果一個字符串在編碼表上，那它的前綴串也在編碼表上。例如:A、B為兩個不同的字符串，AB組成一新的字符串，A為B的前綴串，如果B在編碼表中，則一定在編碼表中。         LZW通過編碼表識別源輸人字符序列，通過向編碼表中增加新的字符串，從而識別更多、更長的字符序列。但由于前綴性的約束，這種識別一般每次只在原來的

10、基礎上增加一個字符，依次進行。同時，由于編碼算法沒有很強的分析功能，使它不知道哪些字符序列將來出現(xiàn)的概率較大，所以它具有一定的盲目性。例如，有一個長度為n的字符序列，LZW編碼表要完全識別它，則至少需要該序列部分或全部重復出現(xiàn)n次。但是，當一個較長的字符串重復出現(xiàn)兩次，我們就能夠容易識別它，而且這樣的字符串再次出現(xiàn)的概率是非常大的?；谶@樣一種認識，本文在LZW算法的基礎上，構造了一種新的編碼算法，我們把新算法稱為LZWC編碼算法，一般情況下它對數(shù)據(jù)的壓縮率比LZW算法有大幅度提高。新算法在最差的情況下可退化成標準的LZW算法。下面對LZWC算法的原理進行詳細的介紹。   

11、      2  LZWC算法         LZWC算法的基本原理是針對源輸人數(shù)據(jù)中不同特點的數(shù)據(jù)序列，采用不同的編碼器分別編碼。數(shù)據(jù)序列的分類則是根據(jù)它的特點，通過對原始數(shù)據(jù)序列的分析來完成。         LZWC算法共有兩個編碼器，它們是：         (1）&#

12、160;重復編碼器（RepeatCorder），簡稱RC。         (2） LZW編碼器。         RC對輸入流中重復的數(shù)據(jù)進行編碼，剩下的數(shù)據(jù)由則由LZW編碼器進行編碼。RC編碼器和LZW編碼器的編碼通過LZW編碼器的編碼表統(tǒng)一起來。         2.1  LZWC算法的編碼及原理   

13、      LZWC的算法過程如下：         對消息序列xn=x1x2x3xn從左到右進行閱讀，并以此進行LZWC編碼：         (1） 輸入流中的數(shù)據(jù)x1，x2，xn依次經過前緩沖區(qū)。         (4） 假如還有數(shù)據(jù)進入緩沖區(qū)，則轉1），繼續(xù)此過程。 &#

14、160;       (5） 否則，結束編碼過程。         LZWC算法和LZW算法一樣采用編碼表來組織輸入數(shù)據(jù)，顯然LZW的編碼表中包含RC和LZW兩個編碼器編碼的編碼表。我們分別稱其為編碼表中的RC項和LZW項。這兩項雖然對兩個編碼器來說是通用的，但實現(xiàn)時為了提高編碼表的搜索速度，可以把兩者分開處理。         RC的編碼識別很簡單，只在緩

15、沖區(qū)中進行，對于較長的重復字符，這種編碼方式簡便易行，效率較高。         LZW編碼器編碼不連續(xù)的字符，當然是有效的，從而獲得較高的壓縮率。從LZWC編碼過程可以看出，如果RC編碼器在輸入流中找不到滿足條件的字符，則LZW編碼器將獨自編碼輸入數(shù)據(jù)。這時LZWC算法退化為LZW算法。         2.2  LZWC算法的解碼原理       

16、60; LZWC壓縮算法的解碼過程是編碼過程的逆過程，以下是LZWC算法的解碼過程：         (1）讀一個編碼（按LZW方式確定的碼長）；         (2）如果是結束碼，則結束解碼過程；         (3）如果是RC標志的編碼，則按照RC編碼規(guī)則解碼，輸出原始數(shù)據(jù)；      &#

17、160;  (4）否則，按LZW方式解碼；         (5）譯碼過程結束。         2.3  LZWC編碼的算例         下面，我們用一個例子來說明LZWC編碼算的過程。例如：假設信源發(fā)出的序列為：00110000111011100011001解：依題意，有：信源序列的數(shù)據(jù)依次經過前緩沖區(qū)，則 &

18、#160;       (1）RC編碼器對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x1=x2，x2x3，即：0重復出現(xiàn)2次，符合RC編碼的條件，則00的LZWC編碼為（1，2，0）。         (2）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x3=x4，x4x5，1重復出現(xiàn)2次，符合RC編碼的條件，則11的LZWC編碼為（2，2，1）。         (3）RC編碼器繼

19、續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x5=x6，x6=x7，x7=x8，x8x9，0重復出現(xiàn)4次，符合RC編碼的條件，則0000的LZWC編碼為（3，4，0）。         (4）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x9=x10，x10=x11，x11x12，1重復出現(xiàn)3次，符合RC編碼的條件，則111的LZWC編碼為（4，3，1）。         (5）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x12x13，0僅出現(xiàn)1次，

20、不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則0的LZWC編碼為（5，1，0）。         (6）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x13=x14，x14=x15，x15x16，1重復出現(xiàn)3次，符合RC編碼的條件，則111的LZWC編碼為（6，3，1）。         (7）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x16=x17，x17=x18，x18x1

21、9，0重復出現(xiàn)3次，符合RC編碼的條件，則000的LZWC編碼為（7，3，0）。         (8）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x19=x20，x20x21，次，符合RC編碼的條件，則11的LZWC編碼為（8，2，1），1重復出現(xiàn)2次，符合RC編碼的條件，則11的LZWC編碼為（8，2，1）。         (9）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x21=x22，x22x23，次，符合RC編碼的條件，則0

22、0的LZWC編碼為（9，2，0）。         (10）RC編碼器繼續(xù)對進入前緩沖區(qū)的數(shù)據(jù)進行檢測，x23是最后一個數(shù)據(jù)，1僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則1的LZWC編碼為（10，1，1）。         (11）前緩沖區(qū)沒有數(shù)據(jù)通過了，編碼到此結束。        

23、0;所以，信源序列的LZWC編碼為：C=(1，2，0)，(2，2，1)，(3，4，0)，(4，3，1)，(5，1，0)，(6，3，1)，(7，3，0)，(8，2，1)，(9，2，0)，(10，1，1)。      11-01-09 15:32:00     作者：徐巨峰    編輯：studa090420       3  LZWC算法與LZW算法性能的比較   &#

24、160;     壓縮算法性能的比較一般有兩個重要因素，就是平均數(shù)據(jù)壓縮率和壓縮時間。我們從下面例子入手，來討論他們的壓縮性能：         例1：設輸入流為：ababcbabccc         先建立初始化字典，將信源符號a，b，c預置為字典的前3項，編碼位點分別為1，2，3。編碼就從這個初始字典開始。       &

25、#160; 3.1  LZW編碼過程         (1） 由于"a"已經在字典中了，而"ab"不在，輸出"a"的編碼，同時把"ab"添加到字典中，所以字典的第4個條目為"ab"令其編碼位點為4，當前位置前移一位，變?yōu)?，當前字符變?yōu)?quot;b"。它的LZW編碼為（4，1，1）。        

26、; (2） 從輸入流的第1個位置開始，"b"已在字典中了， 而"ba"不在。同理，輸出"b"的編碼，同時把"ba"添加到字典中，編碼位點為5，當前位置變?yōu)?，當前字符為"a"它的LZW編碼為（5，1，2）。         (3） 從輸入流的第2個位置開始，"ab"已在字典中了，而"abc"不在。同理，輸出"ab"的編碼，同時把

27、"abc"添加到字典中，編碼位點為6，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（6，1，4）。         (4） 從輸入流的第3個位置開始，"c"已在字典中了，而"cb"不在。同理，輸出"c"的編碼，同時把"cb"添加到字典中，編碼位點為7，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（7，1，3）。    

28、0;    (5） 從輸入流的第4個位置開始，"ba"已在字典中了，而"bab"不在。同理，輸出"ba"的編碼，同時把"bab"添加到字典中，編碼位點為8，當前位置變?yōu)?，當前字符為"b"。它的LZW編碼為（8，1，5）。         (6） 從輸入流的第5個位置開始，"b"已在字典中了，而"bc"不在。同理，輸出

29、"b"的編碼，同時把"bc"添加到字典中，編碼位點為9，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（9，1，2）。         (7） 從輸入流的第6個位置開始，"c"已在字典中了，而"cc"不在。同理，輸出"c"的編碼，同時把"cc"添加到字典中，編碼位點為10，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（10，1，3）。 &

30、#160;       (8） 從輸入流的第10個位置開始，"cc"已在字典中了，并且沒有別的字符需要編碼了。即，編碼過程到此結束。         所以，它的LZW編碼為：         C=(1，0，1)，(2，0，2)，(3，0，3)，(4，1，1)，(5，1，2)，(6，1，4)，(7，1，3)，(8，1，5)，(9，1，2)，

31、(10，1，3)。         3.2  LZWC編碼過程         (1）由于x1x2，a僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則a的LZWC編碼為（1，1，1）。         (2）由于x2x3，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用

32、RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則b的LZWC編碼為（2，1，2）。         (3）由于x3x4，a僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則a的LZWC編碼為（3，1，1）。         (4）由于x4x5，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由

33、LZW編碼器，則b的LZWC編碼為（4，1，2）。         (5）由于x5x6，c僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則c的LZWC編碼為（5，1，3）。         (6）由于x6x7，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則b的LZWC編碼為（6，1，2）。 &#

34、160;       (7）由于x7x8，a僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則a的LZWC編碼為（7，1，1）。         (8）由于x8x9，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則b的LZWC編碼為（8，1，2）。      

35、   (9）由于x9=x10，x10=x11，c重復出現(xiàn)3次，符合RC編碼的條件，則ccc的LZWC編碼為（9，3，3）。         (10）由于x11是最后一個數(shù)據(jù)，前緩沖區(qū)沒有數(shù)據(jù)通過了，編碼過程到此結束。         C=(1，1，1)，(2，1，2)，(3，1，1)，(4，1，2)，(5，1，3)，(6，1，2)，(7，1，1)，(8，1，2)，(9，3，3)。   &

36、#160;     所以，LZWC算法的平均字符壓縮率較高，壓縮時間較短，較LZW算法有一定的優(yōu)勢。         4  結 論         本文在LZW算法的基礎上，提出了一種改進的算法。命名為LZWC算法，LZWCS算法在壓縮方面比LZW算法有了較大的提高，它適合對文本、     11-01-09 15:32

37、:00     作者：徐巨峰    編輯：studa090420       3  LZWC算法與LZW算法性能的比較         壓縮算法性能的比較一般有兩個重要因素，就是平均數(shù)據(jù)壓縮率和壓縮時間。我們從下面例子入手，來討論他們的壓縮性能：         例1：

38、設輸入流為：ababcbabccc         先建立初始化字典，將信源符號a，b，c預置為字典的前3項，編碼位點分別為1，2，3。編碼就從這個初始字典開始。         3.1  LZW編碼過程         (1） 由于"a"已經在字典中了，而"ab"不在，輸出"a

39、"的編碼，同時把"ab"添加到字典中，所以字典的第4個條目為"ab"令其編碼位點為4，當前位置前移一位，變?yōu)?，當前字符變?yōu)?quot;b"。它的LZW編碼為（4，1，1）。         (2） 從輸入流的第1個位置開始，"b"已在字典中了， 而"ba"不在。同理，輸出"b"的編碼，同時把"ba"添加到字典中，編碼位點為5，當前位置變?yōu)?，當前字符為"a

40、"它的LZW編碼為（5，1，2）。         (3） 從輸入流的第2個位置開始，"ab"已在字典中了，而"abc"不在。同理，輸出"ab"的編碼，同時把"abc"添加到字典中，編碼位點為6，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（6，1，4）。         (4） 從輸入流的第3個位置開

41、始，"c"已在字典中了，而"cb"不在。同理，輸出"c"的編碼，同時把"cb"添加到字典中，編碼位點為7，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（7，1，3）。         (5） 從輸入流的第4個位置開始，"ba"已在字典中了，而"bab"不在。同理，輸出"ba"的編碼，同時把"bab"添加到字典中，編碼位點為

42、8，當前位置變?yōu)?，當前字符為"b"。它的LZW編碼為（8，1，5）。         (6） 從輸入流的第5個位置開始，"b"已在字典中了，而"bc"不在。同理，輸出"b"的編碼，同時把"bc"添加到字典中，編碼位點為9，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（9，1，2）。         (

43、7） 從輸入流的第6個位置開始，"c"已在字典中了，而"cc"不在。同理，輸出"c"的編碼，同時把"cc"添加到字典中，編碼位點為10，當前位置變?yōu)?，當前字符為"c"。它的LZW編碼為（10，1，3）。         (8） 從輸入流的第10個位置開始，"cc"已在字典中了，并且沒有別的字符需要編碼了。即，編碼過程到此結束。     

44、    所以，它的LZW編碼為：         C=(1，0，1)，(2，0，2)，(3，0，3)，(4，1，1)，(5，1，2)，(6，1，4)，(7，1，3)，(8，1，5)，(9，1，2)，(10，1，3)。         3.2  LZWC編碼過程         (1）由于x1x2，a僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則a的LZWC編碼為（1，1，1）。         (2）由于x2x3，b僅出