第四章 數(shù)據(jù)壓縮技術(shù)(補(bǔ)充)

1、2022-5-4信息管理系12022-5-4信息管理系2什么是數(shù)據(jù)壓縮 數(shù)據(jù)壓縮就是在一定的精度損失條件下，以最少的數(shù)碼表示信源所發(fā)出的信號信源編碼信道編碼信道信道譯碼信源譯碼信源信宿2022-5-4信息管理系3數(shù)據(jù)壓縮能實(shí)現(xiàn)的條件(1)信息集包含冗余信息。計(jì)算機(jī)內(nèi)的信息均以二進(jìn)制形式表示，以一個(gè)字節(jié)為單位，基本信息集是00-ffh。當(dāng)某信息集的數(shù)據(jù)量大于256時(shí)，理論上可以判定其中必有冗余，而去掉冗余不會減少信息量，仍可原樣恢復(fù)數(shù)據(jù)。如在一份計(jì)算機(jī)文件中，某些符號耍比其他符號額外高得多地重復(fù)出現(xiàn)，或一些字符總在數(shù)據(jù)塊中某一可預(yù)見的位置上出現(xiàn)，這些冗余部分便可在數(shù)據(jù)編碼中除去或減少。2022-

2、5-4信息管理系4(2)數(shù)據(jù)中間尤其是相鄰的數(shù)據(jù)之間常存在著相關(guān)性，如圖片中常常有色彩均勻的背影，電視信號的相鄰兩幀之間可能只有少量的變化景物是不同的，聲音信號有時(shí)具有一定的規(guī)律性和周期性等。因此，有可能利用某些變換來盡可能地去掉這些相關(guān)性。2022-5-4信息管理系5 (3)人們在欣賞音像節(jié)目時(shí)，由于人的視覺和聽覺的生理特性，耳、日對信旱的時(shí)間變化和幅度變化的感受能力都有一定的極限。如人眼對影視節(jié)目有視覺暫留效應(yīng)，對低于某一極限的幅度變化無法感知，故可將信號中這部分感覺不出的分量壓縮掉，經(jīng)過壓縮編碼的視聽信號在復(fù)現(xiàn)時(shí)仍具有較為滿意的主觀質(zhì)量。2022-5-4信息管理系6多媒體信源引起了“數(shù)據(jù)

3、爆炸”如果不進(jìn)行數(shù)據(jù)壓縮 傳輸和存儲都難以實(shí)用化。多媒體數(shù)據(jù)數(shù)據(jù)壓縮的必要性2022-5-4信息管理系7數(shù)數(shù)字字音音頻頻格格式式頻頻帶帶(Hz)帶帶寬寬(KHz)取取樣樣率率(KHz)量量化化位位數(shù)數(shù)存存儲儲容容量量(MB)電電話話20034003.2880.48會會議議電電視視伴伴音音507000716141.68C CD D- -D DA A20200002044.1165.2922D DA AT T20200002048165.762數(shù)數(shù)字字音音頻頻廣廣播播20200002048165.766分鐘數(shù)字音頻信號需要的存儲空間1 12022-5-4信息管理系8分鐘數(shù)字視頻信號需要的存儲空間1

4、 12022-5-4信息管理系9 時(shí)間域壓縮時(shí)間域壓縮迅速傳輸媒體信源迅速傳輸媒體信源 頻率域壓縮頻率域壓縮并行開通更多業(yè)務(wù)并行開通更多業(yè)務(wù) 空間域壓縮空間域壓縮降低存儲費(fèi)用降低存儲費(fèi)用 能量域壓縮能量域壓縮降低發(fā)射功率降低發(fā)射功率數(shù)據(jù)壓縮的好處2022-5-4信息管理系10l壓縮比要大壓縮比要大l恢復(fù)后的失真小恢復(fù)后的失真小l壓縮算法要簡單、速度快壓縮算法要簡單、速度快l壓縮能否用硬件實(shí)現(xiàn)壓縮能否用硬件實(shí)現(xiàn)數(shù)據(jù)壓縮技術(shù)實(shí)現(xiàn)的衡量標(biāo)準(zhǔn)2022-5-4信息管理系112022-5-4信息管理系12 (1)無損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同

5、；無損壓縮用于要求重構(gòu)的信號與原始信號完全一致的場合。 (2)有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號不一定非要和原始信號完全相同的場合。數(shù)據(jù)壓縮技術(shù)的分類2022-5-4信息管理系13 (3)混合壓縮?；旌蠅嚎s是被廣泛采用的方法，它吸收了各種無損壓縮和有損壓縮方法的長處，以求在壓縮比、壓縮效率及保真度之間取得最佳平衡，如靜止圖像壓縮標(biāo)準(zhǔn)JPEG和活動(dòng)圖像壓縮標(biāo)難MPEG就是采用了混合編碼的壓縮方法。2022-5-4信息管理系14壓縮技術(shù)的應(yīng)用電報(bào)、傳真(CCITT)通訊(Modem/網(wǎng)絡(luò)協(xié)議)存儲(

6、壓縮池)文件系統(tǒng)(壓縮扇區(qū))圖像(GIF/TIFF/JPEG)音頻(MP3)視頻(MPEG/RM)數(shù)據(jù)庫(B+樹)歸檔(TAR/ZIP)密碼學(xué)(消除數(shù)據(jù)的原始特征)全文索引(倒排索引表)編譯(JAVA)程序設(shè)計(jì)(算法/空間和時(shí)間效率)人工智能(專家系統(tǒng)/知識樹)2022-5-4信息管理系15壓縮技術(shù)起源信息壓縮技術(shù)的起源比計(jì)算機(jī)的發(fā)明早幾千年2022-5-4信息管理系16一千多年前的中國學(xué)者用“班馬”這樣的縮略語來指代班固和司馬遷，這種崇尚簡約的風(fēng)俗一直延續(xù)到了今天的 Internet 時(shí)代：BBS 上用“ 7456 ”代表“氣死我了”，用“ B4 ”代表“ Before ”的時(shí)候，這就是一種

