四川大學計算機學院多媒體基礎無損壓縮

多媒體技術基礎四川大學計算機學院陳虎huchen@數(shù)字化原理1模擬信號模擬信號指幅度的取值是連續(xù)的（幅值可由無限個數(shù)值表示）。現(xiàn)實中涉及的許多媒體對象是模擬信號

例如：聲音、圖像、視頻等數(shù)字信號數(shù)字信號是人為抽象出來的在時間上的不連續(xù)信號，是離散時間信號的數(shù)字化表示，通常由模擬信號獲得。計算機處理的對象是數(shù)字信號（二進制數(shù)“0”

和“1”）

例如：英文字符以的ASCII代碼，漢字字符的國標GB2312-80代碼表示都是二進制數(shù)字串多媒體系統(tǒng)的數(shù)模與模數(shù)轉換傳感器(聲音、圖像、視頻等--模擬）A/D計算機（數(shù)字）輸出設備（數(shù)字）D/A輸出設備（聲音、電視--等模擬）模數(shù)轉換-采樣概念：

從連續(xù)時間信號中提取離散樣本的過程；或者說在某些離散的時間點上提取連續(xù)時間信號值的過程稱為采樣。采樣按采樣間隔可分為:均勻采樣與非均勻采樣。采樣的必要性

例如，電影的連續(xù)畫面，實際上是由一組時間樣本快速播放實現(xiàn)的，數(shù)字通信系統(tǒng)，微處理器系統(tǒng)對連續(xù)時間信號的處理，都是通過采樣來實現(xiàn)的。采樣是連續(xù)時間信號和離散時間信號之間的橋梁，對連續(xù)信號而言，隨著數(shù)字處理技術的發(fā)展，越來越迫切地要求連續(xù)信號的離散化。采樣示例采樣當取出的樣本一樣時，樣本對應的連續(xù)時間函數(shù)卻不是唯一的。采樣此外，對同一個連續(xù)時間信號，當采樣間隔不同時也會得到不同的樣本序列。結論：沒有任何條件限制的情況下，從連續(xù)時間信號采樣所得到的樣本序列，不能唯一地確定原來的連續(xù)時間信號，即：一個連續(xù)時間信號必須在某一種條件下才能由其樣本來表示。采樣分析采樣樣本：采樣函數(shù)：采樣分析已采樣信號的頻譜：采樣函數(shù)頻譜：原連續(xù)時間信號：采樣分析對連續(xù)時間信號在時域理想采樣，就相當于在頻域以采樣頻率s為周期延拓，幅值減小1/T。要使頻譜不混迭，就必須使信號帶限，且上述即為時域采樣的約束條件從而我們得到怎樣抽取樣本，樣本才能唯一地表征原信號的取樣條件，下面為上述分析的一個完整總結－－采樣定理。采樣定理

設是某一個帶限信號，在||>M時，X（j）=0。如果采樣頻率

s>2

M，其中

s＝2/T,那么就唯一地由其樣本所確定。已知這些樣本值，我們能用如下辦法重建：讓采樣后的信號通過一個增益為T,截止頻率大于M，而小于（s

M）的理想濾波器，該濾波器的輸出就是。2

M稱為奈奎斯特率；

M稱為奈奎斯特頻率。數(shù)據(jù)壓縮2壓縮的必要性音頻、視頻的數(shù)據(jù)量很大，如果不進行處理，計算機系統(tǒng)幾乎無法對它進行存取和交換。

例如：一幅中等分辨率（640×480）的真彩色圖像（24b/像素），它的數(shù)據(jù)量約為0.9MB/幀，若要達到每秒25幀的全動態(tài)顯示要求，每秒所需的數(shù)據(jù)量約為22MB。對于聲音也是如此，CD音質的聲音每秒將有約為172KB的數(shù)據(jù)量。信息論1948年C.E.Shannon香農發(fā)表了題為“通信的數(shù)學理論”的論文。運用通信技術與概率論、隨機過程、數(shù)理統(tǒng)計的方法系統(tǒng)討論了通信的基本問題，得出了幾個重要而帶有普遍意義的結論：

1.闡明通信系統(tǒng)傳遞的對象就是信息

2.對信息給予科學的定量描述

3.提出了信息熵的概念信息論科學體系香農信息論壓縮理論有失真信源編碼無失真信源編碼率失真理論壓縮編碼等長編碼定理變長編碼定理最優(yōu)碼構成Huffman碼Fano碼傳輸理論有噪聲信道編碼理論碼構成糾錯碼代數(shù)編碼卷積碼網絡信道網絡信息理論網絡最佳碼保密理論保密系統(tǒng)的信息理論保密碼信息論之父TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA熵定義：設隨機變量X，取值空間Ω，Ω為有限集合。X的分布密度為p(x)，p(x)=P(X=x)x∈X，則該隨機變量的取值不確定程度，即其熵為：當使用log2時，熵的單位為比特反映一個信源發(fā)出不同信號，具有的平均信息量。熵為什么能夠進行壓縮

信息論認為：若信源編碼的熵大于信源的實際熵，該信源中一定存在冗余度（信息熵冗余）。

冗余的基本概念

指信息存在的各種性質的多余度舉例：（1）廣播員讀文稿時每分鐘約讀180字，一個漢字占兩個字節(jié)；文本數(shù)據(jù)量為360B；（2）如果對語音錄音，由于人說話的音頻范圍為20Hz到4kHz，即語音的帶寬為4kHz，若設量化位數(shù)為8bit,則一秒鐘的數(shù)據(jù)量為：

4×2×8=64kbit/s=8KB/s則一分鐘的數(shù)據(jù)是480KB。360B480KB數(shù)據(jù)冗余的類別空間冗余時間冗余統(tǒng)計冗余信息熵冗余結構冗余知識冗余視覺冗余聽覺冗余數(shù)據(jù)冗余的類別●空間冗余規(guī)則物體和規(guī)則背景的表面物理特性都具有相關性，數(shù)字化后表現(xiàn)為數(shù)據(jù)冗余?！駮r間冗余序列圖像（如電視圖像和運動圖像）和語音數(shù)據(jù)的前后有著很強的相關性，經常包含著冗余。在播出該序列圖像時，時間發(fā)生了推移，但若干幅畫面的同一部位沒有變化，變化的只是其中某些地方，這就形成了時間冗余。數(shù)據(jù)冗余的類別空間冗余和時間冗余是把圖像信號看作概率信號時反應出的統(tǒng)計特性，因此，這兩種冗余也被稱為統(tǒng)計冗余?！窠y(tǒng)計冗余●信息熵冗余信息熵實際情況又稱編碼冗余。信息熵是指一組數(shù)所攜帶的信息量。●結構冗余數(shù)字化圖像中的物體表面紋理等結構往往存在著冗余數(shù)據(jù)冗余的類別由圖像的記錄方式與人對圖像的知識差異所產生的冗余稱為知識冗余。●知識冗余

人類的視覺系統(tǒng)對于圖像場的注意在非均勻和非線性的，視覺系統(tǒng)并不是對圖像的任何變化都能感知?！褚曈X冗余

●聽覺冗余

人耳對不同頻率的聲音的敏感性是不同的，并不能察覺所有頻率的變化，對某些頻率不必特別關注，因此存在聽覺冗余。信息冗余從信息論關系中圖像信息中冗余信息，如果一個圖像的灰度級編碼，使用了多于實際需要的編碼符號，則該圖像包含了信息冗余例：如果用8位表示下面圖像的像素，我們就說該圖像存在著編碼冗余，因為該圖像的像素只有兩個灰度，用一位即可表示。統(tǒng)計冗余從統(tǒng)計的觀點，某點像素的灰度與其鄰域灰度有密切關系。因此任何給定的像素值，原理上都可以通過它的相鄰像素預測到，單個像素攜帶的信息相對是小的。對于一個圖像，很多單個像素對視覺的貢獻是冗余的。例：原圖像數(shù)據(jù)：234223231238235壓縮后數(shù)據(jù)：23411-8-73空間冗余

規(guī)則物體表面有相關性，數(shù)字化后表現(xiàn)出冗余。圖像相鄰像素之間色彩、明度相同或相似，產生信息（有意義的內容）冗余時間冗余時間發(fā)生了推移，若干幅畫面的同一部位沒有變化，于是產生了冗余結構冗余

數(shù)字化圖像中具有規(guī)則紋理的表面產生的冗余。取其中一塊編碼，其余只記錄坐標視覺心理冗余一些信息在一般視覺的處理中比其它信息的相對重要程度要小，可以忽略不計，這種信息就被稱為視覺心理冗余。33K15K數(shù)據(jù)壓縮的評價-壓縮比設：n1和n2是輸入數(shù)據(jù)和輸出數(shù)據(jù)

壓縮比為：CR=n1/n2

例如：圖像512×480，24位

輸入＝(512×480×24)/8=737280B

輸出15000B

壓縮比＝737280/15000＝49

相對數(shù)據(jù)冗余： RD=1–1/CR=(n1-n2)/n2數(shù)據(jù)壓縮的評價-壓縮質量客觀質量評價：壓縮過程對信息的損失能夠表示為原始信息與壓縮并解壓縮后信息的函數(shù)。（信噪比（SNR））例如，圖像中

數(shù)據(jù)壓縮的評價-壓縮質量主觀質量評價：以人的主觀感受作為評價標準。例如：通過視覺比較兩個圖像，給出一個定性的評價，如很粗、粗、稍粗、相同、稍好、較好、很好等，可以對所有人的感覺評分計算平均感覺分來衡量。評分評價說明1優(yōu)秀的優(yōu)秀的具有極高質量的圖像2好的是可供觀賞的高質量的圖像，干擾并不令人討厭3可通過的圖像質量可以接受，干擾不討厭4邊緣的圖像質量較低，希望能加以改善，干擾有些討厭5劣等的圖像質量很差，尚能觀看，干擾顯著地令人討厭6不能用圖像質量非常之差，無法觀看壓縮解壓縮速度算法復雜－壓縮解壓慢，壓縮效果好算法簡單－壓縮解壓快，壓縮效果差在許多應用中，壓縮和解壓可能不同時用，在不同的位置不同的系統(tǒng)中。所以，壓縮、解壓速度分別估計。

例如靜態(tài)圖像中，壓縮速度沒有解壓速度嚴格；動態(tài)圖像中，壓縮、解壓速度都有要求，因為需實時地從攝像機或其他設備中抓取動態(tài)視頻。壓縮編碼的分類數(shù)據(jù)壓縮(datacompression)與信號編碼(signalcoding)往往含義相同壓縮(compress)解壓縮/還原/重構(decompress)編碼(encode/coding)解碼/譯碼(decode)相關學科：信息論、數(shù)學、信號處理、數(shù)據(jù)壓縮、編碼理論和方法壓縮編碼的分類編碼壓縮的方法目前有很多，其分類方法根據(jù)出發(fā)點不同而有差異。一般根據(jù)根據(jù)解碼后數(shù)據(jù)與原始數(shù)據(jù)是否完全一致將編碼壓縮分為：無損壓縮編碼有損壓縮編碼壓縮編碼的分類無損壓縮是指使用壓縮后的數(shù)據(jù)進行重構(或者叫做還原，解壓縮)，重構后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構的信號與原始信號完全一致的場合。有損壓縮是指使用壓縮后的數(shù)據(jù)進行重構，重構后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原始資料表達的信息造成誤解。有損壓縮適用于重構信號不一定非要和原始信號完全相同的場合。圖像、聲音壓縮編碼的分類壓縮有損壓縮無損壓縮行程編碼LZW編碼哈夫曼編碼算術編碼無損預測編碼位平面編碼有損預測編碼分形編碼模型編碼子帶編碼神經網絡編碼變換編碼K-L變換Haar變換Walsh.Hadamard變換離散余弦變換離散傅立葉變換斜變換小波變換壓縮編碼的分類從信息語義角度分為：熵編碼、源編碼和混合編碼熵編碼(entropyencoding)（也稱平均信息量編碼）

熵編碼是一種泛指那些不考慮被壓縮信息的性質的無損編碼。它是基于平均信息量的技術把所有的數(shù)據(jù)當作比特序列，而不根據(jù)壓縮信息的類型優(yōu)化壓縮。也就是說，平均信息量編碼忽略被壓縮信息的語義內容。如RLE（runlengthencoding行程編碼）、LZW（Lempel-Ziv-Walch基于詞典的編碼算法）、Huffman編碼。壓縮編碼的分類源編碼(SourceCoding)

源編碼的冗余壓縮取決于初始信號的類型、前后的相關性、信號的語義內容等。源編碼比嚴格的平均信息量編碼的壓縮率更高。當然壓縮的程度主要取決于數(shù)據(jù)的語義內容，比起平均信息量編碼，它的壓縮比更大。簡而言之，利用信號原數(shù)據(jù)在時間域和頻率域中的相關性和冗余進行壓縮的有語義編碼。如：預測編碼：DM、ADPCM變換編碼：DCT、DWT分層編碼：如子采樣、子帶編碼其他編碼：如矢量量化、運動補償、音感編碼壓縮編碼的分類混合編碼(hybridcoding)

混合編碼=熵編碼+源編碼大多數(shù)壓縮標準都采用混合編碼的方法進行數(shù)據(jù)壓縮，一般是先利用信源編碼進行有損壓縮，再利用熵編碼做進一步的無損壓縮。如H.261、H.263、JPEG、MPEG等。壓縮編碼的分類此外，也可根據(jù)不同的依據(jù)對數(shù)據(jù)的壓縮算法進行其它不同的分類，如：按作用域在空間域或頻率域：空間方法、變換方法、混合方法按是否自適應：自適應性編碼和非適應性（靜態(tài)）編碼按碼長：定長碼和變長碼香農-范諾香農-范諾編碼(Shannon–Fanocoding)在香農的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量在計算熵時，如果對數(shù)的底數(shù)用2，熵的單位就用“香農(Sh)”，也稱“位(bit)”

?！拔弧笔?948年Shannon首次使用的術語。最早闡述和實現(xiàn)“從上到下”的熵編碼方法的人是Shannon(1948年)和Fano(1949年)，因此稱為香農-范諾(Shannon-Fano)編碼法香農-范諾編碼舉例有一幅40個像素組成的灰度圖像，灰度共有5級，分別用符號A，B，C，D和E表示。40個像素中出現(xiàn)灰度A的像素數(shù)有15個，出現(xiàn)灰度B的像素數(shù)有7個，出現(xiàn)灰度C的像素數(shù)有7個，其余情況見表2-1(1)計算該圖像可能獲得的壓縮比的理論值(2)對5個符號進行編碼(3)計算該圖像可能獲得的壓縮比的實際值符號ABCDE出現(xiàn)的次數(shù)157765出現(xiàn)的概率15/407/407/406/405/40香農-范諾編碼舉例理論值按照常規(guī)的編碼方法，表示5個符號最少需要3位，如用000表示A，001表示B，…，100表示E，其余3個代碼(101，110，111)不用。這就意味每個像素用3位，編碼這幅圖像總共需要120位。按照香農理論，這幅圖像的熵為香農-范諾編碼舉例這個數(shù)值表明，每個符號不需要用3位構成的代碼表示，而用2.196位就可以，因此40個像素只需用87.84位就可以，因此在理論上，這幅圖像的的壓縮比為120:87.84≈1.37:1，實際上就是3:2.196≈1.37香農-范諾編碼舉例(2)符號編碼對每個符號進行編碼時采用“從上到下”的方法。首先按照符號出現(xiàn)的頻度或概率排序，然后使用遞歸方法分成兩個部分，每一部分具有近似相同的次數(shù)香農-范諾編碼舉例（3）壓縮比的實際值按照這種方法進行編碼需要的總位數(shù)為30+14+14+18+15＝91，實際的壓縮比為120:91≈1.32:1霍夫曼編碼霍夫曼編碼(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“從下到上”的熵編碼方法根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少廣泛用在JPEG,MPEG,H.26X等各種信息編碼標準中霍夫曼編碼基本原理通過減少編碼冗余來達到壓縮的目的。統(tǒng)計符號的出現(xiàn)概率，建立一個概率統(tǒng)計表將最常出現(xiàn)(概率大的)的符號用最短的編碼，最少出現(xiàn)的符號用最長的編碼?；舴蚵幋a具體步驟：步驟①：按照符號出現(xiàn)概率大小的順序對符號進行排序步驟②：把概率最小的兩個符號組成一個節(jié)點P1步驟③：重復步驟②，得到節(jié)點P2，P3，P4，……，PN，形成一棵樹，其中的PN稱為根節(jié)點步驟④：從根節(jié)點PN開始到每個符號的樹葉，從上到下標上0(上枝)和1(下枝)，至于哪個為1哪個為0則無關緊要步驟⑤：從根節(jié)點PN開始順著樹枝到每個葉子分別寫出每個符號的代碼霍夫曼編碼舉例

aaaa

bbb

cc

d

eeeee

fffffff

432157（共22*8=176bits)霍夫曼編碼舉例

cbdafe7/225/224/222/22f=00e=10a=11b=011c=0100d=01011/221022/223/229/220113/22016/22103/2201編碼形式不唯一4/22)*log2(22/4)+(3/22)*log2(22/3)+(2/22)*log2(22/2)+(1/22)*log2(22/1)+(7/22)*log2(22/7)+(5/22)*log2(22/5)＝2.3678霍夫曼編碼舉例aaaa

