數(shù)據(jù)壓縮可分成兩種類型，一種叫做無損壓縮，另一種叫做有損壓縮。
　　無損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。一個(gè)很常見的例子是磁盤文件的壓縮。根據(jù)目前的技術(shù)水平，無損壓縮算法一般可以把普通文件的數(shù)據(jù)壓縮到原來的1/2～1/4。一些常用的無損壓縮算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)壓縮算法。
　　有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。例如，圖像和聲音的壓縮就可以采用有損壓縮，因?yàn)槠渲邪臄?shù)據(jù)往往多于我們的視覺系統(tǒng)和聽覺系統(tǒng)所能接收的信息，丟掉一些數(shù)據(jù)而不至于對(duì)聲音或者圖像所表達(dá)的意思產(chǎn)生誤解，但可大大提高壓縮比。
　　本章主要介紹目前用得最多和技術(shù)最成熟的無損壓縮編碼技術(shù)，包括包含霍夫曼編碼、算術(shù)編碼、RLE編碼和詞典編碼。對(duì)于不打算開發(fā)壓縮技術(shù)和編寫壓縮程序的讀者可不必深究編譯碼的詳細(xì)過程。

4.1 香農(nóng)-范諾與霍夫曼編碼

4.1.1香農(nóng)-范諾編碼

　　香農(nóng)-范諾編碼算法需要用到下面兩個(gè)基本概念：
　　1、Entropy(熵)的概念
　　1）熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，數(shù)學(xué)上就是概率越小。
　　2）某個(gè)事件的信息量用I_i=-log₂P_i表示， 其中p_i為第i個(gè)事件的概率，0<P_i≤1 
　　2、信源S的熵的定義
　　按照仙農(nóng)(Shannon)的理論，信源S的熵定義為
　　　H(S) = η = ∑_i P_ilog₂(1/P_i)
　　其中P_i是符號(hào)S_i在S中出現(xiàn)的概率；log₂(1/P_i)表示包含在S_i中的信息量，也就是編碼S_i所需要的位數(shù)。例如，一幅用256級(jí)灰度表示的圖像，如果每一個(gè)象素點(diǎn)灰度的概率均為P_i=1/256，編碼每一個(gè)象素點(diǎn)就需要8位。
　　[例4.1] 有一幅40個(gè)象素組成的灰度圖像，灰度共有5級(jí)，分別用符號(hào)A、B、C、D和E表示，40個(gè)象素中出現(xiàn)灰度A的象素?cái)?shù)有15個(gè)，出現(xiàn)灰度B的象素?cái)?shù)有7個(gè)，出現(xiàn)灰度C的象素?cái)?shù)有7個(gè)等等，如表4-01所示。如果用3個(gè)位表示5個(gè)等級(jí)的灰度值，也就是每個(gè)象素用3位表示，編碼這幅圖像總共需要120位。

表4-01 符號(hào)在圖像中出現(xiàn)的數(shù)目

　　按照仙農(nóng)理論，這幅圖像的熵為
　　H(S) = (15/40) ′ log₂(40/15) + (7/40) ′ log₂(40/7) + ? ? ? + (5/40 ′ log₂(40/5) =2.196
這就是說每個(gè)符號(hào)用2.196位表示，40個(gè)象素需用87.84位。
　　最早闡述和實(shí)現(xiàn)這種編碼的是Shannon(1948年)和Fano(1949年)，因此被稱為仙農(nóng)-范諾(Shannon-Fano)算法。這種方法采用從上到下的方法進(jìn)行編碼。首先按照符號(hào)出現(xiàn)的頻度或概率排序，例如，A，B，C，D和E，如表4-02所示。然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)，如圖4-01所示。按照這種方法進(jìn)行編碼得到的總位數(shù)為91。壓縮比約為1.3 : 1。

表4-02 Shannon-Fano算法舉例表

圖4-01 香農(nóng)-范諾算法編碼舉例

　　霍夫曼(Huffman)在1952年提出了另一種編碼方法，即從下到上的編碼方法。現(xiàn)仍以一個(gè)具體的例子說明它的編碼步驟：
　　1、初始化，根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序，如表4-03和圖4-02所示。
　　2、把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)，如圖4-02中的D和E組成節(jié)點(diǎn)P1。
　　3、重復(fù)步驟2，得到節(jié)點(diǎn)P2、P3和P4，形成一棵“樹”，其中的P4稱為根節(jié)點(diǎn)。
　　4、從根節(jié)點(diǎn)P4開始到相應(yīng)于每個(gè)符號(hào)的“樹葉”，從上到下標(biāo)上“0”(上枝)或者“1”(下枝)，至于哪個(gè)為“1”哪個(gè)為“0”則無關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長(zhǎng)度是相同的。
　　5、從根節(jié)點(diǎn)P4開始順著樹枝到每個(gè)葉子分別寫出每個(gè)符號(hào)的代碼，如表4-03所示。
　　6、按照仙農(nóng)理論，這幅圖像的熵為
　　　H(S)＝(15/39)′ log₂(39/15) + (7/39)′ log₂(39/7) + ? ? ? + (5/39)′ log₂(39/5)＝ 2.1859log₂ 壓縮比1.37:1。

表4-03 霍夫曼編碼舉例

圖4-02 霍夫曼編碼方法

　　霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加同步代碼。例如，碼串中的第1位為0，那末肯定是符號(hào)A，因?yàn)楸硎酒渌?hào)的代碼沒有一個(gè)是以0開始的，因此下一位就表示下一個(gè)符號(hào)代碼的第1位。同樣，如果出現(xiàn)“110”，那么它就代表符號(hào)D。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個(gè)碼一個(gè)碼地依次進(jìn)行譯碼。
　　采用霍夫曼編碼時(shí)有兩個(gè)問題值得注意：①霍夫曼碼沒有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。但如果碼串中有錯(cuò)誤，哪僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是一錯(cuò)一大串，全亂了套，這種現(xiàn)象稱為錯(cuò)誤傳播(error propagation)。計(jì)算機(jī)對(duì)這種錯(cuò)誤也無能為力，說不出錯(cuò)在哪里，更談不上去糾正它。②霍夫曼碼是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲(chǔ)代碼之前加以考慮。盡管如此，霍夫曼碼還是得到廣泛應(yīng)用。
　　與仙農(nóng)-范諾編碼相比，這兩種方法都自含同步碼，在編碼之后的碼串中都不須要另外添加標(biāo)記符號(hào)，即在譯碼時(shí)分割符號(hào)的特殊代碼。此外，霍夫曼編碼方法的編碼效率比仙農(nóng)-范諾編碼效率高一些。請(qǐng)讀者自行驗(yàn)證

4.2 算術(shù)編碼

　　算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)(如JPEG，JBIG)中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號(hào)壓縮后的輸出。算術(shù)編碼器的編碼過程可用下面的例子加以解釋。
　　[例4.2] 假設(shè)信源符號(hào)為{00,01,10,11}，這些符號(hào)的概率分別為{ 0.1,0.4,0.2,0.3 }，根據(jù)這些概率可把間隔[0,1)分成4個(gè)子間隔：[0,0.1), [0.1,0.5), [0.5,0.7), [0.7,1)，其中[x,y)表示半開放間隔，即包含x不包含y。上面的信息可綜合在表4-04中。

表4-04 信源符號(hào)，概率和初始編碼間隔

　　如果二進(jìn)制消息序列的輸入為：10 00 11 00 10 11 01。編碼時(shí)首先輸入的符號(hào)是10，找到它的編碼范圍是[0.5,0.7)。由于消息中第二個(gè)符號(hào)00的編碼范圍是[0, 0.1)，因此它的間隔就取[0.5,0.7)的第一個(gè)十分之一作為新間隔[0.5,0.52)。依此類推，編碼第3個(gè)符號(hào)11時(shí)取新間隔為[0.514,0.52)，編碼第4個(gè)符號(hào)00時(shí)，取新間隔為[0.514,0.5146)，…。消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)。整個(gè)編碼過程如圖4-03所示。

圖4-03 算術(shù)編碼過程舉例

　　這個(gè)例子的編碼和譯碼的全過程分別表示在表4-05和表4-06中。根據(jù)上面所舉的例子，可把計(jì)算過程總結(jié)如下。
　　考慮一個(gè)有M個(gè)符號(hào)a_i＝(1,2,…,M)的字符表集，假設(shè)概率P(a_i)＝P_i，而。輸入符號(hào)用X_n表示，第n個(gè)子間隔的范圍用表示。其中l(wèi)₀＝0，d₀＝1和P₀＝0，l_n表示間隔左邊界的值, r_n表示間隔右邊界的值，d_n＝r_n-l_n表示間隔長(zhǎng)度。編碼步驟如下：
　　步驟1：首先在1和0之間給每個(gè)符號(hào)分配一個(gè)初始子間隔，子間隔的長(zhǎng)度等于它的概率，初始子間隔的范圍用I₁＝[l_1,r₁)＝[，)表示。令d₁＝r_1-l₁，L＝l₁和R＝r₁。
　　步驟2：L和R的二進(jìn)制表達(dá)式分別表示為：
　　和
其中u_k和V_k等于“1”或者“0”。
　　比較u₁和V₁：①如果u₁≠V₁，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；②如果u₁＝V₁，就發(fā)送二進(jìn)制符號(hào)u₁。
　　比較u₂和V₂：①如果u₂≠V₂，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；②如果u₂＝V₂，就發(fā)送二進(jìn)制符號(hào)u₂。
　　…
　　這種比較一直進(jìn)行到兩個(gè)符號(hào)不相同為止，然后進(jìn)入步驟3，
　　步驟3：n加1，讀下一個(gè)符號(hào)。假設(shè)第n個(gè)輸入符號(hào)為X_n＝a_i，按照以前的步驟把這個(gè)間隔分成如下所示的子間隔：
　　
　　令L＝l_n，R＝r_n和d_n＝r_n-l_n，然后轉(zhuǎn)到步驟2。

表4-05 編碼過程

表4-06 譯碼過程

　　[例3] 假設(shè)有4個(gè)符號(hào)的信源，它門的概率如表4-07所示：

表4-07 符號(hào)概率

　　輸入序列為X_n:a₂,a₁,a₃,…。它的編碼過程如圖4-04所示，現(xiàn)說明如下。
　　輸入第1個(gè)符號(hào)是X₁＝a₂，可知i＝2，定義初始間隔I₁＝[l₁,r₁)＝[，)＝[0.5,0.75)，由此可知d₁＝0.25，左右邊界的二進(jìn)制數(shù)分別表示為：L＝0.5=0.1(B)，R＝0.7＝0.11…(B)。按照步驟2，u₁＝V₁，發(fā)送1。因u₂≠V₂，因此轉(zhuǎn)到步驟3。
　　輸入第2個(gè)字符X₂＝a₁，i＝1，它的子間隔I₂＝[l₂,r₂)＝[l₁+， )＝[0.5,0.625)，由此可得d₂=0.125。左右邊界的二進(jìn)制數(shù)分別表示為：L＝0.5=0.100 … (B)，R＝0.101… (B)。按照步驟2，u₂＝V₂＝0，發(fā)送0，而u₃和V₃不相同，因此在發(fā)送0之后就轉(zhuǎn)到步驟3。
　　輸入第3個(gè)字符，X₃＝a₃，i＝3, 它的子間隔I₃＝[l₃,r₃)＝[, )＝[0.59375, 0.609375)，由此可得d₃=0.015625。左右邊界的二進(jìn)制數(shù)分別表示為：L＝0.59375=0.10011 (B)，R＝0.609375=0.100111(B)。按照步驟2，u₃＝V₃＝0，u₄＝V₄＝1，u₅＝V₅＝1，但u₆和V₆不相同，因此在發(fā)送011之后轉(zhuǎn)到步驟3。
　　…
　　發(fā)送的符號(hào)是：10011…。被編碼的最后的符號(hào)是結(jié)束符號(hào)。

圖4-04 算術(shù)編碼概念

　　就這個(gè)例子而言，算術(shù)編碼器接受的第1位是“1”，它的間隔范圍就限制在[0.5, 1)，但在這個(gè)范圍里有3種可能的碼符a₁, a₃和a₄，因此第1位沒有包含足夠的譯碼信息。在接受第2位之后就變成“10”，它落在[0.5, 0.75)的間隔里，由于這兩位表示的符號(hào)都指向a₂開始的間隔，因此就可斷定第一個(gè)符號(hào)是a₂。在接受每位信息之后的譯碼情況如下表4-08所示。

表4-08 譯碼過程表

　　在上面的例子中，我們假定編碼器和譯碼器都知道消息的長(zhǎng)度，因此譯碼器的譯碼過程不會(huì)無限制地運(yùn)行下去。實(shí)際上在譯碼器中需要添加一個(gè)專門的終止符，當(dāng)譯碼器看到終止符時(shí)就停止譯碼。
　　在算術(shù)編碼中需要注意的幾個(gè)問題：
　　1.由于實(shí)際的計(jì)算機(jī)的精度不可能無限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此這個(gè)問題可使用比例縮放方法解決。
　　2.算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0, 1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。
　　3.算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。
　　算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改，在編碼期間估算信源符號(hào)概率的過程叫做建模。需要開開發(fā)態(tài)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。因此動(dòng)態(tài)建模就成為確定編碼器壓縮效率的關(guān)鍵。

4.3 RLE編碼

　　現(xiàn)實(shí)中有許多這樣的圖像，在一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。在這種情況下就不需要存儲(chǔ)每一個(gè)象素的顏色值，而僅僅存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色的象素?cái)?shù)目就可以，或者存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色值的行數(shù)。這種壓縮編碼稱為行程編碼，常用(run length encoding，RLE)表示，具有相同顏色并且是連續(xù)的象素?cái)?shù)目稱為行程長(zhǎng)度。
　　為了敘述方便，假定一幅灰度圖像，第n行的象素值為：

圖4-05 RLE編碼的概念

