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

【摘　要】 在分析LZW算法的基礎(chǔ)上，對(duì)LZW算法的缺陷進(jìn)行了探討。并對(duì)LZW算法進(jìn)行了改進(jìn)，大幅度減少了編碼的長(zhǎng)度，降低了匹配長(zhǎng)度取值變化的影響，完全兼容LZW算法，在平均壓縮率方面有較大的提高，而且對(duì)改進(jìn)的算法進(jìn)行了分析論證。
【關(guān)鍵詞】  數(shù)據(jù)壓縮   LZW算法   緩沖區(qū)

        LZW算法的實(shí)質(zhì)是無(wú)損壓縮技術(shù)[1-3]，LZW算法通過(guò)對(duì)輸入流進(jìn)行分析，自適應(yīng)地生成一個(gè)包含輸入流中不重復(fù)子串的串表，將每一子串映射為一獨(dú)立的碼字輸出。這樣，它就充分利用了相鄰輸入之間的相關(guān)性，可以取得超過(guò)信源一階熵的編碼效率。然而，受緩存容量、計(jì)算復(fù)雜度和計(jì)算速度等因素的限制，串表的長(zhǎng)度受到一定限制，且一般信源所具有的局部平穩(wěn)性隨緩存容量加大，編碼效率提高不大。即：它自身固有一定的缺陷與不足，難以滿(mǎn)足人們的需要，對(duì)它進(jìn)行改進(jìn)一直成為人們的研究目標(biāo)之一[4-6]。為了解決這一問(wèn)題，本文對(duì)LZW算法進(jìn)行了改進(jìn)，命名為L(zhǎng)ZWC編碼算法。它兼有LZW算法的優(yōu)點(diǎn)，還具有自身的優(yōu)越性。首先對(duì)LZW算法進(jìn)行一些必要的介紹和分析。
        1. LZW算法
        LZW算法[1]由韋爾奇（T.A.Welch）于1984年通過(guò)對(duì)LZ算法的改進(jìn)。開(kāi)發(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算法的編碼原理
        LZW算法的編碼原理為：對(duì)消息序列xn=x1x2x3…xn從左到右進(jìn)行閱讀，并以此進(jìn)行LZW編碼： 
        (1)對(duì)x1顯然是第一次出現(xiàn)，它的前面也沒(méi)有字符，那么他的編號(hào)是1，它的碼元為(1,0, x1)。 
        (2)對(duì)于x2它可能有兩種情況發(fā)生，即x1=x2或x1≠x2。對(duì)此，有
        ①如果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作第二次編碼，它的前面沒(méi)有出現(xiàn)過(guò)相同的字符。 
        (3)依照上述步驟遞推，如果對(duì)向量xn=x1x2x3…xn，n<m，我們已經(jīng)得到它的編碼：C={(i,li, xji),i=1,2, …, k }.
        對(duì)上式的C滿(mǎn)足的條件:對(duì)每一個(gè)i有且只有一對(duì)(i,li)，使li<i<ji成立。那么C構(gòu)成一LZW樹(shù)。由樹(shù)的構(gòu)造可知，對(duì)每個(gè)點(diǎn)i，它的枝li是唯一的。因此，樹(shù)C的全部枝為li，i=0，1，…,k 確定，而且每個(gè)li與xn中的子向量xαi對(duì)應(yīng)。 
        (4)如向量xn中的編碼C及相應(yīng)的樹(shù)確定，那么我們就可讀xn+1,xn+2,…, xn+k,并對(duì)它們繼續(xù)進(jìn)行編碼，如果有一個(gè)i≦k使xαi=(xn+1,xn+2,…, xn+k)成立，而且對(duì)任何i≦k都有：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, xn+k+1）。
        以此類(lèi)推，就可以完成對(duì)xn的編碼C。
        2.2 LZW算法的原理
        LZW算法通過(guò)編碼表來(lái)組織輸人字符串，并把它們轉(zhuǎn)換成一定長(zhǎng)度的編碼。LZW算法有一個(gè)重要的特性稱(chēng)作前綴性，即如果一個(gè)字符串在編碼表上，那它的前綴串也在編碼表上。例如:A、B為兩個(gè)不同的字符串，AB組成一新的字符串，A為B的前綴串，如果B在編碼表中，則一定在編碼表中。
        LZW通過(guò)編碼表識(shí)別源輸人字符序列，通過(guò)向編碼表中增加新的字符串，從而識(shí)別更多、更長(zhǎng)的字符序列。但由于前綴性的約束，這種識(shí)別一般每次只在原來(lái)的基礎(chǔ)上增加一個(gè)字符，依次進(jìn)行。同時(shí)，由于編碼算法沒(méi)有很強(qiáng)的分析功能，使它不知道哪些字符序列將來(lái)出現(xiàn)的概率較大，所以它具有一定的盲目性。例如，有一個(gè)長(zhǎng)度為n的字符序列，LZW編碼表要完全識(shí)別它，則至少需要該序列部分或全部重復(fù)出現(xiàn)n次。但是，當(dāng)一個(gè)較長(zhǎng)的字符串重復(fù)出現(xiàn)兩次，我們就能夠容易識(shí)別它，而且這樣的字符串再次出現(xiàn)的概率是非常大的�；�于這樣一種認(rèn)識(shí)，本文在LZW算法的基礎(chǔ)上，構(gòu)造了一種新的編碼算法，我們把新算法稱(chēng)為L(zhǎng)ZWC編碼算法，一般情況下它對(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ù)序列的分類(lèi)則是根據(jù)它的特點(diǎn)，通過(guò)對(duì)原始數(shù)據(jù)序列的分析來(lái)完成。
        LZWC算法共有兩個(gè)編碼器，它們是：
        (1） 重復(fù)編碼器（RepeatCorder），簡(jiǎn)稱(chēng)RC。
        (2） LZW編碼器。
        RC對(duì)輸入流中重復(fù)的數(shù)據(jù)進(jìn)行編碼，剩下的數(shù)據(jù)由則由LZW編碼器進(jìn)行編碼。RC編碼器和LZW編碼器的編碼通過(guò)LZW編碼器的編碼表統(tǒng)一起來(lái)。
        2.1  LZWC算法的編碼及原理
        LZWC的算法過(guò)程如下：
        對(duì)消息序列xn=x1x2x3…xn從左到右進(jìn)行閱讀，并以此進(jìn)行LZWC編碼：
        (1） 輸入流中的數(shù)據(jù)x1，x2，…，xn依次經(jīng)過(guò)前緩沖區(qū)。
        (4） 假如還有數(shù)據(jù)進(jìn)入緩沖區(qū)，則轉(zhuǎn)1），繼續(xù)此過(guò)程。
        (5） 否則，結(jié)束編碼過(guò)程。 
        LZWC算法和LZW算法一樣采用編碼表來(lái)組織輸入數(shù)據(jù)，顯然LZW的編碼表中包含RC和LZW兩個(gè)編碼器編碼的編碼表。我們分別稱(chēng)其為編碼表中的RC項(xiàng)和LZW項(xiàng)。這兩項(xiàng)雖然對(duì)兩個(gè)編碼器來(lái)說(shuō)是通用的，但實(shí)現(xiàn)時(shí)為了提高編碼表的搜索速度，可以把兩者分開(kāi)處理。
        RC的編碼識(shí)別很簡(jiǎn)單，只在緩沖區(qū)中進(jìn)行，對(duì)于較長(zhǎng)的重復(fù)字符，這種編碼方式簡(jiǎn)便易行，效率較高。
        LZW編碼器編碼不連續(xù)的字符，當(dāng)然是有效的，從而獲得較高的壓縮率。從LZWC編碼過(guò)程可以看出，如果RC編碼器在輸入流中找不到滿(mǎn)足條件的字符，則LZW編碼器將獨(dú)自編碼輸入數(shù)據(jù)。這時(shí)LZWC算法退化為L(zhǎng)ZW算法。
        2.2  LZWC算法的解碼原理
        LZWC壓縮算法的解碼過(guò)程是編碼過(guò)程的逆過(guò)程，以下是LZWC算法的解碼過(guò)程：
        (1）讀一個(gè)編碼（按LZW方式確定的碼長(zhǎng)）；
        (2）如果是結(jié)束碼，則結(jié)束解碼過(guò)程；
        (3）如果是RC標(biāo)志的編碼，則按照RC編碼規(guī)則解碼，輸出原始數(shù)據(jù)；
        (4）否則，按LZW方式解碼；
        (5）譯碼過(guò)程結(jié)束。
        2.3  LZWC編碼的算例
        下面，我們用一個(gè)例子來(lái)說(shuō)明LZWC編碼算的過(guò)程。例如：假設(shè)信源發(fā)出的序列為：00110000111011100011001解：依題意，有：信源序列的數(shù)據(jù)依次經(jīng)過(guò)前緩沖區(qū)，則
        (1）RC編碼器對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x1=x2，x2≠x3，即：0重復(fù)出現(xiàn)2次，符合RC編碼的條件，則00的LZWC編碼為（1，2，0）。
        (2）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x3=x4，x4≠x5，1重復(fù)出現(xiàn)2次，符合RC編碼的條件，則11的LZWC編碼為（2，2，1）。
        (3）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x5=x6，x6=x7，x7=x8，x8≠x9，0重復(fù)出現(xiàn)4次，符合RC編碼的條件，則0000的LZWC編碼為（3，4，0）。
        (4）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x9=x10，x10=x11，x11≠x12，1重復(fù)出現(xiàn)3次，符合RC編碼的條件，則111的LZWC編碼為（4，3，1）。
        (5）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x12≠x13，0僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則0的LZWC編碼為（5，1，0）。
        (6）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x13=x14，x14=x15，x15≠x16，1重復(fù)出現(xiàn)3次，符合RC編碼的條件，則111的LZWC編碼為（6，3，1）。
        (7）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x16=x17，x17=x18，x18≠x19，0重復(fù)出現(xiàn)3次，符合RC編碼的條件，則000的LZWC編碼為（7，3，0）。
        (8）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x19=x20，x20≠x21，次，符合RC編碼的條件，則11的LZWC編碼為（8，2，1），1重復(fù)出現(xiàn)2次，符合RC編碼的條件，則11的LZWC編碼為（8，2，1）。
        (9）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x21=x22，x22≠x23，次，符合RC編碼的條件，則00的LZWC編碼為（9，2，0）。
        (10）RC編碼器繼續(xù)對(duì)進(jìn)入前緩沖區(qū)的數(shù)據(jù)進(jìn)行檢測(cè)，x23是最后一個(gè)數(shù)據(jù)，1僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則1的LZWC編碼為（10，1，1）。
        (11）前緩沖區(qū)沒(méi)有數(shù)據(jù)通過(guò)了，編碼到此結(jié)束。
        所以，信源序列的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)}。

       3  LZWC算法與LZW算法性能的比較
        壓縮算法性能的比較一般有兩個(gè)重要因素，就是平均數(shù)據(jù)壓縮率和壓縮時(shí)間。我們從下面例子入手，來(lái)討論他們的壓縮性能：
        例1：設(shè)輸入流為：ababcbabccc
        先建立初始化字典，將信源符號(hào)a，b，c預(yù)置為字典的前3項(xiàng)，編碼位點(diǎn)分別為1，2，3。編碼就從這個(gè)初始字典開(kāi)始。
        3.1  LZW編碼過(guò)程
        (1） 由于"a"已經(jīng)在字典中了，而"ab"不在，輸出"a"的編碼，同時(shí)把"ab"添加到字典中，所以字典的第4個(gè)條目為"ab"令其編碼位點(diǎn)為4，當(dāng)前位置前移一位，變?yōu)?，當(dāng)前字符變?yōu)?quot;b"。它的LZW編碼為（4，1，1）。
        (2） 從輸入流的第1個(gè)位置開(kāi)始，"b"已在字典中了，
而"ba"不在。同理，輸出"b"的編碼，同時(shí)把"ba"添加到字典中，編碼位點(diǎn)為5，當(dāng)前位置變?yōu)?，當(dāng)前字符為"a"它的LZW編碼為（5，1，2）。
        (3） 從輸入流的第2個(gè)位置開(kāi)始，"ab"已在字典中了，而"abc"不在。同理，輸出"ab"的編碼，同時(shí)把"abc"添加到字典中，編碼位點(diǎn)為6，當(dāng)前位置變?yōu)?，當(dāng)前字符為"c"。它的LZW編碼為（6，1，4）。
        (4） 從輸入流的第3個(gè)位置開(kāi)始，"c"已在字典中了，而"cb"不在。同理，輸出"c"的編碼，同時(shí)把"cb"添加到字典中，編碼位點(diǎn)為7，當(dāng)前位置變?yōu)?，當(dāng)前字符為"c"。它的LZW編碼為（7，1，3）。
        (5） 從輸入流的第4個(gè)位置開(kāi)始，"ba"已在字典中了，而"bab"不在。同理，輸出"ba"的編碼，同時(shí)把"bab"添加到字典中，編碼位點(diǎn)為8，當(dāng)前位置變?yōu)?，當(dāng)前字符為"b"。它的LZW編碼為（8，1，5）。
        (6） 從輸入流的第5個(gè)位置開(kāi)始，"b"已在字典中了，而"bc"不在。同理，輸出"b"的編碼，同時(shí)把"bc"添加到字典中，編碼位點(diǎn)為9，當(dāng)前位置變?yōu)?，當(dāng)前字符為"c"。它的LZW編碼為（9，1，2）。
        (7） 從輸入流的第6個(gè)位置開(kāi)始，"c"已在字典中了，而"cc"不在。同理，輸出"c"的編碼，同時(shí)把"cc"添加到字典中，編碼位點(diǎn)為10，當(dāng)前位置變?yōu)?，當(dāng)前字符為"c"。它的LZW編碼為（10，1，3）。
        (8） 從輸入流的第10個(gè)位置開(kāi)始，"cc"已在字典中了，并且沒(méi)有別的字符需要編碼了。即，編碼過(guò)程到此結(jié)束。
        所以，它的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編碼過(guò)程
        (1）由于x1≠x2，a僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則a的LZWC編碼為（1，1，1）。
        (2）由于x2≠x3，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則b的LZWC編碼為（2，1，2）。
        (3）由于x3≠x4，a僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則a的LZWC編碼為（3，1，1）。
        (4）由于x4≠x5，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則b的LZWC編碼為（4，1，2）。
        (5）由于x5≠x6，c僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則c的LZWC編碼為（5，1，3）。
        (6）由于x6≠x7，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則b的LZWC編碼為（6，1，2）。
        (7）由于x7≠x8，a僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則a的LZWC編碼為（7，1，1）。
        (8）由于x8≠x9，b僅出現(xiàn)1次，不符合RC編碼的條件，所以，不能用RC編碼器對(duì)其進(jìn)行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則b的LZWC編碼為（8，1，2）。
        (9）由于x9=x10，x10=x11，c重復(fù)出現(xiàn)3次，符合RC編碼的條件，則ccc的LZWC編碼為（9，3，3）。
        (10）由于x11是最后一個(gè)數(shù)據(jù)，前緩沖區(qū)沒(méi)有數(shù)據(jù)通過(guò)了，編碼過(guò)程到此結(jié)束。
        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)}。
        所以，LZWC算法的平均字符壓縮率較高，壓縮時(shí)間較短，較LZW算法有一定的優(yōu)勢(shì)。
        4  結(jié) 論
        本文在LZW算法的基礎(chǔ)上，提出了一種改進(jìn)的算法。命名為L(zhǎng)ZWC算法，LZWCS算法在壓縮方面比LZW算法有了較大的提高，它適合對(duì)文本、字符、數(shù)據(jù)等類(lèi)型的文件進(jìn)行壓縮。對(duì)于重復(fù)字符很少的輸入流，新算法和LZW算法的壓縮效果差別不大。但是，對(duì)于重復(fù)字符較多的輸入流，新算法壓縮效果的優(yōu)勢(shì)十分明顯。但由于新算法兼容LZW算法，所以，它在應(yīng)用中比單純的LZW算法具有更好的性能。

參考文獻(xiàn)
[1] 姜  丹.信息論與編碼[M].合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,2001.
[2] 張鳳林,劉思峰. LZW*:一個(gè)改進(jìn)的LZW數(shù)據(jù)壓縮算法[J]. 小型微型計(jì)算機(jī)系統(tǒng).2006,27（10）1897-1899 
[3] 吳宇新,余松煌.對(duì) LZW 算法的改進(jìn)及其在圖像無(wú)損壓縮中的應(yīng)用[J].上海交通大學(xué)學(xué)報(bào), 1998,3 (29): 110-113 
[4] 卓  越, 楊長(zhǎng)生, 宋廣華.一種基于自適應(yīng)字典的通用無(wú)損壓縮算法[J]. 計(jì)算機(jī)工程, 2001, 27(2): 149-151
[5] David Salomon. Data Compression: The Complete Reference [M].Springer-Verlag New York Inc.,200

【LZW算法的改進(jìn)研究】相關(guān)文章：

入侵檢測(cè)模式匹配算法的研究與改進(jìn)03-29

一種改進(jìn)的粒子濾波算法的研究03-07

一種改進(jìn)的無(wú)線(xiàn)鏈路調(diào)度算法研究03-07

改進(jìn)logit多路徑分配模型及其求解算法研究03-07

基于信道估計(jì)的改進(jìn)單載波頻域塊LMS算法研究03-05

藍(lán)牙的信息安全機(jī)制及密鑰算法改進(jìn)03-18

計(jì)數(shù)查找算法的研究11-22

BP算法在矩陣分析基礎(chǔ)上的改進(jìn)03-07

LDPC碼譯碼算法研究03-07