7、最簡單的數(shù)據(jù)壓縮。2022-5-4信息管理系17在計(jì)算機(jī)出現(xiàn)之前，著名的 Morse 電碼就已經(jīng)成功地實(shí)踐了這一準(zhǔn)則。在 Morse 碼表中，每個(gè)字母都對應(yīng)于一個(gè)唯一的點(diǎn)劃組合，出現(xiàn)概率最高的字母 e 被編碼為一個(gè)點(diǎn)“ . ”，而出現(xiàn)概率較低的字母 z 則被編碼為“ -. ”。顯然，這可以有效縮短最終的電碼長度。 2022-5-4信息管理系18信息論信息存在冗余信息存在冗余通過采用一定通過采用一定的模型和編碼方法，的模型和編碼方法，可以降低這種冗余度可以降低這種冗余度貝爾實(shí)驗(yàn)室的 Claude Shannon 和 MIT 的 R.M.Fano幾乎同時(shí)提出了最早的對符號進(jìn)行有效編碼從而實(shí)現(xiàn)數(shù)據(jù)壓

8、縮的 Shannon-Fano 編碼方法。2022-5-4信息管理系19D.A.Huffman1952 年 發(fā)表論文：“最小冗余度代碼的構(gòu)造方法”A Method for the Construction of Minimum Redundancy CodesUNIX 系統(tǒng)上一個(gè)不太為現(xiàn)代人熟知的壓縮程序 COMPACT 就是 Huffman 0 階自適應(yīng)編碼的具體實(shí)現(xiàn) 80 年代初，Huffman 編碼又在 CP/M 和 DOS 系統(tǒng)中實(shí)現(xiàn)，其代表程序叫 SQHuffman時(shí)代：時(shí)代：60 年代、年代、70 年代乃至年代乃至 80 年代的早期年代的早期2022-5-4信息管理系20接近極限熵

9、80年代早期，數(shù)學(xué)家們設(shè)計(jì)出算術(shù)編碼方法(Arithmetic Coding)可以證明，算術(shù)編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號精確表達(dá)原始信息內(nèi)容 q 但是，在同樣的計(jì)算機(jī)系統(tǒng)上，算術(shù)編碼雖然可以得到最好的壓縮效果，卻要消耗也許幾十倍的計(jì)算時(shí)間 算術(shù)編碼是部分匹配預(yù)測(Predication by Partial matching, PPM)技術(shù)的變體2022-5-4信息管理系21以色列人1978 年 發(fā)表論文：“通過可變比率編碼的獨(dú)立序列的壓縮”Compression of Individual Sequences via Variable-Rate Coding字

10、典編碼時(shí)代：字典編碼時(shí)代：LZ77和和LZ78壓縮算法壓縮算法1977 年 發(fā)表論文：“順序數(shù)據(jù)壓縮的一個(gè)通用算法”A Universal Algorithm for Sequential Data Compression2022-5-4信息管理系22LZW算法Welch 實(shí)現(xiàn)了 LZ78 算法的一個(gè)變種 UNIX：使用 LZW 算法的 Compress 程序MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。 1984 年 發(fā)表論文：“高性能數(shù)據(jù)壓縮技術(shù)”A Technique for High-Performance Data Compression 2022-5-4信息管

11、理系23通用數(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 一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域2022-5-4信息管理系24多媒體數(shù)據(jù)壓縮q國際電報(bào)電話咨詢委員會( CCITT ) ：針對二值圖像的一系列壓縮標(biāo)準(zhǔn)，如 CCITT Group3、CCITT Group4 等 (此外還包括CCITT與ISO共同制訂的JBIG標(biāo)準(zhǔn)) 。q70 年代末 80 年代初：數(shù)學(xué)家們提出了損失壓縮精度

12、以換取壓縮損失壓縮精度以換取壓縮率的嶄新思路率的嶄新思路。國際標(biāo)準(zhǔn)化組織( ISO )和 CCITT 聯(lián)合組成了兩個(gè)委員會：靜態(tài)圖像聯(lián)合專家小組( JPEG )和動(dòng)態(tài)圖像聯(lián)合專家小組( MPEG )。誕生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列標(biāo)準(zhǔn)。qPostScript矢量圖形格式：起源于 1976 年的 Evans & Sutherland 計(jì)算機(jī)公司，當(dāng)時(shí)的名字是 Design System。1978 年，John Warnock 和 Martin Newel 將其演變?yōu)?JAM 語言。1982 年，John Warnock 和 Chuck Gesch