bbb

cc

d

eeeee

fffffff

（共22*8=176bits)432157

經過Huffman編碼之后的數(shù)據(jù)為：11111111011011011010001000101101010101000000000000000(共7*2+5*2+4*2+3*3+2*4+1*4=53bits)

霍夫曼編碼a10.20a20.19a30.18a40.17a50.15a60.10a70.01100.11100.2610.3500.610010110.391.00碼字碼長1021120003001301030110401114平均碼長：2.72熵：2.58霍夫曼編碼局限性利用霍夫曼編碼，每個符號的編碼長度只能為整數(shù)，所以如果源符號集的概率分布不是2負n次方的形式，則無法達到熵極限。輸入符號數(shù)受限于可實現(xiàn)的碼表尺寸譯碼復雜需要實現(xiàn)知道輸入符號集的概率分布沒有錯誤保護功能應用舉例在圖像的編碼中首先計算頻率并以二叉樹方式進行排序來獲得編碼值，其次用編碼值取代圖像數(shù)據(jù)進入圖像文件中。編碼值的不唯一性灰度分布很不均勻和很均勻時的效率構造性差常用的且有效的方法是：將圖像分割成若干的小塊，對每塊進行獨立的Huffman編碼。例如：分成8×8的子塊，就可以大大降低不同灰度值的個數(shù)（最多是64而不是256）。應用舉例8*8分塊的編碼效率為47.27%16*16分塊的編碼效率約為61%全圖的編碼效率為91.47%霍夫曼編碼Huffman編碼討論Huffman編碼是唯一可譯碼。短的碼不會成為更長碼的啟始部分；Huffman編碼的平均碼長接近于熵缺點：需要多次排序，耗費時間算術編碼Huffman編碼的局限性：

Huffman編碼使用整數(shù)個二進制位對符號進行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設某個字符的出現(xiàn)概率為80%，該字符事實上只需要-log2(0.8)=0.322位編碼，但Huffman編碼一定會為其分配一位0或一位1的編碼?？梢韵胂?，整個信息的80%在壓縮后都幾乎相當于理想長度的3倍左右。算術編碼例1：在信源的符號數(shù)目很小的情況X:abP(X):0.90.1H=0.4690ab1a=0,b=1算術編碼例2：信源的符號的概率嚴重不對稱：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symbolHuffman編碼：a 0b 11c 10l=1.05bits/symbol冗余（Redundancy）=l-H=0.715bits/sym(213%!)算術編碼基本思想：考慮對兩個字母序列而不是單個字母編碼l=1.222/2=0.611冗余=0.276bits/symbol（27%）LetterProbabilityCodeaa0.90250ab0.0190111ac0.0285100ba0.01901101bb0.0004110011bc0.0006110001ca0.0285101cb0.0006110010cc0.0009110000算術編碼該思想還可以繼續(xù)擴展考慮長度為n的所有可能的mn

序列(已做了32)理論上：考慮更長的序列能提高編碼性能實際上：字母表的指數(shù)增長將使得這不現(xiàn)實例如：對長度為3的ASCII序列：2563=224=16M需要對長度為n的所有序列產生碼本很多序列的概率可能為0分布嚴重不對稱是真正的大問題：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symboll1=1.05,l2=0.611,…當n=8時編碼性能才變得可接受但此時|alphabet|=38=6561!!!算術編碼基本思想：算術編碼不是將單個信源符號映射成一個碼字，而是把整個消息表示為實數(shù)線上的0到1之間的一個區(qū)間，其長度等于該序列的概率，再在該區(qū)間內選擇一個代表性的小數(shù)，轉化為二進制作為實際的編碼輸出。消息序列中的每個元素都要用來縮短這個區(qū)間。消息序列中元素越多，所得到的區(qū)間就越小，當區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間。采用算術編碼每個符號的平均編碼長度可以為小數(shù)算術編碼符號串編碼：將串中使用的符號表按原編碼（如字符的ASCII編碼、數(shù)字的二進制編碼）從小到大順序排列成表。計算表中每種符號si出現(xiàn)的概率pi，然后依次根據(jù)這些符號概率大小pi來確定其在[0,1)期間中對應的小區(qū)間范圍[xi,yi)：其中，p0=0，顯然，符號si所對應的小區(qū)間的寬度就是其概率pi算術編碼輸入串編碼：設串中第j個符號cj為符號表中的第i個符號si，則可根據(jù)si在符號表中所對應區(qū)間的上下限xi和yi，來計算編碼區(qū)間

Ij=[lj,rj)。其中，dj=rj-lj為區(qū)間Ij的寬度，初值l0=0，r0=1，d0=1。顯然，lj↑而dj與rj↓。串的最后一個符號所對應區(qū)間的下限ln就是該符號串的算術編碼值.算術編碼通常，對任意序列x=x1x2…xn只需知道信源的cdf，即信源的概率模型算術編碼：編碼和解碼過程都只涉及算術運算（加、減、乘、除）

舉例2字符概率a0.3b0.7aba要編的字符串算術編碼010.3aba[0,0.3)b[0.3,1)1.劃分范圍2.開始編碼“aba”00.3ab第一個為a，編碼范圍限制在0～0.3范圍內1算術編碼00.30.09ab00.3ab1對已知區(qū)間進行再次分割第二個為b，編碼范圍限制在0.09～0.3范圍內00.30.09ab算術編碼0.090.30.153ab0ab0.3對已知區(qū)間進行再次分割第3個為a，編碼范圍限制在[0.09,0.153)范圍內0.090.090.153ab0.3算術編碼在[0.09,0.153)中任選一個浮點數(shù)來標識這個區(qū)間，如0.15，即可表示我們要編的消息為“aba”把該浮點數(shù)轉變?yōu)槎M制編碼:0010特性：區(qū)間越窄，說明符號串越長，二進制碼長越長舉例2假設信源符號為{00,01,10,11}，它們的概率分別為{0.1,0.4,0.2,0.3}對二進制消息序列10001100101101…進行算術編碼算術編碼初始化：根據(jù)信源符號的概率把間隔[0,1)分成如表2-4所示的4個子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)。其中[x,y)的表示半開放間隔，即包含x不包含y，x稱為低邊界或左邊界，y稱為高邊界或右邊界

符號00011011概率0.3初始區(qū)間[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)算術編碼確定符號的編碼范圍編碼時輸入第1個符號是10，找到它的編碼范圍是[0.5,0.7]消息中第2個符號00的編碼范圍是[0,0.1)，它的間隔就取[0.5,0.7)的第一個十分之一作為新間隔[0.5,0.52)編碼第3個符號11時，取新間隔為[0.514,0.52)編碼第4個符號00時，取新間隔為[0.514,0.5146)依此類推……消息的編碼輸出可以是最后一個間隔中的任意數(shù)算術編碼算術編碼算術編碼算術編碼

算術編碼長度為n的序列的算術編碼的平均碼長為：算術編碼的效率高：當信源符號序列很長，平均碼長接近信源的熵算術編碼在算術編碼中需要注意的問題：由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。算術編碼器對整個消息只產生一個碼字，這個碼字是在間隔[0,1)中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。算術編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導致整個消息譯錯。算術編碼

算術編碼可以是靜態(tài)的或者自適應的。在靜態(tài)算術編碼中，信源符號的概率是固定的。在自適應算術編碼中，信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改。開發(fā)動態(tài)算術編碼的原因是因為事先知道精確的信源概率是很難的，而且是不切實際的。當壓縮消息時，我們不能期待一個算術編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。帶縮放的算術編碼編碼器：一旦我們到達1.或2.，就可以忽略[0,1)的另一半還需要告知解碼器標識所在的半?yún)^(qū)間：發(fā)送0/1比特用來指示下上界所在區(qū)間將標識區(qū)間縮放到[0,1):E1:[0,0.5)=>[0,1); E1(x)=2xE2:[0.5,1)=>[0,1); E2(x)=2(x-0.5)注意：在縮放過程中我們丟失了最高位但這不成問題—我們已經發(fā)送出去了解碼器根據(jù)0/1比特并相應縮放與編碼器保持同步帶縮放的算術編碼考慮隨機變量X(ai)=i

對序列1321編碼：

Input:1321Output:

Input:-321Output:

1帶縮放的算術編碼Input:--21Output:11Input:---1Output:110Input:---1Output:1100Input:---1Output:11000

帶縮放的算術編碼假設碼字長為6輸入：1100011000000.1100012=0.76562510第1位：1Output:1Input:110001100000Output:13Input:-10001100000(左移)Input:-10001100000(0.546875)Output:132Input:---001100000(左移)Input:--0001100000(左移)帶縮放的算術編碼此時解碼最后一個符號Input:----01100000(左移)Input:-----1100000(左移)Input:-----100000

(左移)Input:-----100000Output:1321應用背景： 對于“局部冗余”的特殊類型。 主要應用于圖象表達、處理。原因：數(shù)字化的image有大量的“局部冗余”占空間大 （一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。）語義依賴典型：行程編碼（run-lengthencoding:RLE）差異映射(differencemapping)詞典編碼(DictionaryEncoding)語義依賴差異映射：算法思想：圖象表示為相鄰像素在亮度/顏色上的差異陣列，而不是像素本身的亮度/顏色值例[Laeseretal.1986]8bits/pixel(256brightness)3bits/pixel語義依賴詞典編碼詞典：全部詞語（words）常用詞語+詞語結束符號編碼方法：指向詞典的指針表指向詞典的指針表（常用詞語）+編碼（不常用詞語）語義依賴分解與編碼源信息代碼（長度）：block->blockblock->variablevariable->blockvariable->variable例：“aabbbccccdddddeeeeeefffffffgggggggg”

block->block(120)Sourcemassage codeworda 000b 001c 010d 011e 100f 101g 110space 111分解與編碼例："aabbbccccdddddeeeeeefffffffgggggggg”variable->variable(30)

Sourcemassage codewordaa 0bbb 1ccccc 10ddddd 11eeeeeee 100fffffff 101gggggggg 110space 111分解與編碼“定義字”與“自由分解”方法定義字（defined-word）方式源信息分解的長度在編碼調用之前已確定自由分解（free-parse）方式編碼算法本身決定源信息分解的長度（變長）分解與編碼典型算法定義字方式的：Shannon-FanocodingHuffmancodingUniversalcodes(通用碼)Arithmeticcoding(算術編碼)自由分解方式的：Lempel-ZivcodesAlgorithmBSTW行程編碼（RLE）基本原理：它通過將信源中相同符號序列轉換成一個計數(shù)字段再加上一個重復字符標志實現(xiàn)壓縮。

行程編碼（RLE）行程編碼(RLE）算法:x1,x2,……

xn---->(

c1,l1),(

c2,l2),……

(

ck,lk)

ci:亮度/顏色li:第i行程（相同亮度/顏色的像素的序列）的長度不需要存儲每一個象素的顏色值，而僅僅存儲一個象素的顏色值，以及具有相同顏色的象素數(shù)目就可以；或者存儲一個象素的顏色值，以及具有相同顏色值的行數(shù)。具有相同顏色并且是連續(xù)的象素數(shù)目稱為行程長度。行程編碼（RLE）例：代碼字為：（0，8),（1，3),（8，50),（1，4),(0，8）行程編碼（RLE）RLE所能獲得的壓縮比——主要是取決于圖像本身的特點。如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之，壓縮比就越小。RLE是無損壓縮技術。行程編碼（RLE）應用：尤其適用于計算機生成的圖像，對減少圖像文件的存儲空間非常有效。（對顏色豐富的自然圖像不能單純使用RLE一種編碼方法，需要和其他的壓縮編碼技術聯(lián)合應用。）商業(yè)數(shù)據(jù)處理（如連續(xù)多個0，空格）行程編碼（RLE）特點：

利用兩個字節(jié)代替連續(xù)出現(xiàn)的同一數(shù)據(jù)。通常需要在表示重復次數(shù)的字節(jié)中利用前一位或兩位作為標志位，提示應用程序中隨后的極為表示次數(shù)，另一字節(jié)表示重復數(shù)據(jù)的值。舉例說明：

aaaa

bbb

cc

d

eeeee

fffffff

(共22*8=176bits)

4a3b2c1d5e7f(共12*8=96bits)BMP行程編碼BI_RLE8的編碼方式：由2個字節(jié)組成，第一個字節(jié)指定使用相同顏色的象素數(shù)目，第二個字節(jié)指定使用的顏色索引。此外，這個字節(jié)對中的第一個字節(jié)可設置為0，聯(lián)合使用第二個字節(jié)的值表示：

第二個字節(jié)的值為0：行的結束。

第二個字節(jié)的值為1：圖象結束。

第二個字節(jié)的值為2：其后的兩個字節(jié)表示下一個象素從當前開始的水平和垂直位置的偏移量。

BMP行程編碼例如：

0304050602780002050102780000091E0001

這些壓縮數(shù)據(jù)可解釋為：

0304040404

05060606060606

02787878

00020501從當前位置右移5個位置后向下移一行

02787878

0000行結束

091E1E1E1E1E1E1E1E1E1E

0001編碼圖象結束PCX行程編碼PCX簡介：真彩色圖像以行為單位，按色面存放128字節(jié)的文件頭圖像數(shù)據(jù)調色板PCX行程編碼圖像數(shù)據(jù)以字節(jié)為單位進行編碼按行進行壓縮長度在前，灰度值在后單像素沒有長度值以最高兩位作為判斷是重復數(shù)還是原像素。最高兩位為1（B0除外），說明是重復數(shù)，否則，說明是原像素值

PCX行程編碼重復像素長度iC最大值為26-1=63，如果遇到iC大于63的情況，則分為小于63的幾段，分別處理。如果遇到不重復的單個像素P： 如果P<0xC0（192）直接存入該像素值， 否則先存入長度1，再存入像素值（192-255之間的單像素圖像不減反增）PCX行程編碼例

0X15····0X150X5A0X670X5F0X710X6911

0X35····0X350XD70XD90XCC80

[0XCB0X15]0X5A0X670X5F0X710X69

[0XFF0X35][0XD10X35][0XC10XD7][0XC10XD9][0XC10XCC]行程編碼（RLE）對于有大面積色塊的圖像，壓縮效果很好對于紛雜的圖像，壓縮效果不好，最壞情況下（圖像中每兩個相鄰點的顏色都不同），會使數(shù)據(jù)量加倍，所以現(xiàn)在單純采用行程編碼的壓縮算法用得并不多二維行程編碼二維行程編碼要解決的核心問題是：將二維排列的像素，采用某種方式轉化成一維排列的方式。之后按照一維行程編碼方式進行編碼兩種典型的二維行程編碼的排列方式二維行程編碼數(shù)據(jù)量：64*8=512(bit)二維行程編碼如果按照方式(a)掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127二維行程編碼行程編碼為：

數(shù)據(jù)量：43*（3+8）=473(bit)(94.22%)（7，130），（2，130），（4，129），（2，130），（1，129）；（1，127），（1，128），（1，127），（1，129），（1，131），（1，130），（1，132），（2，134），（2，133），（1，132），（1，130），（1，129），（1，128），（1，127），（1，128），（1，127），（1，128），（1，127），（1，125），（1，126），（2，129），（1，127），（1，129），（1，133），（1，132），（1，131），（1，129），（2，130），（1，129），（3，130），（1，129），（1，130），（2，132），（2，131），（1，130），（1，126），（2，128），（2，127）比特平面編碼思想：

對于灰度或彩色圖像，如果每個像素用k位表示，將相同位上的0，1取出，就可以形成k個N*N的二值圖像。將每一個二值圖像稱為一個比特平面。希望連續(xù)的0/1出現(xiàn)的概率增大.比特平面編碼二值圖像壓縮標準靜止圖像（stillimages）包括兩類：黑白（二值）靜止圖像連續(xù)色調（彩色或灰度）靜止圖像。二值圖像壓縮方法主要用于不包含任何連續(xù)色調信息的文檔，或者連續(xù)色調信息(大多數(shù)為圖片)可以用黑白的模式來獲取的應用。例如辦公／商業(yè)文檔，手寫文本、線條圖形、工程圖等。二值圖像壓縮標準二值圖像壓縮的標準：3類（CCITTGroup3）數(shù)字傳真標準4類（CCITTGroup4）數(shù)字傳真標準JBIG（JointBi-levelImageexpertsGroup，二值圖像聯(lián)合專家組）標準二值圖像壓縮標準G3和G4－由CCITT國家電話電報咨詢委員會(consultativecommitteeoftheinternationaltelephoneandtelegraph)的兩個小組(Group3和Group4)負責制定的，最初為傳真應用而設計（1）G3采用一維行程長度編碼；（2）行程采用Huffman編碼；（3）0－63之間的行程，用單個碼字即終止碼表示；（4）大于63的游長用一個形成碼和一個終止碼組合表示。形成碼表示實際行程對64的倍數(shù)；（5）G3能達到15：1的壓縮比；（6）G4采用二維行程程度編碼，壓縮比比G3提高30％。二值圖像壓縮標準一維壓縮基本思想：1）每一行行首、尾編碼行首：用一個白行程碼開始。如果行首是黑像素，則 用零長度的白00110101開始。行尾：用行尾編碼字(EOL)000000000001結束。2）圖像首、尾編碼圖像首行：用一個EOL開始。圖像結尾：用連續(xù)6個EOL結束。3）圖像內部編碼內部編碼：長度小于63的用哈夫曼編碼，大于63的用組合編碼：大于63的長度編碼+小于63的余長度編碼二值圖像壓縮標準長度小于63的哈夫曼編碼行程長度白編碼 黑編碼0 00110101 00001101111 000111 0102 0111 113 1000 104 1011 0115 1100 001161 00110010 00000101101062 00110011 00000110011063 00110100 000001011011二值圖像壓縮標準長度大于63的組合編碼

行程長度白編碼 黑編碼64 11011 0000001111128 10010 000011001000192 010111 000011001001256 0110111 000001011011320 00110110 000000110011384 00110111 0000001101001600 010011010 00000010110111664 011000 00000011001001728 010011011 0000001100101二值圖像壓縮標準二維壓縮

1)基本思想：利用上一行相同改變元素的位置，來為當前行編碼假設相臨兩行改變元素位置相似的情況很多且上一行改變元素距當前行改變元素的距離，小于行程的長度，從而可以降低編碼長度a0b1b2a1a2參考行當前行二值圖像壓縮標準2)定義幾個重要符號：參考行：當前處理行的前一行。改變元素：與前一個像素值不同的像素參考元素：一共有5個（當前行3個，參考行2個）：a0：當前處理行上，與前一個像素值不同的像素。 行首元素是本行的第一個a0a1：a0右邊下一個改變元素。a2：a1右邊下一個改變元素。b1：參考行上在a0右邊，且與a0值相反的改變元素b2：b1右邊下一個改變元素。a0b1b2a1a2參考行當前行二值圖像壓縮標準3)編碼方法：對三種情況的三種編碼方式：（1）通過編碼方式：條件：b2在a1的左邊，排除參考行兩個改變元素都在 a1左邊的情況編碼：0001，動作：把a0移到b2的下面b1b2a1a2a0新a0二值圖像壓縮標準3)編碼方法：對三種情況的三種編碼方式：（2）水平編碼方式：條件：a1到b1之間的距離大于3，放棄利用上一行編碼編碼：001+M(a0a1)+M(a1a2)，M：一維行程編碼動作：把a0移到a2。a0b1b2a1a2a1b1二值圖像壓縮標準3）編碼方法：對三種情況的三種編碼方式：（3）垂直編碼方式：條件：a1到b1之間的距離小于等于3，利用上一行編碼。編碼：見CCITT二維編碼表（下頁）動作：把a0移到a1a0b1b2a1a2a1b1二值圖像壓縮標準4)CCITT二維編碼表

a1與b1的距離 編碼：

a1在b1下面： 1 a1在b1右邊1個 001 a1在b1右邊2個 000011 a1在b1右邊3個 0000011 a1在b1左邊1個 010 a1在b1左邊2個 000010 a1在b1左邊3個 0000010二值圖像壓縮標準CCITTGroup3基本思想：Group3標準應用了一種非適應的，一維和二維混合的行程編碼技術在該編碼中，每一個K行組的最后K-1行（K=2或4），有選擇地用二維編碼方式。二值圖像壓縮標準CCITTGroup4基本思想：Group4標準是Group3標準簡化或改進版本只用二維壓縮編碼。且為非適應二維編碼方法每一個新圖像的第一行的參考行是一個虛擬的白行二值圖像壓縮標準JBIG是“二值圖像聯(lián)合專家組（JointBi-levelImageexpertsGroup）”的簡稱。它建立于1988年，是一個由國際標準實體和主要公司提名產生的專家組，致力于制訂二值圖像編碼標準?！奥?lián)合”指的是他們同時為ISO、IEC和ITU-T制訂標準。JBIG的正式名稱，在ISO和IEC叫ISO/IECJTC1SC29第一工作組，在ITU-T，則稱為ITU-TSG8。JBIG和JPEG一同工作，同時為JPEG和JBIG制訂標準。人們常常將他們制訂的這兩種標準分別簡稱為JPEG標準和JBIG標準，或直接稱為JPEG和JBIG。二值圖像壓縮標準JBIG1在性能上有很大提高JBIG1采用順序傳輸模式來適應瀏覽技術(數(shù)字信息檢索和恢復)的要求，這項技術已普遍用于現(xiàn)代圖書館和網絡數(shù)據(jù)庫JBIG1結合了預測建模、自適應和無損編碼等技術選擇算術編碼作為數(shù)字壓縮的基礎，能夠適應所遇到的圖像統(tǒng)計概率。用細化網格里的黑色像素密度代表灰度，因為人眼的分辨能力很有限，人的視覺系統(tǒng)會把這些小點平滑地聯(lián)起來。對計算機生成的圖像。JBIG1采用干凈自然的圖像邊緣來改善性能。二值圖像壓縮標準缺省的傳輸模式是順序模式在順序模式中，全分辨率圖像ID從左邊進入，圖像經過一連串的降低分辨率達到ID-1，…，I0。最低分辨率的水平稱為底層，所有的高一點的分辨率水平稱為差分層。描述底層的信息最先發(fā)送，然后是逐步向上的差分層信息。除非接收到信號中止這個過程，這樣一直到全分辨率。無損預測編碼預測編碼：

數(shù)字圖像或者音頻按照行或列從新排列后可以得到一個一位信號序列。預測編碼就是根據(jù)這個信號序列的一些已知情況來預測以后信號可能發(fā)生的情況，然后對預測的誤差進行編碼而不是直接對信號進行。當預測比較準確、誤差較小是，這種編碼方式就能達到數(shù)據(jù)壓縮的目的。無損預測編碼基本思想圖像相鄰像素間存在很強的相關性，通過觀察其相鄰像素取值，可預測一像素的大概情況。預測值和實際值存在誤差，稱為預測誤差。預測誤差的方差必然比原圖像像素的方差小，因此對預測誤差編碼必然壓縮其平均碼長。對預測誤差進行編碼的技術稱為DPCM（差分脈沖編碼調制）。無損預測編碼無損預測編碼無損預測編碼預測誤差的熵對比一幅圖像和其差分圖像的標準差和熵。不同圖像的差分圖像直方圖分布形態(tài)大致相同，只是方差有所不同。無損預測編碼預測方程式線性預測：如果ai是常數(shù)，則為時不變線性預測，否則為自適應線性預測（ADPCM）最簡單的預測方程：無損預測編碼預測器整數(shù)舍入符號編碼器預測器符號解碼器SS源數(shù)據(jù)壓縮數(shù)據(jù)恢復數(shù)據(jù)預測誤差,enfnf^nen+f^n++-fn壓縮數(shù)據(jù)無損預測編碼為實現(xiàn)無失真編碼，通常對差分進行熵編碼（通常是Huffman編碼）；預測誤差熵編碼的步驟：建立碼表和編碼。通常采用一個通用碼表，節(jié)省建立專用碼表時間，由此帶來壓縮比損失較?。痪幋a：若對差分所有灰度建立碼表，則項數(shù)較多。通常對－16~16采用Huffman編碼，其他直接用前綴＋實際灰度值。無損預測編碼一副數(shù)字圖像或一段音頻可以看成一個空間點陣，圖像信號不僅在水平方向是相關的，在垂直方向也是相關的。根據(jù)已知樣值與待預測樣值間的位置關系，可以分為：（1）一維預測（行內預測）：利用同一行上相鄰的樣值進行預測。（2）二維預測（幀內預測）：利用同一行和前面幾行的數(shù)據(jù)進行預測。（3）三維預測（幀間預測）：利用相鄰幾幀（或不同波段）上的取樣值進行預測無損預測編碼舉例：公式：中取：m=2，a1=a2=1/2f={154,159,151,149,139,121,112,109,129}預測值f2=1/2*(154+159)156 e2=151–

156=-5 f3=1/2*(159+151)=155 e3=149–155=

-6 f4=1/2*(151+149)=150 e4=139–150=-11 f5=1/2*(149+139)=144 e5=121–144=

