dd數(shù)據(jù)壓縮技術(shù)概論

1、王詠剛 2001年2月數(shù)據(jù)壓縮技術(shù)概論 壓縮技術(shù)簡史 壓縮技術(shù)基礎(chǔ) Huffman編碼 算術(shù)編碼 LZ77和LZW算法 JPEG算法 通用壓縮工具比較1壓縮技術(shù)分類通用數(shù)據(jù)壓縮（均為無損壓縮）多媒體數(shù)據(jù)壓縮（無損和有損壓縮）基于統(tǒng)計模型的壓縮技術(shù)基于字典模型的壓縮技術(shù)Huffman編碼算術(shù)編碼LZ77LZ78LZW圖像壓縮音頻和視頻壓縮MPEG等二值圖像CCITTJBIG等灰度圖像FELICSJPEG等彩色圖像RLE編碼JPEG等矢量圖像PostScriptWMFCAD等2壓縮技術(shù)的應(yīng)用電報、傳真(CCITT)通訊(Modem/網(wǎng)絡(luò)協(xié)議)存儲(壓縮池)文件系統(tǒng)(壓縮扇區(qū))圖像(GIF/TIFF

2、/JPEG)音頻(MP3)視頻(MPEG/RM)數(shù)據(jù)庫(B+樹)歸檔(TAR/ZIP)密碼學(xué)(消除數(shù)據(jù)的原始特征)全文索引(倒排索引表)編譯(JAVA)程序設(shè)計(算法/空間和時間效率)人工智能(專家系統(tǒng)/知識樹)3壓縮技術(shù)起源信息壓縮技術(shù)的起源比計算機(jī)的發(fā)明早幾千年4信息論信息存在冗余通過采用一定的模型和編碼方法，可以降低這種冗余度貝爾實驗室的 Claude Shannon 和 MIT 的 R.M.Fano幾乎同時提出了最早的對符號進(jìn)行有效編碼從而實現(xiàn)數(shù)據(jù)壓縮的 Shannon-Fano 編碼方法。5D.A.Huffman1952 年 發(fā)表論文：“最小冗余度代碼的構(gòu)造方法”A Method f

3、or the Construction of Minimum Redundancy CodesUNIX 系統(tǒng)上一個不太為現(xiàn)代人熟知的壓縮程序 COMPACT 就是 Huffman 0 階自適應(yīng)編碼的具體實現(xiàn) 80 年代初，Huffman 編碼又在 CP/M 和 DOS 系統(tǒng)中實現(xiàn)，其代表程序叫 SQHuffman時代：60 年代、70 年代乃至 80 年代的早期6接近極限熵80年代早期，數(shù)學(xué)家們設(shè)計出算術(shù)編碼方法(Arithmetic Coding)可以證明，算術(shù)編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號精確表達(dá)原始信息內(nèi)容 但是，在同樣的計算機(jī)系統(tǒng)上，算術(shù)編碼雖然可以得到最

4、好的壓縮效果，卻要消耗也許幾十倍的計算時間 算術(shù)編碼是部分匹配預(yù)測(Predication by Partial matching, PPM)技術(shù)的變體7以色列人Jacob Ziv 和 Abraham Lempel1978 年 發(fā)表論文：“通過可變比率編碼的獨立序列的壓縮”Compression of Individual Sequences via Variable-Rate Coding字典編碼時代：LZ77和LZ78壓縮算法1977 年 發(fā)表論文：“順序數(shù)據(jù)壓縮的一個通用算法”A Universal Algorithm for Sequential Data Compression8LZ

5、W算法Terry Welch Welch 實現(xiàn)了 LZ78 算法的一個變種 LZW算法UNIX：使用 LZW 算法的 Compress 程序MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。 1984 年 發(fā)表論文：“高性能數(shù)據(jù)壓縮技術(shù)”A Technique for High-Performance Data Compression 9通用數(shù)據(jù)壓縮80年代中期以后，對LZ77算法進(jìn)行改進(jìn)Haruyasu Yoshizaki(Yoshi) 的 LHarcRobert Jung 的 ARJ 從PKZip到WinZip：通用數(shù)據(jù)壓縮格式標(biāo)準(zhǔn) ZIPLZ77、LZ78、LZW 一起

6、壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域10多媒體數(shù)據(jù)壓縮國際電報電話咨詢委員會( CCITT ) ：針對二值圖像的一系列壓縮標(biāo)準(zhǔn)，如 CCITT Group3、CCITT Group4 等 (此外還包括CCITT與ISO共同制訂的JBIG標(biāo)準(zhǔn)) 。70 年代末 80 年代初：數(shù)學(xué)家們提出了損失壓縮精度以換取壓縮率的嶄新思路。國際標(biāo)準(zhǔn)化組織( ISO )和 CCITT 聯(lián)合組成了兩個委員會：靜態(tài)圖像聯(lián)合專家小組( JPEG )和動態(tài)圖像聯(lián)合專家小組( MPEG )。誕生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列標(biāo)準(zhǔn)。PostScript矢量圖形格式：起源于 1976 年的

7、Evans & Sutherland 計算機(jī)公司，當(dāng)時的名字是 Design System。1978 年，John Warnock 和 Martin Newel 將其演變?yōu)?JAM 語言。1982 年，John Warnock 和 Chuck Geschke 創(chuàng)建了著名的 Adobe System 公司，第三次設(shè)計和實現(xiàn)了這個語言，并稱其為 PostScript。11技術(shù)準(zhǔn)備：什么是熵熵來源于40年代由Claude Shannon創(chuàng)立的信息論中的一條定理，這一定理借用了熱力學(xué)中的名詞“熵”( Entropy )來表示一條信息中真正需要編碼的信息量：考慮用 0 和 1 組成的二進(jìn)制數(shù)碼為含有 n

8、 個符號的某條信息編碼，假設(shè)符號 Fn 在整條信息中重復(fù)出現(xiàn)的概率為 Pn，則該符號的熵也即表示該符號所需的二進(jìn)制位數(shù)為：En = - log2( Pn )整條信息的熵也即表示整條信息所需的二進(jìn)制位數(shù)為：E = knEn例：對信息aabbaccbaa，字符串長度為 10，字符a、b、c分別出現(xiàn)了5、3、2次，則Ea=-log2(0.5)=1 Eb=-log2(0.3)=1.737 Ec=-log2(0.2)=2.322E= 5Ea + 3Eb + 2Ec =14.855 位對比一下，我們用ASCII編碼表示該信息需要80位12技術(shù)準(zhǔn)備：模型使用模型：得到字符或單詞在信息中出現(xiàn)的概率靜態(tài)/半靜態(tài)

9、模型自適應(yīng)模型Claude Shannon的“聚會游戲”(party game)：他每次向聽眾公布一條被他隱藏起一個字符的消息，讓聽眾來猜下一個字符，一次猜一個，直到猜對為止。然后，Shannon 使用猜測次數(shù)來確定整個信息的熵。（人的語言經(jīng)驗）靜態(tài)字典模型自適應(yīng)字典模型統(tǒng)計模型字典模型13技術(shù)準(zhǔn)備：編碼通過模型，我們可以確定對某一個符號該用多少位二進(jìn)制數(shù)進(jìn)行編碼。現(xiàn)在的問題是，如何設(shè)計一種編碼方案，使其盡量精確地用模型計算出來的位數(shù)表示某個符號。前綴編碼規(guī)則：任何一個符號的編碼都不是另一個符號編碼的前綴。最簡單的前綴編碼字符編碼A0B10C110D1110E11110111101111000

10、10 D A B B D C E A A B 14技術(shù)準(zhǔn)備：壓縮=模型+編碼輸入模型編碼輸出符號概率代碼15Shannon-Fano編碼cabcedeacacdeddaaabaababaaabbacdebaceada a 16b 7c 6d 6e - 5 a 16b 7-c 6-d 6e - 5 例子中的信息編碼為：10 00 01 10 111 110 111 00 10 00 10 .碼長共91位，而使用ASCII編碼表示上述信息共需要240位a 00b 01c 10d 110e 111root0010111abcde16Huffman編碼cabcedeacacdeddaaabaababa

11、aabbacdebaceada a 16b 7c 6d 6e - 5 例子中的信息編碼為：101 0 100 101 111 110 111 0 101 0 101 .碼長88位，比Shannon-Fano編碼略短一些a 0b 100c 101d 110e 111root00111abcde00117整數(shù)位編碼與信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 該信息的熵經(jīng)計算可知為86.601位符號理想位數(shù)（熵）S-F編碼需要位數(shù)Huffman編碼需要位數(shù)a1.32221b2.51523c2.73723d2.73733e3.00033總計86.60191

12、8818另：Huffman編碼還有一個變種范式Huffman編碼，可以有效減少編碼字典的存儲空間。Huffman編碼的模型選擇奇怪的段落If Youth，throughout all history，had had a champion to stand up for it；to show a doubting world that a child can think；and，possibly，do it practically；you wouldnt constantly run across folks today who claim that a child dont know anyt

13、hing.“- Gadsby by E.V.Wright, 1939.19算術(shù)編碼假設(shè)某個字符的出現(xiàn)概率為 80%，該字符事實上只需要 -log2(0.8) = 0.322 個二進(jìn)制位進(jìn)行編碼難道真的能只輸出 0.322 個 0 或 0.322 個 1 嗎？算術(shù)編碼的輸出是：一個小數(shù)算術(shù)編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于0和1之間的二進(jìn)制小數(shù)。例如算術(shù)編碼對某條信息的輸出為1010001111，那么它表示小數(shù)0.1010001111，也即十進(jìn)制數(shù)0.6420算術(shù)編碼例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb第

14、一步：在沒有開始壓縮進(jìn)程之前，假設(shè)我們對 a b c 三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應(yīng)模型），即認(rèn)為三者的出現(xiàn)概率相等，也就是都為1/3，我們將0-1區(qū)間按照概率的比例分配給三個字符，即a從0.0000到0.3333，b從0.3333到0.6667，c從0.6667到1.0000。用圖形表示就是：1.00000.66670.33330.0000Pc = 1/3Pb = 1/3Pa = 1/321算術(shù)編碼第二步：現(xiàn)在我們拿到第一個字符b，讓我們把目光投向b對應(yīng)的區(qū)間0.3333-0.6667。這時由于多了字符b，三個字符的概率分布變成：Pa=1/4，Pb=2/4，Pc=1/4。

15、好，讓我們按照新的概率分布比例劃分0.3333-0.6667這一區(qū)間，劃分的結(jié)果可以用圖形表示為：0.66670.58340.41670.3333Pc = 1/4Pb = 2/4Pa = 1/4例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb22算術(shù)編碼第三步：接著我們拿到字符c，我們現(xiàn)在要關(guān)注上一步中得到的c的區(qū)間 0.5834-0.6667。新添了c以后，三個字符的概率分布變成Pa=1/5，Pb=2/5，Pc=2/5。我們用這個概率分布劃分區(qū)間0.5834-0.6667：0.66670.63340.60010.5834Pc = 2/5Pb = 2

16、/5Pa = 1/5例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb23算術(shù)編碼第四步：現(xiàn)在輸入下一個字符c，三個字符的概率分布為：Pa=1/6，Pb=2/6，Pc=3/6。我們來劃分c的區(qū)間0.6334-0.6667：0.66670.65010.63900.6334Pc = 3/6Pb = 2/6Pa = 1/6例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb24算術(shù)編碼第五步：輸入最后一個字符b，因為是最后一個字符，不用再做進(jìn)一步的劃分了，上一步中得到的b的區(qū)間為0.6390-0.6501，好，讓我們在

17、這個區(qū)間內(nèi)隨便選擇一個容易變成二進(jìn)制的數(shù)，例如0.64，將它變成二進(jìn)制0.1010001111，去掉前面沒有太多意義的0和小數(shù)點，我們可以輸出1010001111，這就是信息被壓縮后的結(jié)果，我們完成了一次最簡單的算術(shù)壓縮過程0.66670.65010.63900.6334Pc = 3/6Pb = 2/6Pa = 1/6例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb輸出:(0.64)10 = (0.1010001111)225自適應(yīng)模型的階h(t)(t)gh(t)igh(t)例文：the weight of .0階1階2階3階問題：半靜態(tài)模型和自適應(yīng)

18、模型轉(zhuǎn)義碼的使用存儲空間問題26LZ77算法字典模型：現(xiàn)代漢語詞典以及下面的例子27LZ77算法LZ77算法的基本流程：“滑動的窗口”1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步驟 3。2、輸出三元符號組(off,len,c)。其中off為窗口中匹配字符串相對窗口邊界的偏移，len為可匹配的長度，c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟 1。3、輸出三元符號組(0,0,c)。其中c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟 1。28LZ77算法應(yīng)用實例：窗口大小為10個字符，剛編碼過的

19、10個字符為“abcdbbccaa”，即將編碼的10個字符為 “abaeaaabaee”。我們首先發(fā)現(xiàn)，可以和待編碼字符匹配的最長串為ab(off=0,len=2), ab的下一個字符為a，我們輸出三元組：(0,2,a)現(xiàn)在窗口向后滑動3個字符，窗口中的內(nèi)容為：dbbccaaaba下一個字符e在窗口中沒有匹配，我們輸出三元組：(0,0,e)窗口向后滑動1個字符，其中內(nèi)容變?yōu)椋篵bccaaabae我們馬上發(fā)現(xiàn)，要編碼的aaabae在窗口中存在(off=4,len=6)，其后的字符為e，我們可以輸出：(4,6,e)這樣，我們將可以匹配的字符串都變成了指向窗口內(nèi)的指針，并由此完成了對上述數(shù)據(jù)的壓縮。

20、解壓縮時，只要我們向壓縮時那樣維護(hù)好滑動的窗口，隨著三元組的不斷輸入，我們在窗口中找到相應(yīng)的匹配串，綴上后繼字符c輸出（如果off和len都為0則只輸出后繼字符c)即可還原出原始數(shù)據(jù)。29LZ77算法三元組的編碼方法（編碼方式取決于數(shù)據(jù)的分布概率）：對于第一個分量窗口內(nèi)的偏移，通常的經(jīng)驗是，偏移接近窗口尾部的情況要多于接近窗口頭部的情況。但對于普通的窗口大小來說，這一差別可以忽略不計，我們用固定的位數(shù)來表示它：即編碼off需要的位數(shù)為upper_bound(log2(MAX_WND_SIZE)對于第二個分量字符串長度，它的值在大多數(shù)時候不會太大，大字符串的匹配的發(fā)生概率很小。顯然可以使用一種變

21、長的編碼方式來表示該長度值。我們已經(jīng)知道，要輸出變長的編碼，該編碼必須滿足前綴編碼的條件。其實 Huffman 編碼也可以在此處使用，但卻不是最好的選擇。適用于此處的好的編碼方案很多，我們將在稍后介紹其中兩種應(yīng)用非常廣泛的編碼：Golomb編碼和編碼。對三元組的最后一個分量字符 c，因為其分布并無規(guī)律可循，我們只能老老實實地用 8 個二進(jìn)制位對其編碼。30假設(shè)對正整數(shù)x進(jìn)行Golomb編碼，選擇參數(shù)m，令b = 2mq = INT(x - 1)/b)r = x - qb 1則x可以被編碼為兩部分，第一部分是由q個1加1個0組成，第二部分為m位二進(jìn)制數(shù)，其值為 r。Golomb編碼31假設(shè)對x編

22、碼，令q = int( log2x )則編碼的前一部分是q個1加一個0，后一部分是q位長的二進(jìn)制數(shù)，其值等于(x-2q )值 x編碼10210 0310 14110 005110 016110 107110 1181110 00091110 001編碼32LZ77算法的其他問題其他的編碼方式：輸出匹配串時不輸出后續(xù)字符輸出0表示下面是一個匹配串，輸出1表示下面是一個單個字符對匹配串長度加以限制如何查找匹配串：限制匹配串的長度，在內(nèi)存中組織二叉有序樹將窗口中每個長度為3的字符串建立字典索引使用Hash表建立索引使用字符樹建立索引窗口滑動時內(nèi)存中的索引重建問題：建立環(huán)狀偏移以環(huán)狀偏移為基礎(chǔ)建立窗口

23、索引33內(nèi)存詞典：第二步：壓縮串“AD .”在內(nèi)存詞典中仍無法找到匹配串，則輸出二元組(0，“A”)并將字串“A”置入內(nèi)存詞典第一步：壓縮串“DAD.”在內(nèi)存詞典中無法找到匹配串，則輸出二元組(0，“D”)二元組中第一個元素表示詞典的索引，第二個元素表示后續(xù)字符。并將字串“D”置入內(nèi)存詞典內(nèi)存詞典：LZW算法LZW算法是LZ78的改進(jìn)，其基本思路是在內(nèi)存中維護(hù)一個動態(tài)的字典，輸出的代碼是該字典的索引例：待壓縮的信息為 DAD DADA DADDY DADO. 索引0詞條null索引01詞條null“D”34第三步：壓縮串“D D.”在內(nèi)存詞典中可以找到最大匹配串“D”，輸出二元組 (1，“ ”

24、)以此對字串“D ”進(jìn)行了編碼，然后將“D ”置入內(nèi)存詞典內(nèi)存詞典：內(nèi)存詞典：第四步：壓縮串“DAD.”在內(nèi)存詞典中可以找到最大匹配串“D”，則輸出二元組(1，“A”)以此對字串“DA”進(jìn)行了編碼，然后將“DA”置入內(nèi)存詞典LZW算法例：待壓縮的信息為 DAD DADA DADDY DADO. 索引012詞條null“D”“A”索引0123詞條null“D”“A”“D ”35LZW算法例：待壓縮的信息為 DAD DADA DADDY DADO. 第九步后，內(nèi)存詞典的情況如下：索引01234詞條null“D”“A”“D ”“DA”索引56789詞條“DA ”“DAD”“DY”“ ”“DADO”每

25、一步的輸出如下（每一步輸出均為二元組）：36JPEG圖像壓縮算法JPEG 是有損壓縮算法JPEG 核心是“離散余弦變換(Discrete Cosine Transform,DCT)”JPEG 壓縮算法的基本步驟為：1、離散余弦變換DCT Transformation2、系數(shù)量子化Coefficient Quantization 3、無損壓縮Lossless Compression37一維波38二維波39離散余弦變換 DCTDCT操作X、Y、Z坐標(biāo)軸上的三維信號。X、Y坐標(biāo)軸是平面圖像的兩個維度，Z軸表示圖象的象素值。對N * N的象素矩陣進(jìn)行DCT變換的公式如下：離散余弦變換(Discrete

26、 Cosine Transform,DCT)公式：反向離散余弦變換(Inverse Discrete Cosine Transform,IDCT)公式：其中：但是：按照上述基本公式寫出的程序?qū)崿F(xiàn)存在一個嚴(yán)重的問題時間復(fù)雜度太高40使用矩陣運(yùn)算的DCT替代公式實現(xiàn)上面的替代公式的程序代碼的時間復(fù)雜度就大大降低了。進(jìn)一步的改進(jìn)還包括將余弦函數(shù)由浮點運(yùn)算改為整數(shù)運(yùn)算、改進(jìn)傅立葉變換技術(shù)等。41量子化 QuantizationDCT變換的輸入是8位的象素值（0255，JPEG實現(xiàn)時將其減去128，范圍變成-128127），但輸出范圍是從1024到1023 ，占11位。量子化即通過整除運(yùn)算減少輸出值的存儲位數(shù)。使用量子化矩陣（Quantization Matrix）來實現(xiàn)量子化。量子化公式為：量化后的值( i, j ) = ROUND( DCT(i, j) / 量子(i, j) )逆量子化公式為：DCT(i, j) = 量化后的值( i, j ) * 量子(i, j) 量子化是JPEG算法中損失圖像精度的根源，也是產(chǎn)生壓縮效果的源泉42量子表Quantum Table471013161922257101316192225281013161922252831131619222528313416192225283134371922252831