13、ke 創(chuàng)建了著名的 Adobe System 公司，第三次設(shè)計(jì)和實(shí)現(xiàn)了這個(gè)語言，并稱其為 PostScript。2022-5-4信息管理系25技術(shù)準(zhǔn)備：什么是熵熵熵來源于40年代由Claude Shannon創(chuàng)立的信息論中的一條定理，這一定理借用了熱力學(xué)中的名詞“熵”( Entropy )來表示一條信息中真正需要編碼的信息量：考慮用 0 和 1 組成的二進(jìn)制數(shù)碼為含有 n 個(gè)符號的某條信息編碼，假設(shè)符號 Fn 在整條信息中重復(fù)出現(xiàn)的概率為 Pn，則該符號的熵也即表示該符號所需的二進(jìn)制位數(shù)為：En = - log2( Pn )整條信息的熵也即表示整條信息所需的二進(jìn)制位數(shù)為：E = knEn例：對

14、信息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位2022-5-4信息管理系26技術(shù)準(zhǔn)備：模型使用模型：得到字符或單詞在信息中出現(xiàn)的概率靜態(tài)/半靜態(tài)模型自適應(yīng)模型Claude Shannon的“聚會游戲”(party game)：他每次向聽眾公布一條被他隱藏起一個(gè)字符的消息，讓聽眾來猜下一個(gè)字符，一次猜一個(gè)，直到猜對為止。然后，Shannon 使

15、用猜測次數(shù)來確定整個(gè)信息的熵。（人的語言經(jīng)驗(yàn)）靜態(tài)字典模型自適應(yīng)字典模型統(tǒng)計(jì)模型字典模型2022-5-4信息管理系27技術(shù)準(zhǔn)備：編碼通過模型，我們可以確定對某一個(gè)符號該用多少位二進(jìn)制數(shù)進(jìn)行編碼?，F(xiàn)在的問題是，如何設(shè)計(jì)一種編碼方案，使其盡量精確地用模型計(jì)算出來的位數(shù)表示某個(gè)符號。前綴編碼規(guī)則：任何一個(gè)符號的編碼都不是另一個(gè)符號編碼的前綴。最簡單的前綴編碼字符字符編碼編碼A0B10C110D1110E111101110010101110110111100010 D A B B D C E A A B 反過來說就是，任何一個(gè)字符的編碼，都不是由另一個(gè)字符的編碼加上若干位 0 或 1 組成 2022-

16、5-4信息管理系28二叉樹可以實(shí)現(xiàn)前綴編碼規(guī)則root01011abcde0102022-5-4信息管理系29技術(shù)準(zhǔn)備：壓縮=模型+編碼輸入模型編碼輸出符號概率代碼2022-5-4信息管理系30Shannon-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

17、 00b 01c 10d 110e 111root0010111abcde2022-5-4信息管理系31Shannon-Fano編碼步驟:1) 將給定符號按照其頻率從大到小排序。對上面的例子，應(yīng)該得到：a - 16 b - 7 c - 6 d - 6 e - 52022-5-4信息管理系32Shannon-Fano編碼步驟2) 將序列分成上下兩部分，使得上部頻率總和盡可能接近下部頻率總和.a - 16 b - 7 - c 6 d - 6 e - 52022-5-4信息管理系33Shannon-Fano編碼步驟3) 我們把第二步中劃分出的上部作為二叉樹的左子樹，記 0，下部作為二叉樹的右子樹，記

18、 1。2022-5-4信息管理系34Shannon-Fano編碼步驟4) 分別對左右子樹重復(fù) 2 3 兩步，直到所有的符號都成為二叉樹的樹葉為止。現(xiàn)在我們有如下的二叉樹.root01011abcde0012022-5-4信息管理系35 1952 年時(shí)，年輕的 Huffman 是麻省理工學(xué)院的一名學(xué)生，他為了向老師證明自己可以不參加某門功課的期末考試，才設(shè)計(jì)了這個(gè)看似簡單，但卻影響深遠(yuǎn)的Huffman編碼方法。1、Huffman故事Huffman編碼2022-5-4信息管理系362、Huffman編碼過程2022-5-4信息管理系372022-5-4信息管理系382022-5-4信息管理系392

19、022-5-4信息管理系402022-5-4信息管理系412022-5-4信息管理系4271161050030111010Huffman碼2022-5-4信息管理系43Huffman編碼cabcedeacacdeddaaabaababaaabbacdebaceada 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 111root00111abcde0012022-5-4信息管理

20、系44整數(shù)位編碼與信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 該信息的熵經(jīng)計(jì)算可知為86.601位符號符號理想位數(shù)理想位數(shù)（熵）（熵）S-F編碼需編碼需要位數(shù)要位數(shù)Huffman編編碼需要位數(shù)碼需要位數(shù)a1.32221b2.51523c2.73723d2.73733e3.00033總計(jì)總計(jì)86.60191882022-5-4信息管理系45另：Huffman編碼還有一個(gè)變種范式Huffman編碼，可以有效減少編碼字典的存儲空間。Huffman編碼的模型選擇奇怪的段落奇怪的段落If Youth，throughout all history，had had

21、 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 anything.“- Gadsby by E.V.Wright, 1939.2022-5-4信息管理系46算術(shù)編碼假設(shè)某個(gè)字符的出現(xiàn)概率為 80%，該字符事實(shí)上只需要 -log2(0.8) = 0.322 個(gè)二進(jìn)制位進(jìn)行

22、編碼難道真的能只輸出 0.322 個(gè) 0 或 0.322 個(gè) 1 嗎？算術(shù)編碼的輸出是：一個(gè)小數(shù)算術(shù)編碼的輸出是：一個(gè)小數(shù)算術(shù)編碼對整條信息（無論信息有多么長），其輸出僅僅是一個(gè)數(shù)，而且是一個(gè)介于0和1之間的二進(jìn)制小數(shù)。例如算術(shù)編碼對某條信息的輸出為1010001111，那么它表示小數(shù)0.1010001111，也即十進(jìn)制數(shù)0.642022-5-4信息管理系47算術(shù)編碼例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb第一步第一步：在沒有開始壓縮進(jìn)程之前，假設(shè)我們對 a b c 三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應(yīng)模型），即認(rèn)為三者的出現(xiàn)概

23、率相等，也就是都為1/3，我們將0-1區(qū)間按照概率的比例分配給三個(gè)字符，即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/32022-5-4信息管理系48算術(shù)編碼第二步第二步：現(xiàn)在我們拿到第一個(gè)字符b，讓我們把目光投向b對應(yīng)的區(qū)間0.3333-0.6667。這時(shí)由于多了字符b，三個(gè)字符的概率分布變成：Pa=1/4，Pb=2/4，Pc=1/4。好，讓我們按照新的概率分布比例劃分0.3333-0.6667這一區(qū)間，劃分的結(jié)果可以用圖形表示為：

24、0.66670.58340.41670.3333Pc = 1/4Pb = 2/4Pa = 1/4例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb2022-5-4信息管理系49算術(shù)編碼第三步第三步：接著我們拿到字符c，我們現(xiàn)在要關(guān)注上一步中得到的c的區(qū)間 0.5834-0.6667。新添了c以后，三個(gè)字符的概率分布變成Pa=1/5，Pb=2/5，Pc=2/5。我們用這個(gè)概率分布劃分區(qū)間0.5834-0.6667：0.66670.63340.60010.5834Pc = 2/5Pb = 2/5Pa = 1/5例：考慮某條信息中可能出現(xiàn)的字符僅有 a b

25、c 三種，我們要壓縮保存的原始信息為 bccb2022-5-4信息管理系50算術(shù)編碼第四步第四步：現(xiàn)在輸入下一個(gè)字符c，三個(gè)字符的概率分布為：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 三種，我們要壓縮保存的原始信息為 bccb2022-5-4信息管理系51算術(shù)編碼第五步第五步：輸入最后一個(gè)字符b，因?yàn)槭亲詈笠粋€(gè)字符，不用再做進(jìn)一步的劃分了，上一步中得到的b的區(qū)間為0.6390-0.6501，好，讓我們在這

26、個(gè)區(qū)間內(nèi)隨便選擇一個(gè)容易變成二進(jìn)制的數(shù)，例如0.64，將它變成二進(jìn)制0.1010001111，去掉前面沒有太多意義的0和小數(shù)點(diǎn)，我們可以輸出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)22022-5-4信息管理系52自適應(yīng)模型的階h(t)(t)gh(t)igh(t)例文：例文：the weight of .0階階

27、1階階2階階3階階問題：半靜態(tài)模型和自適應(yīng)模型轉(zhuǎn)義碼的使用1. 存儲空間問題2022-5-4信息管理系53階概念例: 對一篇英文文本進(jìn)行編碼，已經(jīng)編碼了 10000 個(gè)英文字符，剛剛編碼的字符是 t，下一個(gè)要編碼的字符是 h。在前面的編碼過程中已經(jīng)統(tǒng)計(jì)出前 10000 個(gè)字符中出現(xiàn)了 113 次字母 t，其中有 47 個(gè) t 后面跟著字母 h。我們得出字符 h 在字符 t 后的出現(xiàn)頻率是 47/113，我們使用這一頻率對字符 h 進(jìn)行編碼，需要 -log2(47/113) = 1.266 位。2022-5-4信息管理系54階概念 對比 0 階自適應(yīng)模型，如果前 10000 個(gè)字符中 h 的出現(xiàn)