-23 f6=1/2*(139+121)=130 e6=112–130=-18 f7=1/2*(121+112)116 e7=109–116=-7 f8=1/2*(112+109)110 e8=129–110=19無損預測編碼這種壓縮算法被應用到JPEG標準的無損壓縮模式之中，中等復雜程度的圖像壓縮比可達到2:1。cabx選擇值預測值0非預測1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三鄰域預測法無損預測編碼視頻信號的冗余度主要體現(xiàn)在空間相關性（幀內）、時間相關性（幀間）和色度空間表示上的相關性。對于每秒30幀的視頻信號，其相繼幀之間存在極強的相關性。據(jù)統(tǒng)計256級灰度的黑白圖像序列，幀間差值超過3的象素數(shù)不超過4％。所以在活動圖像序列中可以利用前面的幀來預測后面的幀，以實現(xiàn)數(shù)據(jù)壓縮。幀間預測編碼技術被廣泛應用到H.261、H.263、MPEG-1和MPEG-2等視頻壓縮標準之中。無損預測編碼運動補償預測將前一個畫面的數(shù)值作為后一個畫面的預測值。編碼器運動補償圖像輸入運動矢量輸出-譯碼器幀緩存運動估計預測誤差輸出無損預測編碼無損預測編碼無損預測編碼無損預測編碼無損預測編碼無損預測編碼無損預測編碼詞典編碼文本中的詞用它在詞典中表示位置的號碼代替的一種無損數(shù)據(jù)壓縮方法。采用靜態(tài)詞典編碼技術時，編碼器需要事先構造詞典，解碼器要事先知道詞典。采用動態(tài)辭典編碼技術時,編碼器將從被壓縮的文本中自動導出詞典，解碼器解碼時邊解碼邊構造解碼詞典。詞典編碼詞典編碼主要利用數(shù)據(jù)本身包含許多重復的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我們如果用一些簡單的代號代替這些字符串，就可以實現(xiàn)壓縮，實際上就是利用了信源符號之間的相關性。字符串與代號的對應表就是詞典。實用的詞典編碼算法的核心就是如何動態(tài)地形成詞典，以及如何選擇輸出格式以減小冗余第一類編碼算法第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經出現(xiàn)過的字符串替代重復的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。LZ77算法LZ77算法在某種意義上又可以稱為“滑動窗口壓縮”，該算法將一個虛擬的，可以跟隨壓縮進程滑動的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長度。使用固定大小窗口進行詞語匹配，而不是在所有已經編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進程滑動詞典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。LZ77算法1、從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進行步驟2，否則進行步驟3。2、輸出三元符號組(off,len,c)。其中off為窗口中匹配字符串相對窗口邊界的偏移，len為可匹配的長度，c為下一個字符，即不匹配的第一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟1。3、輸出三元符號組(0,0,c)。其中c為下一個字符。然后將窗口向后滑動1個字符，繼續(xù)步驟1。LZ77算法LZ77算法AABCBBABCA步驟位置匹配串輸出11－－0,0,A22A1,1,B34－－0,0,C45B2,1,B57ABC5,3,ALZSS算法LZ77通過輸出真實字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個方面，一是空指針，二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個匹配串中的字符。LZSS算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針（匹配串長度大于等于MIN_LENGTH），否則就輸出真實字符。另外要輸出額外的標志位區(qū)分是指針還是字符LZSS算法1、從當前壓縮位置開始，考察未編碼的字符，并試圖在滑動窗口中找出最長的匹配字符串，如果匹配串長度len大于等于最小匹配串長度（len>=MIN_LENGTH），則進行步驟2，否則進行步驟3。2、輸出指針二元組(off,len)。其中off為窗口中匹配字符串相對窗口邊界的偏移，len為匹配串的長度，然后將窗口向后滑動len個字符，繼續(xù)步驟1。3、輸出當前字符c，然后將窗口向后滑動1個字符，繼續(xù)步驟1。LZSS算法位置1234567891011字符AABBCBBAABC步驟位置匹配串輸出11－－A22AA33－－B44BB55－－C66BB（3，2）78AAB（7，3）811CC輸入數(shù)據(jù)流：編碼過程MIN_LEN=2LZSS算法在相同的計算機環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡單。這也就是為什么這種算法成為開發(fā)新算法的基礎，許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip,GZip,ARJ,LHArc和ZOO等等，其差別僅僅是指針的長短和窗口的大小等有所不同。LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。第二類詞典編碼第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典(dictionaryofthephrases)”，這種短語可以是任意字符的組合。編碼數(shù)據(jù)過程中當遇到已經在詞典中出現(xiàn)的“短語”時，編碼器就輸出這個詞典中的短語的“索引號”，而不是短語本身。LZ78算法LZ78的編碼思想是不斷地從字符流中提取新的字符串(String)，通俗地理解為新“詞條”，然后用“代號”也就是碼字(Codeword)表示這個“詞條”。這樣一來，對字符流的編碼就變成了用碼字(Codeword)去替換字符流(Charstream)，生成碼字流(Codestream)，從而達到壓縮數(shù)據(jù)的目的。LZ78編碼器的輸出是碼字-字符(W,C)對，每次輸出一對到碼字流中，與碼字W相對應的字符串(String)用字符C進行擴展生成新的字符串(String)，然后添加到詞典中。LZ78算法步驟1：將詞典和當前前綴P都初始化為空。步驟2：當前字符C:=字符流中的下一個字符。步驟3：判斷P＋C是否在詞典中（1）如果“是”，則用C擴展P，即讓P:=P＋C，返回到步驟2。（2）如果“否”，則輸出與當前前綴P相對應的碼字W和當前字符C，即（W，C）；將P＋C添加到詞典中；令P:=空值，并返回到步驟2LZ78算法位置123456789字符ABBCBCABA步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)輸入數(shù)據(jù)流：編碼過程：LZW算法J.Ziv和A.Lempel在1978年首次發(fā)表了介紹第二類詞典編碼算法的文章。在他們的研究基礎上，TerryA.Welch在1984年發(fā)表了改進這種編碼算法的文章，因此把這種編碼方法稱為LZW(Lempel-ZivWalch)壓縮編碼。在編碼原理上，LZW與LZ78相比有如下差別：LZW只輸出代表詞典中的字符串(String)的碼字(codeword)。這就意味在開始時詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個字符。即在編碼匹配時，至少可以在詞典中找到長度為1的匹配串。

LZW編碼是圍繞稱為詞典的轉換表來完成的。LZW算法

LZW編碼器(軟件編碼器或硬件編碼器)就是通過管理這個詞典完成輸入與輸出之間的轉換。LZW編碼器的輸入是字符流(Charstream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼字流(Codestream)，碼字代表單個字符或多個字符組成的字符串(String)。LZW算法步驟1：將詞典初始化為包含所有可能的單字符，當前前綴P初始化為空。步驟2：當前字符C:=字符流中的下一個字符。步驟3：判斷P＋C是否在詞典中（1）如果“是”，則用C擴展P，即讓P:=P＋C，返回到步驟2。（2）如果“否”，則輸出與當前前綴P相對應的碼字W；將P＋C添加到詞典中；令P:=C，并返回到步驟2LZW算法位置123456789字符ABBABABAC步驟位置碼字詞典輸出1A2B3C114AB1225BB2336BA2447ABA4558ABAC76－－－3輸入數(shù)據(jù)流：LZW算法

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因為它不需要執(zhí)行那么多的綴-符串比較操作。對LZW算法進一步的改進是增加可變的碼字長度，以及在詞典中刪除老的綴-符串。在GIF圖像格式、TIFF圖像格式和UNIX的壓縮程序中已經采用了這些改進措施之后的LZW算法。

LZW算法取得了專利，專利權的所有者是美國的一個大型計算機公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產公司之外，可以免費使用LZW算法。GIF例子：GIF和TIFF都使用LZW壓縮法。下面以GIF為例進行介紹：1）GIF簡介（多圖像、256色）文件結構： 文件頭信息：標識（GIF）、版本號 屏幕描述：屏幕長、寬、背景色等 全局調色板：長度（256x3）//三個256色的調色板GIF

圖象描述：描述圖像塊在屏幕上的左上角位置及寬高 局部調色板:長度（256x3）//三個256色的調色板，每個圖像可有一個 圖像數(shù)據(jù)：用LZW方式壓縮，用256字節(jié)的塊來存放 擴充塊描述：有四種擴充塊文件頭信息LZW壓縮圖像數(shù)據(jù)全局調色板屏幕描述圖像描述局部調色板擴充數(shù)據(jù)塊GIF初始化字典輸出清除標記LZW_CLEARTemp=空串k=從輸入流中讀一個字符是結尾標志嗎？Temp+k在字典中嗎？輸出Temp的編碼把新串Temp+k加到字典中Temp=kTemp=Temp+k輸出Temp的編碼輸出結束標記GIF編碼舉例：設字符集{a,b,c,d}， 串：aabdaadaa

壓縮字典 臨時串輸入串編碼

0 a T=temp+ a 1 b T=a + a0 2 c T=a + b00 3 d T=b + d 001 4 aa T=d + a 00135 ab T=a + a 6 bd T=aa + d 001347 da T=d + a