第三章 數(shù)據(jù)壓縮

1、主要內(nèi)容主要內(nèi)容n3.1 數(shù)據(jù)壓縮技術(shù)概述n3.2 熵的概念n3.3 無損壓縮和常用無損壓縮算法。n香農(nóng)范諾編碼n霍夫曼編碼和算術(shù)編碼n算術(shù)編碼n行程編碼（RLE）n詞典編碼3.1多媒體數(shù)據(jù)壓縮技術(shù)概述多媒體數(shù)據(jù)壓縮技術(shù)概述n數(shù)據(jù)壓縮就是用比較少的數(shù)據(jù)量表達(dá)原始的圖像或聲音等信息。n多媒體數(shù)據(jù)壓縮的必要性n數(shù)據(jù)存儲容量n傳輸帶寬武漢書武漢書P793.1.1多媒體數(shù)據(jù)冗余類型多媒體數(shù)據(jù)冗余類型n多媒體數(shù)據(jù)有大量的冗余數(shù)據(jù)，如將重復(fù)的數(shù)據(jù)，改用數(shù)學(xué)方法表示，就可以減少數(shù)據(jù)量。n將人的眼睛和耳朵感覺不到的信息去掉，也可以壓縮數(shù)據(jù)。數(shù)據(jù)冗余類型有六種：武漢書武漢書P793.1.1多媒體數(shù)據(jù)冗余類型多媒

2、體數(shù)據(jù)冗余類型n空間（空域）冗余如一幅圖像，規(guī)則物體和規(guī)則背景的表面物理特性具有相關(guān)性。n時間（時域）冗余如圖像序列的后一幅圖像與前一幅之間有較大的相關(guān)。人在說話時聲音的音頻是一個連續(xù)漸變的過程，也存在時間冗余。武漢書武漢書P793.1.1多媒體數(shù)據(jù)冗余多媒體數(shù)據(jù)冗余類型類型n信息熵冗余（編碼冗余）信息熵是指一組數(shù)據(jù)所攜帶的平均信息量。n結(jié)構(gòu)冗余數(shù)字化圖像中的物體表面紋理（如草席的紋理）等結(jié)構(gòu)，存在冗余。3.1.1多媒體數(shù)據(jù)冗余類型多媒體數(shù)據(jù)冗余類型n知識冗余許多圖像的理解與某些基礎(chǔ)知識有相關(guān)性，如人臉的結(jié)構(gòu)可由先驗知識和背景知識得到。n視覺冗余人類的視覺系統(tǒng)對于圖像的注意是非均勻和非線性的，

3、視覺系統(tǒng)并不是圖像的任何變化都能感知的。n按解碼后的數(shù)據(jù)與原始數(shù)據(jù)一致性分類：按解碼后的數(shù)據(jù)與原始數(shù)據(jù)一致性分類： 無損壓縮無損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)( (或者叫做或者叫做還原，解壓縮還原，解壓縮) )，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號與原始信號完全一致的場合。損壓縮用于要求重構(gòu)的信號與原始信號完全一致的場合。 有損壓縮有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原始資料表達(dá)數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原

4、始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號不一定非要和的信息造成誤解。有損壓縮適用于重構(gòu)信號不一定非要和原始信號完全相同的場合。原始信號完全相同的場合。新一代數(shù)據(jù)壓縮方法有矢量量化和子帶編碼，基于模新一代數(shù)據(jù)壓縮方法有矢量量化和子帶編碼，基于模型的壓縮，分形壓縮和小波變換壓縮等。型的壓縮，分形壓縮和小波變換壓縮等。3.1.2數(shù)據(jù)壓縮方法分類數(shù)據(jù)壓縮方法分類武書武書P803.1.2數(shù)據(jù)壓縮方法分類數(shù)據(jù)壓縮方法分類n按方法的原理分類：n 信息熵編碼n 預(yù)測編碼n 變換編碼n 量化與向量量化編碼n 頻帶編碼n 模型編碼1. 基于知識的編碼武漢書武漢書P803.1.3數(shù)據(jù)壓縮方法的基本原理數(shù)據(jù)壓