　　用RLE編碼方法得到的代碼為：80315084180。代碼中用黑體表示的數(shù)字是行程長(zhǎng)度，黑體字后面的數(shù)字代表象素的顏色值。例如黑體字50代表有連續(xù)50個(gè)象素具有相同的顏色值，它的顏色值是8。
　　對(duì)比RLE編碼前后的代碼數(shù)可以發(fā)現(xiàn)，在編碼前要用73個(gè)代碼表示這一行的數(shù)據(jù)，而編碼后只要用11個(gè)代碼表示代表原來的73個(gè)代碼，壓縮前后的數(shù)據(jù)量之比約為7:1，即壓縮比為7:1。這說明RLE確實(shí)是一種壓縮技術(shù)，而且這種編碼技術(shù)相當(dāng)直觀，也非常經(jīng)濟(jì)。RLE所能獲得的壓縮比有多大，這主要是取決于圖像本身的特點(diǎn)。如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之，壓縮比就越小。
　　譯碼時(shí)按照與編碼時(shí)采用的相同規(guī)則進(jìn)行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。因此，RLE是無損壓縮技術(shù)。
　　RLE壓縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。然而，RLE對(duì)顏色豐富的自然圖像就顯得力不從心，在同一行上具有相同顏色的連續(xù)象素往往很少，而連續(xù)幾行都具有相同顏色值的連續(xù)行數(shù)就更少。如果仍然使用RLE編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)據(jù)變得更大。請(qǐng)注意，這并不是說RLE編碼方法不適用于自然圖像的壓縮，相反，在自然圖像的壓縮中還真少不了RLE，只不過是不能單純使用RLE一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。

4.4 詞典編碼

　　有許多場(chǎng)合，開始時(shí)不知道要編碼數(shù)據(jù)的統(tǒng)計(jì)特性，也不一定允許你事先知道它們的統(tǒng)計(jì)特性。因此，人們提出了許許多多的數(shù)據(jù)壓縮方法，企圖用來對(duì)這些數(shù)據(jù)進(jìn)行壓縮編碼，在實(shí)際編碼過程中以盡可能獲得最大的壓縮比。這些技術(shù)統(tǒng)稱為通用編碼技術(shù)。詞典編碼(Dictionary Encoding)技術(shù)就是屬于這一類，這種技術(shù)屬于無損壓縮技術(shù)。

4.4.1 詞典編碼的思想

　　詞典編碼(dictionary encoding)的根據(jù)是數(shù)據(jù)本身包含有重復(fù)代碼這個(gè)特性。例如文本文件和光柵圖像就具有這種特性。詞典編碼法的種類很多，歸納起來大致有兩類。
　　第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。這種編碼概念如圖4-06所示。

圖4-06 第一類詞典法編碼概念

　　這里所指的“詞典”是指用以前處理過的數(shù)據(jù)來表示編碼過程中遇到的重復(fù)部分。這類編碼中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年開發(fā)和發(fā)表的稱為L(zhǎng)Z77算法為基礎(chǔ)的，例如1982年由Storer和Szymanski改進(jìn)的稱為L(zhǎng)ZSS算法就是屬于這種情況。
　　第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典(dictionary of the phrases)”，這種短語不一定是像“嚴(yán)謹(jǐn)勤奮求實(shí)創(chuàng)新”和“國(guó)泰民安是坐穩(wěn)總統(tǒng)寶座的根本”這類具有具體含義的短語，它可以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語”時(shí)，編碼器就輸出這個(gè)詞典中的短語的“索引號(hào)”，而不是短語本身。這個(gè)概念如圖4-07所示。

圖4-07 第二類詞典法編碼概念

　　J.Ziv和A.Lempel在1978年首次發(fā)表了介紹這種編碼方法的文章。在他們的研究基礎(chǔ)上，Terry A.Weltch在1984年發(fā)表了改進(jìn)這種編碼算法的文章，因此把這種編碼方法稱為L(zhǎng)ZW(Lempel-Ziv Walch)壓縮編碼，首先在高速硬盤控制器上應(yīng)用了這種算法。

4.4.2 LZ77算法

　　為了更好地說明LZ77算法的原理，首先介紹算法中用到的幾個(gè)術(shù)語：
　　1.輸入數(shù)據(jù)流(input stream)：要被壓縮的字符序列。
　　2.字符(character)：輸入數(shù)據(jù)流中的基本單元。
　　3.編碼位置(coding position)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開始字符。
　　4.前向緩沖存儲(chǔ)器(Lookahead buffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。
　　5.窗口(window)：指包含W個(gè)字符的窗口，字符是從編碼位置開始向后數(shù)也就是最后處理的字符數(shù)。
　　6.指針(pointer)：指向窗口中的匹配串且含長(zhǎng)度的指針。
　　LZ77編碼算法的核心是查找從前向緩沖存儲(chǔ)器開始的最長(zhǎng)的匹配串。編碼算法的具體執(zhí)行步驟如下：
　　1.把編碼位置設(shè)置到輸入數(shù)據(jù)流的開始位置。
　　2.查找窗口中最長(zhǎng)的匹配串。
　　3.以“(Pointer, Length) Characters”的格式輸出，其中Pointer是指向窗口中匹配串的指針，Length表示匹配字符的長(zhǎng)度，Characters是前向緩沖存儲(chǔ)器中的不匹配的第1個(gè)字符。
　　4.如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移(Length+1)個(gè)字符，然后返回到步驟2。
　　[例4.4] 待編碼的數(shù)據(jù)流如表4-09所示，編碼過程如表4-10所示?，F(xiàn)作如下說明：
　　1.“步驟”欄表示編碼步驟。
　　2.“位置”欄表示編碼位置，輸入數(shù)據(jù)流中的第1個(gè)字符為編碼位置1。
　　3.“匹配串”欄表示窗口中找到的最長(zhǎng)的匹配串。
　　4.“字符”欄表示匹配之后在前向緩沖存儲(chǔ)器中的第1個(gè)字符。
　　5.“輸出”欄以“(Back_chars, Chars_length) Explicit_character”格式輸出。其中，(Back_chars, Chars_length)是指向匹配串的指針，告訴譯碼器“在這個(gè)窗口中向后退Back_chars個(gè)字符然后拷貝Chars_length個(gè)字符到輸出”，Explicit_character是真實(shí)字符。例如，表4-10中的輸出“(5,2) C”告訴譯碼器回退5個(gè)字符，然后拷貝2個(gè)字符“AB”

表4-09待編碼的數(shù)據(jù)流

表4-10 編碼過程

4.4.3 LZSS算法

　　LZ77通過輸出真實(shí)字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個(gè)解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個(gè)方面，一是空指針，二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。LZSS算法以比較有效的方法解決這個(gè)問題，它的思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度長(zhǎng)就輸出指針，否則就輸出真實(shí)字符。由于輸出的壓縮數(shù)據(jù)流中包含有指針和字符本身，為了區(qū)分它們就需要有額外的標(biāo)志位，即ID位。
　　LZSS編碼算法的具體執(zhí)行步驟如下：
　　1.把編碼位置置于輸入數(shù)據(jù)流的開始位置。
　　2.在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串
　　?、?Pointer ：=匹配串指針。
　　?、?Length ：=匹配串長(zhǎng)度。
　　3.判斷匹配串長(zhǎng)度Length是否大于等于最小匹配串長(zhǎng)度(Length 3 MIN_LENGTH) ，如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。
　　如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。
　　4.如果前向緩沖存儲(chǔ)器不是空的，就返回到步驟2。
　　[例4.5] 編碼字符串如表4-11所示，編碼過程如表4-12所示。現(xiàn)說明如下：
　　1.“步驟”欄表示編碼步驟。
　　2.“位置”欄表示編碼位置，輸入數(shù)據(jù)流中的第1個(gè)字符為編碼位置1。
　　3.“匹配”欄表示窗口中找到的最長(zhǎng)的匹配串。
　　4.“字符”欄表示匹配之后在前向緩沖存儲(chǔ)器中的第1個(gè)字符。
　　5.“輸出”欄的輸出為：
　　　① 如果匹配串本身的長(zhǎng)度Length 3 MIN_LENGTH，輸出指向匹配串的指針，格式為(Back_chars, Chars_length)。該指針告訴譯碼器“在這個(gè)窗口中向后退Back_chars個(gè)字符然后拷貝Chars_length個(gè)字符到輸出”。
　　　② 如果匹配串本身的長(zhǎng)度Length ￡ MIN_LENGTH，則輸出真實(shí)的匹配串。

表4-11 輸入數(shù)據(jù)流

表4-12 編碼過程(MIN_LENGTH = 2)

　　在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。這也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip, ARJ, LHArc和ZOO等等，其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同。
　　LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。

　　在介紹LZ78算法之前，首先說明在算法中用到的幾個(gè)術(shù)語和符號(hào)：
　　●字符流(Charstream)：要被編碼的數(shù)據(jù)序列。
　　●字符(Character)：字符流中的基本數(shù)據(jù)單元。
　　●前綴(Prefix)： 在一個(gè)字符之前的字符序列。
　　●綴-符串(String)：前綴＋字符。
　　●.碼字(Code word)：碼字流中的基本數(shù)據(jù)單元，代表詞典中的一串字符。
　　●碼字流(Codestream)： 碼字和字符組成的序列，是編碼器的輸出。
　　●詞典(Dictionary)： 綴-符串表。按照詞典中的索引號(hào)對(duì)每條綴-符串(String)指定一個(gè)碼字(Code word)。
　　●當(dāng)前前綴(Current prefix)：在編碼算法中使用，指當(dāng)前正在處理的前綴，用符號(hào)P表示。
　　●當(dāng)前字符(Current character)：在編碼算法中使用，指當(dāng)前前綴之后的字符，用符號(hào)C表示。
　　●10.當(dāng)前碼字(Current code word)： 在譯碼算法中使用，指當(dāng)前處理的碼字，用W表示當(dāng)前碼字，String.W表示當(dāng)前碼字的綴-符串。
　　1. 編碼算法
　　LZ78的編碼思想是不斷地從字符流中提取新的綴-符串(String)，通俗地理解為新“詞條”，然后用“代號(hào)”也就是碼字(Code word)表示這個(gè)“詞條”。這樣一來，對(duì)字符流的編碼就變成了用碼字(Code word)去替換字符流(Charstream)，生成碼字流(Codestream)，從而達(dá)到壓縮數(shù)據(jù)的目的。
　　在編碼開始時(shí)詞典是空的，不包含任何綴-符串(string)。在這種情況下編碼器就輸出一個(gè)表示空字符串的特殊碼字(例如“0”)和字符流中(Charstream)的第一個(gè)字符C，并把這個(gè)字符C添加到詞典中作為一個(gè)由一個(gè)字符組成的綴-符串(string)。在編碼過程中，如果出現(xiàn)類似的情況，也照此辦理。在詞典中已經(jīng)包含某些綴-符串(String)之后，如果“當(dāng)前前綴P +當(dāng)前字符C”已經(jīng)在詞典中，就用字符C來擴(kuò)展這個(gè)前綴，這樣的擴(kuò)展操作一直重復(fù)到獲得一個(gè)在詞典中沒有的綴-符串(String)為止。此時(shí)就輸出表示當(dāng)前前綴P的碼字(Code word)和字符C，并把P+C添加到詞典中作為前綴(Prefix)，然后開始處理字符流(Charstream)中的下一個(gè)前綴。
　　LZ78編碼器的輸出是碼字-字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的綴-符串(String)用字符C進(jìn)行擴(kuò)展生成新的綴-符串(String)，然后添加到詞典中。LZ78編碼的具體算法如下：
　　步驟1： 在開始時(shí)，詞典和當(dāng)前前綴P都是空的。
　　步驟2： 當(dāng)前字符C:=字符流中的下一個(gè)字符。
　　步驟3： 判斷P+C是否在詞典中：
　　　(1) 如果“是”：用C擴(kuò)展P，讓P := P+C ；
　　　(2) 如果“否”：
　　　?、?輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字和當(dāng)前字符C；
　　　?、?把字符串P+C 添加到詞典中。
　　　?、?令P:=空值。
　　　(3) 判斷字符流中是否還有字符需要編碼
　　　?、?如果“是”：返回到步驟2。
　　　?、?如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。
　　2. 譯碼算法
　　在譯碼開始時(shí)譯碼詞典是空的，它將在譯碼過程中從碼字流中重構(gòu)。每當(dāng)從碼字流中讀入一對(duì)碼字-字符(W,C)對(duì)時(shí)，碼字就參考已經(jīng)在詞典中的綴-符串，然后把當(dāng)前碼字的綴-符串string.W 和字符C輸出到字符流(Charstream)，而把當(dāng)前綴-符串(string.W+C)添加到詞典中。在譯碼結(jié)束之后，重構(gòu)的詞典與編碼時(shí)生成的詞典完全相同。LZ78譯碼的具體算法如下：
　　步驟1： 在開始時(shí)詞典是空的。
　　步驟2： 當(dāng)前碼字W :=碼字流中的下一個(gè)碼字。
　　步驟3： 當(dāng)前字符C := 緊隨碼字之后的字符。
　　步驟4： 把當(dāng)前碼字的綴-符串(string.W)輸出到字符流(Charstream)，然后輸出字符C。
　　步驟5： 把string.W+C添加到詞典中。
　　步驟6： 判斷碼字流中是否還有碼字要譯
　　　(1) 如果“是”，就返回到步驟2。
　　　(2) 如果“否”，則結(jié)束。
　　[例4.6] 編碼字符串如表4-13所示，編碼過程如表4-14所示。現(xiàn)說明如下：
　　●“步驟”欄表示編碼步驟。
　　●“位置”欄表示在輸入數(shù)據(jù)中的當(dāng)前位置。
　　●“詞典”欄表示添加到詞典中的綴-符串，綴-符串的索引等于“步驟”序號(hào)。
　　●“輸出”欄以(當(dāng)前碼字W, 當(dāng)前字符C)簡(jiǎn)化為(W, C)的形式輸出。

表4-13 編碼字符串

表4-14 編碼過程

　　與LZ77相比，LZ78的最大優(yōu)點(diǎn)是在每個(gè)編碼步驟中減少了綴-符串(String)比較的數(shù)目，而壓縮率與LZ77類似。

　　在LZW算法中使用的術(shù)語與LZ78使用的相同，僅增加了一個(gè)術(shù)語—前綴根(Root)，它是由單個(gè)字符串組成的綴-符串(String)。在編碼原理上，LZW與LZ78相比有如下差別：①LZW只輸出代表詞典中的綴-符串(String)的碼字(code word)。這就意味在開始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。②由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每個(gè)編碼步驟開始時(shí)都使用一字符前綴(one-character prefix)，因此在詞典中搜索的第1個(gè)綴-符串有兩個(gè)字符。
　　現(xiàn)將LZW編碼算法和譯碼算法介紹如下。
　　1. 編碼算法
　　LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。這張轉(zhuǎn)換表用來存放稱為前綴(Prefix)的字符序列，并且為每個(gè)表項(xiàng)分配一個(gè)碼字(Code word)，或者叫做序號(hào)，如表4-15所示。這張轉(zhuǎn)換表實(shí)際上是把8位ASCII字符集進(jìn)行擴(kuò)充，增加的符號(hào)用來表示在文本或圖像中出現(xiàn)的可變長(zhǎng)度ASCII字符串。擴(kuò)充后的代碼可用9位、10位、11位、12位甚至更多的位來表示。Welch的論文中用了12位，12位可以有4096個(gè)不同的12位代碼，這就是說，轉(zhuǎn)換表有4096個(gè)表項(xiàng)，其中256個(gè)表項(xiàng)用來存放已定義的字符，剩下3840個(gè)表項(xiàng)用來存放前綴(Prefix)。

表4-15 詞典

　　LZW編碼器(軟件編碼器或硬件編碼器)就是通過管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換。LZW編碼器的輸入是字符流(Charstream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼字流(Codestream)，碼字代表單個(gè)字符或多個(gè)字符組成的字符串。
　　LZW編碼器使用了一種很實(shí)用的分析(parsing)算法，稱為貪婪分析算法(greedy parsing algorithm)。在貪婪分析算法中，每一次分析都要串行地檢查來自字符流(Charstream)的字符串，從中分解出已經(jīng)識(shí)別的最長(zhǎng)的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長(zhǎng)的前綴(Prefix)。用已知的前綴(Prefix)加上下一個(gè)輸入字符C也就是當(dāng)前字符(Current character)作為該前綴的擴(kuò)展字符，形成新的擴(kuò)展字符串——綴-符串(String)：Prefix.C。這個(gè)新的綴-符串(String)是否要加到詞典中，還要看詞典中是否存有和它相同的綴-符串String。如果有，那么這個(gè)綴-符串(String)就變成前綴(Prefix)，繼續(xù)輸入新的字符，否則就把這個(gè)綴-符串(String)寫到詞典中生成一個(gè)新的前綴(Prefix)，并給一個(gè)代碼。
　　LZW編碼算法的具體執(zhí)行步驟如下：
　　步驟1： 開始時(shí)的詞典包含所有可能的根(Root)，而當(dāng)前前綴P是空的；
　　步驟2： 當(dāng)前字符(C) :=字符流中的下一個(gè)字符；
　　步驟3： 判斷綴-符串P+C是否在詞典中
　　　(1) 如果“是”：P := P+C // (用C擴(kuò)展P)；
　　　(2) 如果“否”
　　　?、?把代表當(dāng)前前綴P的碼字輸出到碼字流;
　　　?、?把綴-符串P+C添加到詞典;
　　　?、?令P := C //(現(xiàn)在的P僅包含一個(gè)字符C);
　　步驟4： 判斷碼字流中是否還有碼字要譯
　　　(1) 如果“是”，就返回到步驟2；
　　　(2) 如果“否”
　　　　① 把代表當(dāng)前前綴P的碼字輸出到碼字流;
　　　?、?結(jié)束。
　　LZW編碼算法可用偽碼表示。開始時(shí)假設(shè)編碼詞典包含若干個(gè)已經(jīng)定義的單個(gè)碼字。例如，256個(gè)字符的碼字，用偽碼可以表示成：

　　Dictionary[j] ← all n single-character， j＝1, 2， …，n
　　j ← n+1
　　Prefix ← read first Character in Charstream
　　while((C ← next Character)!=NULL)
　　Begin
　　　If Prefix.C is in Dictionary
　　　　Prefix ← Prefix.C
　　　else
　　　　Codestream ← cW for Prefix
　　　Dictionary[j] ← Prefix.C
　　　j ← n+1
　　　Prefix ← C
　　end
　　Codestream ← cW for Prefix

　　2. 譯碼算法
　　LZW譯碼算法中還用到另外兩個(gè)術(shù)語：①當(dāng)前碼字(Current code word)：指當(dāng)前正在處理的碼字，用cW表示，用string.cW表示當(dāng)前綴-符串；②先前碼字(Previous code word)：指先于當(dāng)前碼字的碼字，用pW表示，用string.pW表示先前綴-符串。
　　LZW譯碼算法開始時(shí)，譯碼詞典與編碼詞典相同，它包含所有可能的前綴根(roots)。LZW算法在譯碼過程中會(huì)記住先前碼字(pW)，從碼字流中讀當(dāng)前碼字(cW)之后輸出當(dāng)前綴-符串string.cW，然后把用string.cW的第一個(gè)字符擴(kuò)展的先前綴-符串string.pW添加到詞典中。
　　LZW譯碼算法的具體執(zhí)行步驟如下：
　　步驟1：在開始譯碼時(shí)詞典包含所有可能的前綴根(Root)。
　　步驟2：cW :=碼字流中的第一個(gè)碼字。
　　步驟3：輸出當(dāng)前綴-符串string.cW到碼字流。
　　步驟4： 先前碼字pW := 當(dāng)前碼字cW。
　　步驟5： 當(dāng)前碼字cW := 碼字流中的下一個(gè)碼字。
　　步驟6： 判斷先前綴-符串string.pW是否在詞典中
　　　(1) 如果“是”，則：
　　　　① 把先前綴-符串string.pW輸出到字符流。
　　　　② 當(dāng)前前綴P :=先前綴-符串string.pW。
　　　　③ 當(dāng)前字符C :=當(dāng)前前綴-符串string.cW的第一個(gè)字符。
　　　?、?把綴-符串P+C添加到詞典。
　　　(2) 如果“否”，則：
　　　?、?當(dāng)前前綴P :=先前綴-符串string.pW。
　　　　② 當(dāng)前字符C :=當(dāng)前綴-符串string.cW的第一個(gè)字符。
　　　?、?輸出綴-符串P+C到字符流，然后把它添加到詞典中。
　　步驟7： 判斷碼字流中是否還有碼字要譯
　　　(1) 如果“是”，就返回到步驟4。
　　　(2) 如果“否”, 結(jié)束。
　　LZW譯碼算法可用偽碼表示如下:

　　Dictionary[j] ← all n single-character， j＝1, 2， …，n
　　j ← n+1
　　cW ← first code from Codestream
　　Charstream ← Dictionary[cW]
　　pW ← cW
　　While((cW ← next Code word)!=NULL)
　　Begin
　　　If cW is in Dictionary
　　　　Charstream ← Dictionary[cW]
　　　　Prefix ← Dictionary[pW]
　　　　cW ← first Character of Dictionary[cW]
　　　　Dictionary[j] ← Prefix.cW
　　　　j ← n+1
　　　　pW ← cW
　　　else
　　　　Prefix ← Dictionary[pW]
　　　　cW ← first Character of Prefix
　　　　Charstream ← Prefix.cW
　　    Dictionary[j] ← Prefix.C
　　    pW ← cW
　　    j ← n+1
　　end
　　[例4.7] 編碼字符串如表4-16所示，編碼過程如表4-17所示?，F(xiàn)說明如下：
　　●“步驟”欄表示編碼步驟；
　　●“位置”欄表示在輸入數(shù)據(jù)中的當(dāng)前位置；
　　●“詞典”欄表示添加到詞典中的綴-符串，它的索引在括號(hào)中；
　　●“輸出”欄表示碼字輸出。

表4-16 被編碼的字符串

表4-17 LZW的編碼過程

　　表4-18解釋了譯碼過程。每個(gè)譯碼步驟譯碼器讀一個(gè)碼字，輸出相應(yīng)的綴-符串，并把它添加到詞典中。例如，在步驟4中，先前碼字(2)存儲(chǔ)在先前碼字(pW)中，當(dāng)前碼字(cW)是(4)，當(dāng)前綴-符串string.cW是輸出(“A B”)，先前綴-符串string.pW ("B")是用當(dāng)前綴-符串string.cW ("A")的第一個(gè)字符，其結(jié)果("B A") 添加到詞典中，它的索引號(hào)是(6)

表4-18 LZW的譯碼過程

　　LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操作。對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。
　　LZW算法取得了專利，專利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法

參考文獻(xiàn)和站點(diǎn)

練習(xí)與思考題

練習(xí)_表1

　　2.字符流的輸入如練習(xí)_表2所示，使用LZW算法計(jì)算輸出的碼字流。如果你自己對(duì)本章介紹的LZW算法不打算進(jìn)行改進(jìn)，并且使用練習(xí)_表3進(jìn)行計(jì)算。請(qǐng)核對(duì)計(jì)算的輸出碼字流是否為：
(1) (2) (4) (3) (5) (8) (1) (10) (11) …
并將碼字流中的碼字填入練習(xí)_表2對(duì)應(yīng)的位置。

練習(xí)_表2

練習(xí)_表3

　　3.LZ78算法和LZ77算法的差別在哪里？
　　4.LZSS算法和LZ77算法的核心思想是什么？它們之間有什么差別？
　　5.LZW算法和LZ78算法的核心思想是什么？它們之間有什么差別？

參考文獻(xiàn)和站點(diǎn)

• Timothy C.Bell, John G.Cleary, Ian H.Witten. Text Compression.Prentice-Hall, Inc.,1990
• Terry A. Welch, A Technique for High-Performance Data Compression. Computer, June 1984.
• Wayne E.Carlson. A Survey of computer Graphics c4age Encoding and Storage Formats. Computer Graphics, April 1991，Vol.25, No.2
• Gerald L.Graef. Graphics Formats. Byte, Sept. 1989
• Julia Nguyen, Eric Hamiltom. JPEG File Interchange Format. Radius Inc, C-Cube Microsystems, April 10, 1991
• R.Hunter and A.H.Robison. International Digital Facsimile Coding Standards. Proceedings of the IEEE, Vol.68, No.7，July, 1980，pp854～867
• http://www.rasip./(瀏覽日期：2000年1月15)