28、次數(shù)為 82 次，則字符 h 的概率是 82/10000，我們用此概率對 h 進(jìn)行編碼，需要 -log2(82/10000) = 6.930 位?？紤]上下文因素的優(yōu)勢顯而易見。2022-5-4信息管理系55階概念例: 要編碼字符 h 的前兩個(gè)字符是 gt，而在已經(jīng)編碼的文本中 gt 后面出現(xiàn) h 的概率是 80%，那么我們只需要 0.322 位就可以編碼輸出字符 h。此時(shí)，我們使用的模型叫做 2 階上下文自適應(yīng)模型. 同樣對于3階一樣.2022-5-4信息管理系56字典壓縮日常生活: 我們常常跟人說“奧運(yùn)會”、“IBM”、“TCP”之類的詞匯，說者和聽者都明白它們指的是“奧林匹克運(yùn)動(dòng)會”、“國

29、際商業(yè)機(jī)器公司”和“傳輸控制協(xié)議”，這實(shí)際就是信息的壓縮。我們之所以可以順利使用這種壓縮方式而不產(chǎn)生語義上的誤解，是因?yàn)樵谡f者和聽者的心中都有一個(gè)事先定義好的縮略語字典，我們在對信息進(jìn)行壓縮（說）和解壓縮（聽）的過程中都對字典進(jìn)行了查詢操作。字典壓縮模型正是基于這一思路設(shè)計(jì)實(shí)現(xiàn)的.2022-5-4信息管理系57字典壓縮最簡單的情況: 我們擁有一本預(yù)先定義好的字典。例如，我們要對一篇中文文章進(jìn)行壓縮，我們手中已經(jīng)有一本現(xiàn)代漢語詞典。那么，我們掃描要壓縮的文章，并對其中的句子進(jìn)行分詞操作，對每一個(gè)獨(dú)立的詞語，我們在現(xiàn)代漢語詞典查找它的出現(xiàn)位置，如果找到，我們就輸出頁碼和該詞在該頁中的序號，如果沒有

30、找到，我們就輸出一個(gè)新詞。這就是靜態(tài)字典模型的基本算法.2022-5-4信息管理系58字典壓縮靜態(tài)缺點(diǎn):(1)靜態(tài)模型的適應(yīng)性不強(qiáng)，我們必須為每類不同的信息建立不同的字典；(2)對靜態(tài)模型，我們必須維護(hù)信息量并不算小的字典，這一額外的信息量影響了最終的壓縮效果。自適應(yīng)的方式: 將已經(jīng)編碼過的信息作為字典，如果要編碼的字符串曾經(jīng)出現(xiàn)過，就輸出該字符串的出現(xiàn)位置及長度，否則輸出新的字符串。2022-5-4信息管理系59字典壓縮例:2022-5-4信息管理系60LZ77算法 LZ77 算法在某種意義上又可以稱為“滑動(dòng)窗口壓縮”，該算法將一個(gè)虛擬的，可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為詞典，要壓縮的字符串如

31、果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長度。使用固定大小窗口進(jìn)行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因?yàn)槠ヅ渌惴ǖ臅r(shí)間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進(jìn)程滑動(dòng)詞典窗口，使其中總包含最近編碼過的信息，是因?yàn)閷Υ蠖鄶?shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。2022-5-4信息管理系61LZ77算法LZ77算法的基本流程：“滑動(dòng)的窗口”1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出最長的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步驟 3。2、輸出三元符號組(off,len,c)。其中off為窗口中匹配字符串相對窗口邊界

32、的偏移，len為可匹配的長度，c為下一個(gè)字符。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟 1。3、輸出三元符號組(0,0,c)。其中c為下一個(gè)字符。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟 1。2022-5-4信息管理系62LZ77算法應(yīng)用實(shí)例：窗口大小為10個(gè)字符，剛編碼過的10個(gè)字符為“abcdbbccaa”，即將編碼的10個(gè)字符為 “abaeaaabaee”。我們首先發(fā)現(xiàn)，可以和待編碼字符匹配的最長串為ab(off=0,len=2), ab的下一個(gè)字符為a，我們輸出三元組：(0,2,a)現(xiàn)在窗口向后滑動(dòng)3個(gè)字符，窗口中的內(nèi)容為：dbbccaaaba下一個(gè)字符e在窗口中沒有匹配，我們

33、輸出三元組：(0,0,e)窗口向后滑動(dòng)1個(gè)字符，其中內(nèi)容變?yōu)椋篵bccaaabae我們馬上發(fā)現(xiàn)，要編碼的aaabae在窗口中存在(off=4,len=6)，其后的字符為e，我們可以輸出：(4,6,e)這樣，我們將可以匹配的字符串都變成了指向窗口內(nèi)的指針，并由此完成了對上述數(shù)據(jù)的壓縮。解壓縮時(shí)，只要我們向壓縮時(shí)那樣維護(hù)好滑動(dòng)的窗口，隨著三元組的不斷輸入，我們在窗口中找到相應(yīng)的匹配串，綴上后繼字符c輸出（如果off和len都為0則只輸出后繼字符c)即可還原出原始數(shù)據(jù)。2022-5-4信息管理系63LZ77算法三元組的編碼方法（編碼方式取決于數(shù)據(jù)的分布概率）：對于第一個(gè)分量窗口內(nèi)的偏移，通常的經(jīng)驗(yàn)是

34、，偏移接近窗口尾部的情況要多于接近窗口頭部的情況。但對于普通的窗口大小來說，這一差別可以忽略不計(jì)，我們用固定的位數(shù)來表示它：即編碼off需要的位數(shù)為upper_bound(log2(MAX_WND_SIZE)對于第二個(gè)分量字符串長度，它的值在大多數(shù)時(shí)候不會太大，大字符串的匹配的發(fā)生概率很小。顯然可以使用一種變長的編碼方式來表示該長度值。我們已經(jīng)知道，要輸出變長的編碼，該編碼必須滿足前綴編碼的條件。其實(shí) Huffman 編碼也可以在此處使用，但卻不是最好的選擇。適用于此處的好的編碼方案很多，我們將在稍后介紹其中兩種應(yīng)用非常廣泛的編碼：Golomb編碼和編碼。對三元組的最后一個(gè)分量字符 c，因?yàn)槠?/p>

35、分布并無規(guī)律可循，我們只能老老實(shí)實(shí)地用 8 個(gè)二進(jìn)制位對其編碼。2022-5-4信息管理系64假設(shè)對正整數(shù)x進(jìn)行Golomb編碼，選擇參數(shù)m，令b = 2mq = INT(x - 1)/b)r = x - qb 1則x可以被編碼為兩部分，第一部分是由q個(gè)1加1個(gè)0組成，第二部分為m位二進(jìn)制數(shù)，其值為 r。值值 xm = 0m = 1m = 2m = 3100 00 000 0002100 10 010 001311010 00 100 0104111010 10 110 011511110110 010 000 1006111110110 110 010 101711111101110 010

36、 100 1108111111101110 110 110 111911111111011110 0110 0010 0002022-5-4信息管理系65假設(shè)對x編碼，令q = int( log2x )則編碼的前一部分是q個(gè)1加一個(gè)0，后一部分是q位長的二進(jìn)制數(shù)，其值等于(x-2q )值值 x編碼編碼10210 0310 14110 005110 016110 107110 1181110 00091110 0012022-5-4信息管理系66LZ77算法的其他問題其他的編碼方式：輸出匹配串時(shí)不輸出后續(xù)字符輸出0表示下面是一個(gè)匹配串，輸出1表示下面是一個(gè)單個(gè)字符對匹配串長度加以限制如何查找匹配

37、串：限制匹配串的長度，在內(nèi)存中組織二叉有序樹將窗口中每個(gè)長度為3的字符串建立字典索引使用Hash表建立索引使用字符樹建立索引窗口滑動(dòng)時(shí)內(nèi)存中的索引重建問題：建立環(huán)狀偏移1. 以環(huán)狀偏移為基礎(chǔ)建立窗口索引2022-5-4信息管理系67LZSS算法 LZ77通過輸出真實(shí)字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個(gè)解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個(gè)方面，一是空指針，二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。 LZSS算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針（匹配串長度大于等于MIN_LENGTH），否則就輸出真實(shí)字符。另外要輸出額外的標(biāo)志位區(qū)

38、分是指針還是字符。2022-5-4信息管理系68LZSS編碼的基本流程1、從當(dāng)前壓縮位置開始，考察未編碼的字符，并試圖在滑動(dòng)窗口中找出最長的匹配字符串，如果匹配串長度len大于等于最小匹配串長度（len = MIN_LENGTH），則進(jìn)行步驟 2，否則進(jìn)行步驟 3。2、輸出指針二元組 ( off, len)。其中 off 為窗口中匹配字符串相對窗口邊界的偏移，len 為匹配串的長度，然后將窗口向后滑動(dòng) len 個(gè)字符，繼續(xù)步驟 1。3、輸出當(dāng)前字符c，然后將窗口向后滑動(dòng) 1 個(gè)字符，繼續(xù)步驟 1。2022-5-4信息管理系69LZSS編碼舉例位置位置1234567891011字符字符AABBC

39、BBAABC步驟步驟位置位置匹配串匹配串輸出輸出11A22AA33B44BB55C66BB（3，2）78AAB（1，3）811CC輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：編碼過程編碼過程MIN_LEN =22022-5-4信息管理系70LZSS算法 在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡單。這也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差別僅僅是指針的長短和窗口的大小等有所不同。 LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip

40、則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。2022-5-4信息管理系71第二類詞典編碼 第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典 (dictionary of the phrases)”，這種短語可以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語”時(shí)，編碼器就輸出這個(gè)詞典中的短語的“索引號”，而不是短語本身。2022-5-4信息管理系72LZ78算法 LZ78的編碼思想是不斷地從字符流中提取新的字符串(String)，通俗地理解為新“詞條”，然后用“代號”也就是碼字(Code word)表示這個(gè)“詞條”。這樣一來，對字符流的編碼就變成了用碼字

41、(Code word)去替換字符流(Char stream)，生成碼字流(Code stream)，從而達(dá)到壓縮數(shù)據(jù)的目的。 LZ78編碼器的輸出是碼字-字符(W,C)對，每次輸出一對到碼字流中，與碼字W相對應(yīng)的字符串(String)用字符C進(jìn)行擴(kuò)展生成新的字符串(String)，然后添加到詞典中。2022-5-4信息管理系73算法中用到的幾個(gè)術(shù)語: 字符流(Charstream)：待編碼的數(shù)據(jù)序列。 字符(Character)：字符流中的基本數(shù)據(jù)單元。 前綴(Prefix)：在一個(gè)字符之前的字符序列。 綴-符串(String)：前綴字符。 碼字(Code word)：碼字流中的基本數(shù)據(jù)單元，

42、代表詞典中的一串字符。 2022-5-4信息管理系74碼流(Codestream)：碼字和字符組成的序列，是編碼器的輸出。 詞典(Dictionary)：綴-符串表。按照詞典中的索引號對每條綴-符串(String)指定一個(gè)碼字(Code word)。 當(dāng)前前綴(Current prefix)：在編碼算法中使用，指當(dāng)前正在處理的前綴，用符號P表示。 當(dāng)前字符(Current character)：在編碼算法中使用，指當(dāng)前前綴之后的字符，用符號C表示。 當(dāng)前碼字(Current code word)：在譯碼算法中使用，指當(dāng)前處理的碼字，用W表示當(dāng)前碼字，String.W表示當(dāng)前碼字的綴-符串。20

43、22-5-4信息管理系75LZ78編碼算法步驟1：在開始時(shí)，詞典和當(dāng)前前綴P都是空的； 步驟2：當(dāng)前字符C：=字符流中的下一個(gè)字符； 步驟3：判斷P+C是否在詞典中 (1) 如果“是”：用C擴(kuò)展P，讓P：= P+C ； (2) 如果“否”： 輸出與當(dāng)前前綴P相對應(yīng)的碼字和當(dāng)前字符C； 把字符串P+C添加到詞典中； 令P：=空值； (3) 判斷字符流中是否還有字符需要編碼 如果“是”：返回到步驟2； 如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。 2022-5-4信息管理系76LZ78編碼舉例位置位置123456789字符字符ABBCBCABA步驟步驟位置位置詞典詞

44、典輸出輸出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：編碼過程：編碼過程：2022-5-4信息管理系77LZ78譯碼的具體算法如下： 步驟1：在開始時(shí)詞典是空的； 步驟2：當(dāng)前碼字W：=碼字流中的下一個(gè)碼字； 步驟3：當(dāng)前字符C：= 緊隨碼字之后的字符； 步驟4：把當(dāng)前碼字的綴-符串(string.W)輸出到字符流，然后輸出字符C； 步驟5：把string.W+C添加到詞典中； 步驟6：判斷碼字流中是否還有碼字要譯 (1) 如果“是”，就返回到步驟2； (2) 如果“否”，則結(jié)束。2022-5-4信息管理系78LZW

45、算法 J.Ziv和A.Lempel在1978年首次發(fā)表了介紹第二類詞典編碼算法的文章。在他們的研究基礎(chǔ)上，Terry A.Welch在1984年發(fā)表了改進(jìn)這種編碼算法的文章，因此把這種編碼方法稱為LZW(Lempel-Ziv Walch)壓縮編碼。 2022-5-4信息管理系79在編碼原理上，LZW與LZ78相比有如下差別： LZW只輸出代表詞典中的字符串(String)的碼字(code word)。這就意味在開始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符。即在編碼匹配時(shí)，至少可以在詞典中找到長度為1的匹配串。 LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。2022-5-4信息管

46、理系80LZW算法的詞典算法的詞典 LZW編碼器(軟件編碼器或硬件編碼器)就是通過管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換。LZW編碼器的輸入是字符流(Char stream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼字流 (Code stream)，碼字代表單個(gè)字符或多個(gè)字符組成的字符串(String)。2022-5-4信息管理系81LZW編碼算法步驟1： 開始時(shí)的詞典包含所有可能的根(Root)，而當(dāng)前前綴P是空的；步驟2： 當(dāng)前字符(C) :=字符流中的下一個(gè)字符；步驟3： 判斷綴-符串P+C是否在詞典中(1) 如果“是”：P := P+C / (用

47、C擴(kuò)展P)；(2) 如果“否” 把代表當(dāng)前前綴P的碼字輸出到碼字流; 把綴-符串P+C添加到詞典; 令P := C /(現(xiàn)在的P僅包含一個(gè)字符C);步驟4： 判斷碼字流中是否還有碼字要譯(1) 如果“是”，就返回到步驟2；(2) 如果“否” 把代表當(dāng)前前綴P的碼字輸出到碼字流; 結(jié)束。2022-5-4信息管理系82LZW編碼舉例位置位置123456789字符字符ABBABABAC步驟步驟位置位置碼字碼字詞典詞典輸出輸出1A2B3C114AB1225BB2336BA2447ABA4558ABAC763輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：2022-5-4信息管理系83LZW算法 LZW算法得到普遍采用，它的速

48、度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操作。對LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。 LZW算法取得了專利，專利權(quán)的所有者是美國的一個(gè)大型計(jì)算機(jī)公司Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法。2022-5-4信息管理系84LZW特點(diǎn)如下： l)LZW壓縮技術(shù)對于可預(yù)測性不大的數(shù)據(jù)具有較好的處理效果，常用于GIF格式的圖像壓縮，其平均壓縮比在2)1以上，最高壓縮比可達(dá)到3：1。 2)對于數(shù)據(jù)流中連續(xù)重復(fù)出現(xiàn)的字節(jié)和字串，

49、LZW壓縮技術(shù)具有很高的壓縮比。 3)除了用于圖像數(shù)據(jù)處理以外，LZW壓縮技術(shù)還被用于文本程序等數(shù)據(jù)壓縮領(lǐng)域。2022-5-4信息管理系85 4)LZW壓縮技術(shù)有很多變體，例如常見的ARC、RKARC、PKZIP高效壓縮程序。 5)對于任意寬度和像素位長度的圖像，都具有穩(wěn)定的壓縮過程。壓縮和解壓縮速度較快。 6)對機(jī)器硬件條件要求不高，在 Intel 80386的計(jì)算機(jī)上即可進(jìn)行壓縮和解壓縮。2022-5-4信息管理系86比較：LZ77算法LZ77算法的基本流程：“滑動(dòng)的窗口”1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出最長的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步

50、驟 3。2、輸出三元符號組(off,len,c)。其中off為窗口中匹配字符串相對窗口邊界的偏移，len為可匹配的長度，c為下一個(gè)字符。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟 1。3、輸出三元符號組(0,0,c)。其中c為下一個(gè)字符。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟 1。2022-5-4信息管理系87LZ77算法應(yīng)用實(shí)例：窗口大小為10個(gè)字符，剛編碼過的10個(gè)字符為“abcdbbccaa”，即將編碼的10個(gè)字符為 “abaeaaabaee”。我們首先發(fā)現(xiàn)，可以和待編碼字符匹配的最長串為ab(off=0,len=2), ab的下一個(gè)字符為a，我們輸出三元組：(0,2,a)現(xiàn)在窗

51、口向后滑動(dòng)3個(gè)字符，窗口中的內(nèi)容為：dbbccaaaba下一個(gè)字符e在窗口中沒有匹配，我們輸出三元組：(0,0,e)窗口向后滑動(dòng)1個(gè)字符，其中內(nèi)容變?yōu)椋篵bccaaabae我們馬上發(fā)現(xiàn)，要編碼的aaabae在窗口中存在(off=4,len=6)，其后的字符為e，我們可以輸出：(4,6,e)這樣，我們將可以匹配的字符串都變成了指向窗口內(nèi)的指針，并由此完成了對上述數(shù)據(jù)的壓縮。解壓縮時(shí)，只要我們向壓縮時(shí)那樣維護(hù)好滑動(dòng)的窗口，隨著三元組的不斷輸入，我們在窗口中找到相應(yīng)的匹配串，綴上后繼字符c輸出（如果off和len都為0則只輸出后繼字符c)即可還原出原始數(shù)據(jù)。2022-5-4信息管理系88LZ78編碼

52、算法步驟1：在開始時(shí)，詞典和當(dāng)前前綴P都是空的； 步驟2：當(dāng)前字符C：=字符流中的下一個(gè)字符； 步驟3：判斷P+C是否在詞典中 (1) 如果“是”：用C擴(kuò)展P，讓P：= P+C ； (2) 如果“否”： 輸出與當(dāng)前前綴P相對應(yīng)的碼字和當(dāng)前字符C； 把字符串P+C添加到詞典中； 令P：=空值； (3) 判斷字符流中是否還有字符需要編碼 如果“是”：返回到步驟2； 如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。 2022-5-4信息管理系89LZ78編碼舉例位置位置123456789字符字符ABBCBCABA步驟步驟位置位置詞典詞典輸出輸出11A(0, A)22B(0

53、, B)33BC(2, C)45BCA(3, A)58BA(2, A)輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：編碼過程：編碼過程：2022-5-4信息管理系90LZW編碼算法步驟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) 如

54、果“否” 把代表當(dāng)前前綴P的碼字輸出到碼字流; 結(jié)束。2022-5-4信息管理系91LZW編碼舉例位置位置123456789字符字符ABBABABAC步驟步驟位置位置碼字碼字詞典詞典輸出輸出1A2B3C114AB1225BB2336BA2447ABA4558ABAC763輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：2022-5-4信息管理系92行程編碼（RLE） 行程編碼（Run-Length Encoding）：它通過將信源中相同符號序列轉(zhuǎn)換成一個(gè)計(jì)數(shù)字段再加上一個(gè)重復(fù)字符標(biāo)志實(shí)現(xiàn)壓縮。 例如：RTTTTTTTTABBCDG被轉(zhuǎn)換為：R#8TABBCDG，其中“”作為轉(zhuǎn)義字符，表明其后所跟的字符表示長度。 行程編碼多用于黑白二值圖像的壓縮中。例如00000000111111111111000001111111被轉(zhuǎn)化為一系列黑串和白串長度的編碼：801215071。因?yàn)榇L度并非等概率分布，所以一般要配合以統(tǒng)計(jì)編碼（Huffman編碼）。2022-5-4信息管理系93JPEG圖像壓縮算法qJPEG 是有損壓縮算法qJPEG 核心是“離散余弦變換(Dis