5、縮方法的基本原理n統(tǒng)計冗余度的壓縮n空間冗余度的壓縮n時間冗余度的壓縮n視覺冗余度的壓縮武漢書武漢書P81壓縮比要大壓縮比要大恢復(fù)后的失真小恢復(fù)后的失真小壓縮算法要簡單、速度快壓縮算法要簡單、速度快壓縮能否用硬件實現(xiàn)壓縮能否用硬件實現(xiàn)3.1.4 數(shù)據(jù)壓縮技術(shù)實現(xiàn)的衡量標(biāo)準(zhǔn)數(shù)據(jù)壓縮技術(shù)實現(xiàn)的衡量標(biāo)準(zhǔn)數(shù)據(jù)壓縮的性能指標(biāo)數(shù)據(jù)壓縮的性能指標(biāo)算法的編碼效率算法的編碼效率編碼圖像的質(zhì)量編碼圖像的質(zhì)量算法的適用范圍算法的適用范圍算法的復(fù)雜度算法的復(fù)雜度n信源被抽象為一個隨機(jī)變量序列（隨機(jī)過程）。信源被抽象為一個隨機(jī)變量序列（隨機(jī)過程）。n如果信源輸出的隨機(jī)變量取值于某一連續(xù)區(qū)間，如果信源輸出的隨機(jī)變量取值于

6、某一連續(xù)區(qū)間，就叫做就叫做連續(xù)信源連續(xù)信源。比如語音信號。比如語音信號X(t)。n如果信源輸出的隨機(jī)變量取值于某一離散符號如果信源輸出的隨機(jī)變量取值于某一離散符號集合，就叫做集合，就叫做離散信源離散信源。比如平面圖像。比如平面圖像X(x，y)和電報。和電報。信源信源 X1, X2, X3, X43.2熵的概念熵的概念3.2.1 決策量、信息量和熵決策量、信息量和熵n香農(nóng)信息論把一個事件（字符香農(nóng)信息論把一個事件（字符a1）所攜帶的所攜帶的信信息量息量定義為：定義為： I(a1) = log2 (1/p) = - log2 p (bit) 其中其中p p為事件發(fā)生（字符出現(xiàn)）的為事件發(fā)生（字符出

7、現(xiàn)）的概率概率nI(a1)即隨機(jī)變量即隨機(jī)變量X取值為取值為a1時所攜帶的信息量時所攜帶的信息量n因為因為X的信息量也是一個隨機(jī)變量，所以我們的信息量也是一個隨機(jī)變量，所以我們要研究它的統(tǒng)計特性。其數(shù)學(xué)期望為：要研究它的統(tǒng)計特性。其數(shù)學(xué)期望為： 稱稱H(X)為一階為一階信息熵信息熵或者簡稱為或者簡稱為熵熵(Entropy)mjmjjjjjppaIpxH11log)()(2信源的概率分布與熵的關(guān)系信源的概率分布與熵的關(guān)系n熵的大小與信源的概率模型熵的大小與信源的概率模型(分布分布)有著密有著密切的關(guān)系。是無序的表現(xiàn)。切的關(guān)系。是無序的表現(xiàn)。n最大離散熵定理最大離散熵定理：當(dāng)與信源對應(yīng)的字符：當(dāng)與

8、信源對應(yīng)的字符集中的各個字符為集中的各個字符為等概率分布等概率分布時，熵具時，熵具有極大值有極大值log2m。m為字符集中字符個數(shù)。為字符集中字符個數(shù)。mjjjppxH1log)(3.2.3 平均碼長與熵平均碼長與熵n如果對字符如果對字符aj的編碼長度為的編碼長度為Lj，則則X的平均碼的平均碼長為：長為：n根據(jù)前面的分析，有：根據(jù)前面的分析，有：mjjjLpL1)(1)(XHLLXHmjjjjmjjppLp121log 在在Lj log2pj時，平均碼長取得極小值時，平均碼長取得極小值H(X)數(shù)據(jù)冗余量數(shù)據(jù)冗余量數(shù)據(jù)的冗余量數(shù)據(jù)的冗余量(R) = 決策量決策量(H0) - 熵熵(H)例如：令a

9、,b,c為3個事件構(gòu)成的數(shù)據(jù)集，它們出現(xiàn)的概率分別為P(a)=0.5， P(b)=0.25， P(c)=0.25則數(shù)據(jù)冗余量為R= H0-H = 1.58 1.50 =0.08熵編碼熵編碼n熵編碼包括香農(nóng)范諾編碼、霍夫曼編碼和算術(shù)編碼，其宗旨在于找到一種編碼使得平均碼長達(dá)到熵極限，基本思想就是對出現(xiàn)概率較大的符號取較短的碼長，而對出現(xiàn)概率較小的符號取較大的碼長。3.3無損數(shù)據(jù)壓縮無損數(shù)據(jù)壓縮3.3.1 香農(nóng)香農(nóng)-范諾編碼范諾編碼n 在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量。n在計算熵時，以2為底的對數(shù)時，單位就是“位bit”。n例 2.1 見書P27 壓縮比的理論值 符號編碼

10、 壓縮比的實際值統(tǒng)計編碼統(tǒng)計編碼 香農(nóng)香農(nóng)-范諾編碼范諾編碼符號符號出現(xiàn)的次數(shù)出現(xiàn)的次數(shù)(p(xi)Log2(1/ p(xi)分配的分配的代碼代碼需要的需要的位數(shù)位數(shù)A15(0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.000011115統(tǒng)計編碼統(tǒng)計編碼3.3.2 霍夫曼編碼霍夫曼編碼nHuffman（霍夫曼） 1952年問世，依據(jù)變字長編碼理論n具體步驟：（1）初始化,按概率排序（2）合并概率最小的兩個事件（3）重復(fù)（2），形成一棵樹（4）從根節(jié)點開始分配代碼（5）寫出

11、每個符號的代碼（6）按照香農(nóng)理論計算熵P29統(tǒng)計編碼統(tǒng)計編碼霍夫曼編碼舉例霍夫曼編碼舉例例 2.2 見書P28符號符號出現(xiàn)的次數(shù)出現(xiàn)的次數(shù)(p(xi)Log2(1/ p(xi)分配的分配的代碼代碼需要的需要的位數(shù)位數(shù)A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115統(tǒng)計編碼統(tǒng)計編碼局限性局限性n霍夫曼碼沒有錯誤保護(hù)功能，錯誤傳播n可變長度碼，很難隨意查找壓縮文件中間的內(nèi)容?；舴蚵幋a是自含同步的代碼霍夫曼編碼是自含同步的代碼n雖然分配的代碼長度不是固定的，但

12、編碼時卻不需要在生成的碼流中附加同步代碼。 因為解碼時，可以根據(jù)碼表進(jìn)行譯碼。統(tǒng)計編碼統(tǒng)計編碼3.3.3 算術(shù)編碼算術(shù)編碼n基本思想：算術(shù)編碼不是將單個信源符號映射基本思想：算術(shù)編碼不是將單個信源符號映射成一個碼字，成一個碼字，而是把整個信源表示為實數(shù)線上而是把整個信源表示為實數(shù)線上的的0到到1之間的一個區(qū)間，其長度等于該序列的之間的一個區(qū)間，其長度等于該序列的概率，再在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，概率，再在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，轉(zhuǎn)化為二進(jìn)制作為實際的編碼輸出。轉(zhuǎn)化為二進(jìn)制作為實際的編碼輸出。消息序列消息序列中的每個元素都要用來縮短這個區(qū)間。消息序中的每個元素都要用來縮短這個區(qū)間。消

13、息序列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間。變小時，就需要更多的數(shù)位來表示這個區(qū)間。n采用算術(shù)編碼每個符號的平均編碼長度可以為采用算術(shù)編碼每個符號的平均編碼長度可以為小數(shù)。小數(shù)。統(tǒng)計編碼統(tǒng)計編碼算術(shù)編碼舉例算術(shù)編碼舉例符號符號00011011概率概率0.10.40.20.3初始區(qū)間初始區(qū)間0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1)P30統(tǒng)計編碼統(tǒng)計編碼算術(shù)編碼的具體實現(xiàn)算術(shù)編碼的具體實現(xiàn)n因為實際只能用有限長的寄存器，這就要求將因為實際只能用有限長的寄存器，這就要求將已編碼的高位碼字及時輸出，

14、但又不能輸出過已編碼的高位碼字及時輸出，但又不能輸出過早，以免后續(xù)運算還要調(diào)整已輸出的碼位。早，以免后續(xù)運算還要調(diào)整已輸出的碼位。（具體算法見相關(guān)參考書）（具體算法見相關(guān)參考書）n算術(shù)編碼每次遞推都要做乘法，所以效率比較算術(shù)編碼每次遞推都要做乘法，所以效率比較低。低。二進(jìn)制算術(shù)編碼二進(jìn)制算術(shù)編碼是一種實用的編碼算法，是一種實用的編碼算法，用移位代替了乘法，使效率大大提高。用移位代替了乘法，使效率大大提高。n自適應(yīng)算術(shù)編碼自適應(yīng)算術(shù)編碼可以在編碼過程中根據(jù)符號出可以在編碼過程中根據(jù)符號出現(xiàn)的頻繁程度動態(tài)的修改分布概率，這樣可以現(xiàn)的頻繁程度動態(tài)的修改分布概率，這樣可以避免在編碼之前必須精確求出信源

15、概率的難題。避免在編碼之前必須精確求出信源概率的難題。統(tǒng)計編碼統(tǒng)計編碼自適應(yīng)算術(shù)編碼舉例自適應(yīng)算術(shù)編碼舉例cba1.00000.66670.33330.00000.66670.58340.41670.33330.66670.63340.60010.58340.66670.65010.63900.6334c1/31/42/53/6b1/32/42/52/6a1/31/41/51/6輸入序列為：輸入序列為：bcc.統(tǒng)計編碼統(tǒng)計編碼3.3.4 行程編碼（行程編碼（RLE）n行程編碼（行程編碼（Run-Length Encoding）：）：它通它通過將信源中相同符號序列轉(zhuǎn)換成一個計數(shù)字過將信源中相同符

16、號序列轉(zhuǎn)換成一個計數(shù)字段再加上一個重復(fù)字符標(biāo)志實現(xiàn)壓縮。段再加上一個重復(fù)字符標(biāo)志實現(xiàn)壓縮。n例如：例如：RTTTTTTTTABBCDG被轉(zhuǎn)換為：被轉(zhuǎn)換為：R#8TABBCDG，其中其中“”作為轉(zhuǎn)義字符，作為轉(zhuǎn)義字符，表明其后所跟的字符表示長度。表明其后所跟的字符表示長度。n行程編碼多用于行程編碼多用于黑白二值圖像黑白二值圖像的壓縮中。例的壓縮中。例如如00000000111111111111000001111111被轉(zhuǎn)化為被轉(zhuǎn)化為一系列黑串和白串長度的編碼：一系列黑串和白串長度的編碼：81257。因。因為串長度并非等概率分布，所以一般要配合為串長度并非等概率分布，所以一般要配合以統(tǒng)計編碼（以統(tǒng)

17、計編碼（Huffman編碼）。編碼）。武P89，清P513.3.5 詞典編碼詞典編碼n詞典編碼主要利用數(shù)據(jù)本身包含許多重復(fù)的字詞典編碼主要利用數(shù)據(jù)本身包含許多重復(fù)的字符串的特性。符串的特性。例如：吃葡萄不吐葡萄皮，不吃例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。葡萄倒吐葡萄皮。 我們?nèi)绻靡恍┖唵蔚拇栁覀內(nèi)绻靡恍┖唵蔚拇柎孢@些字符串，就可以實現(xiàn)壓縮，實際上就代替這些字符串，就可以實現(xiàn)壓縮，實際上就是利用了信源符號之間的相關(guān)性。字符串與代是利用了信源符號之間的相關(guān)性。字符串與代號的對應(yīng)表就是詞典。號的對應(yīng)表就是詞典。n實用的詞典編碼算法的核心就是如何實用的詞典編碼算法的核心就是如何動態(tài)地

18、形動態(tài)地形成詞典成詞典，以及如何選擇輸出格式以減小冗余。，以及如何選擇輸出格式以減小冗余。第一類詞典編碼第一類詞典編碼n第一類詞典法的想法是企圖查找正在壓縮的字符序列第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的出現(xiàn)過的字符串的“指針指針”。第二類詞典編碼第二類詞典編碼n第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典短語詞典 (dictionar

19、y of the phrases)”，這種短語可這種短語可以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的詞典中出現(xiàn)的“短語短語”時，編碼器就輸出這個詞典中時，編碼器就輸出這個詞典中的短語的的短語的“索引號索引號”，而不是短語本身。，而不是短語本身。3.3.5.1 LZ77算法算法nLZ77 算法在某種意義上又可以稱為算法在某種意義上又可以稱為“滑動窗口壓滑動窗口壓縮縮”，該算法將一個虛擬的，可以跟隨壓縮進(jìn)程滑，該算法將一個虛擬的，可以跟隨壓縮進(jìn)程滑動的窗口作為詞典，要壓縮的字符串如果在該窗口動的窗口作為詞典，要壓縮的字符串如果在該窗口中

20、出現(xiàn)，則輸出其出現(xiàn)中出現(xiàn)，則輸出其出現(xiàn)位置和長度位置和長度。使用固定大小窗口進(jìn)行詞語匹配，而不是在所有已經(jīng)使用固定大小窗口進(jìn)行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因為匹配算法的時間消耗往編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制詞典的大小才能保證算法的效率；往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進(jìn)程滑動詞典窗口，使其中總包含最近編隨著壓縮的進(jìn)程滑動詞典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。字符串往往在最近的上下文中更容易找到匹配串。

21、LZ77編碼的基本流程編碼的基本流程1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進(jìn)行步驟找到，則進(jìn)行步驟 2，否則進(jìn)行步驟，否則進(jìn)行步驟 3。2、輸出三元符號組、輸出三元符號組 ( off, len, c )。其中其中 off 為窗口為窗口中匹配字符串相對窗口邊界的偏移，中匹配字符串相對窗口邊界的偏移，len 為可匹為可匹配的長度，配的長度，c 為下一個字符，即為下一個字符，即不匹配的第一個不匹配的第一個字符字符。然后將窗口向后滑動。然后將窗口向后滑動 len

22、+ 1 個字符個字符，繼，繼續(xù)步驟續(xù)步驟 1。3、輸出三元符號組、輸出三元符號組 ( 0, 0, c )。其中其中 c 為下一個字為下一個字符。然后將窗口向后滑動符。然后將窗口向后滑動 1 個字符，繼續(xù)步驟個字符，繼續(xù)步驟 1。書P34 LZ77算法算法LZ77編碼舉例編碼舉例AABCBBABCA步驟位置匹配串輸出110, 0, A22A1, 1, B340, 0, C45B2, 1, B57AB5, 3, A書P35 位置位置 1 2 3 4 5 6 7 8 9 103.3.5.2 LZSS算法算法nLZ77通過通過輸出真實字符輸出真實字符解決了在窗口中出現(xiàn)沒解決了在窗口中出現(xiàn)沒有匹配串的問

23、題，但這個解決方案包含有匹配串的問題，但這個解決方案包含有冗余有冗余信息信息。冗余信息表現(xiàn)在兩個方面，一是空指針，。冗余信息表現(xiàn)在兩個方面，一是空指針，二是編碼器可能輸出額外的字符，這種字符是二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個匹配串中的字符。指可能包含在下一個匹配串中的字符。nLZSS算法的思想是如果匹配串的長度比指針本算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針（匹配串長度大于等于身的長度長就輸出指針（匹配串長度大于等于MIN_LENGTH），），否則就輸出真實字符。另否則就輸出真實字符。另外要輸出額外的標(biāo)志位區(qū)分是指針還是字符。外要輸出額外的標(biāo)志位區(qū)分是

24、指針還是字符。LZSS編碼的基本流程編碼的基本流程1、從當(dāng)前壓縮位置開始，考察未編碼的字符，并、從當(dāng)前壓縮位置開始，考察未編碼的字符，并試圖在滑動窗口中找出最長的匹配字符串，如試圖在滑動窗口中找出最長的匹配字符串，如果匹配串長度果匹配串長度len大于等于最小匹配串長度（大于等于最小匹配串長度（len = MIN_LENGTH），），則進(jìn)行步驟則進(jìn)行步驟 2，否則進(jìn)，否則進(jìn)行步驟行步驟 3。2、輸出指針二元組、輸出指針二元組 ( off, len)。其中其中 off 為窗口中為窗口中匹配字符串相對窗口邊界的偏移，匹配字符串相對窗口邊界的偏移，len 為匹配串為匹配串的長度，然后將窗口向后滑動的長

25、度，然后將窗口向后滑動 len 個字符，繼個字符，繼續(xù)步驟續(xù)步驟 1。3、輸出當(dāng)前字符、輸出當(dāng)前字符c，然后將窗口向后滑動然后將窗口向后滑動 1 個字個字符，繼續(xù)步驟符，繼續(xù)步驟 1。LZSS編碼舉例編碼舉例位置1234567891011字符AABBCBBAABC步驟位置匹配串輸出11A22AA33B44BB55C66BB（3，2）78AAB（7，3）811CC輸入數(shù)輸入數(shù)據(jù)流：據(jù)流：編碼過程編碼過程MIN_LEN =2LZSS算法算法n在相同的計算機(jī)環(huán)境下，在相同的計算機(jī)環(huán)境下，LZSS算法比算法比LZ77可獲可獲得比較高的壓縮比，而譯碼同樣簡單。這也就是得比較高的壓縮比，而譯碼同樣簡單。這

26、也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了來開發(fā)的文檔壓縮程序都使用了LZSS的思想。的思想。例如，例如，PKZip, GZip, ARJ, LHArc和和ZOO等等，等等，其差別僅僅是指針的長短和窗口的大小等有所不其差別僅僅是指針的長短和窗口的大小等有所不同。同。nLZSS同樣可以和熵編碼聯(lián)合使用，例如同樣可以和熵編碼聯(lián)合使用，例如ARJ就與就與霍夫曼編碼聯(lián)用，而霍夫曼編碼聯(lián)用，而PKZip則與則與Shannon-Fano聯(lián)聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。用，它的后續(xù)版本也采用霍夫曼編碼。3.3.5.3 LZ78

27、算法算法nLZ78的編碼思想是不斷地從字符流中提取新的字的編碼思想是不斷地從字符流中提取新的字符串符串(String)，通俗地理解為新通俗地理解為新“詞條詞條”，然后用，然后用“代號代號”也就是也就是碼字碼字(Code word)表示這個表示這個“詞詞條條”。這樣一來，對字符流的編碼就變成了。這樣一來，對字符流的編碼就變成了用碼用碼字字(Code word)去替換字符流去替換字符流(Char stream)，生成生成碼字流碼字流(Code stream)，從而達(dá)到壓縮數(shù)據(jù)的目的。從而達(dá)到壓縮數(shù)據(jù)的目的。nLZ78編碼器的輸出是編碼器的輸出是碼字碼字-字符字符(W,C)對，每次輸對，每次輸出一對

28、到碼字流中，與碼字出一對到碼字流中，與碼字W相對應(yīng)的字符串相對應(yīng)的字符串(String)用字符用字符C進(jìn)行擴(kuò)展生成新的字符串進(jìn)行擴(kuò)展生成新的字符串(String)，然后添加到詞典中。然后添加到詞典中。LZ78編碼算法編碼算法步驟1：將詞典和當(dāng)前前綴P都初始化為空。步驟2：當(dāng)前字符C:=字符流中的下一個字符。步驟3：判斷PC是否在詞典中 （1）如果“是”，則用C擴(kuò)展P，即讓P:=PC，返回到步驟2。 （2）如果“否”，則 輸出與當(dāng)前前綴P相對應(yīng)的碼字W和當(dāng)前字符C， 即（W，C）； 將PC添加到詞典中； 令P:=空值，并返回到步驟2LZ78編碼舉例編碼舉例位置123456789字符ABBCBCA

29、BA步驟位置詞典輸出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：編碼過程：編碼過程：3.3.5.4 LZWLZW算法算法 J.Ziv和和A.Lempel在在1978年首次發(fā)表了介紹年首次發(fā)表了介紹第二類詞典編碼算法的文章。在他們的研究基礎(chǔ)第二類詞典編碼算法的文章。在他們的研究基礎(chǔ)上，上，Terry A.Welch在在1984年發(fā)表了改進(jìn)這種編碼年發(fā)表了改進(jìn)這種編碼算法的文章，稱為算法的文章，稱為LZW 壓縮編碼。壓縮編碼。 在編碼原理上，在編碼原理上，LZW與與LZ78相比有如下差別：相比有如下差別： LZW只輸出代

30、表詞典中的字符串只輸出代表詞典中的字符串(String)的碼的碼字字(code word)。這就意味在這就意味在開始時詞典不能是空開始時詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的的，它必須包含可能在字符流出現(xiàn)中的所有單個所有單個字符字符。即在編碼匹配時，至少可以在詞典中找到即在編碼匹配時，至少可以在詞典中找到長度為長度為1的匹配串。的匹配串。 LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。書P38 LZWLZW算法的詞典算法的詞典 LZW編碼器編碼器(軟件編碼軟件編碼器或硬件編碼器器或硬件編碼器)就是通過管就是通過管理這個詞典完成輸入與輸出理這個詞典完成輸入與輸出之間的轉(zhuǎn)換。之間的轉(zhuǎn)換。LZW編碼器的編碼器的輸入是字符流輸入是字符流(Char stream)，字符流可以是用字符流可以是用8位位ASCII字字符組成的字符串，而輸出是符組成的字符串，而輸出是用用n位位(例如例如12位位)表示的碼字表示的碼字流流 (Code stream)，碼字代表碼字代表單個字符或多個字符組成的單個字符或多個字符組成的字符串字符串(String)。LZWLZW編碼算法編碼算法步驟1：將詞典初始化為包含所有可能的單字符，當(dāng)前前綴P初始化為空。步驟2：當(dāng)前字符C:=字符流中的下一個字符。步驟3：判斷PC是否在詞典中 （1）如果“是”，則用C擴(kuò)展P，即讓P: