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

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

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

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

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

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

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

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

8、效編碼從而實現(xiàn)數(shù)據(jù)壓縮的 Shannon-Fano 編碼方法。2022-4-29信息管理系19D.A.Huffman1952 年 發(fā)表論文：“最小冗余度代碼的構(gòu)造方法”A Method for 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 年代的早期年代的早期2022-4-29

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

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

11、on 2022-4-29信息管理系23通用數(shù)據(jù)壓縮80年代中期以后，對LZ77算法進行改進Haruyasu Yoshizaki(Yoshi) 的 LHarcRobert Jung 的 ARJ 從PKZip到WinZip：通用數(shù)據(jù)壓縮格式標準 ZIPLZ77、LZ78、LZW 一起壟斷當今的通用數(shù)據(jù)壓縮領(lǐng)域一起壟斷當今的通用數(shù)據(jù)壓縮領(lǐng)域2022-4-29信息管理系24多媒體數(shù)據(jù)壓縮q國際電報電話咨詢委員會( CCITT ) ：針對二值圖像的一系列壓縮標準，如 CCITT Group3、CCITT Group4 等 (此外還包括CCITT與ISO共同制訂的JBIG標準) 。q70 年代末 80 年

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

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

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

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

16、上若干位 0 或 1 組成 2022-4-29信息管理系28二叉樹可以實現(xiàn)前綴編碼規(guī)則root01011abcde0102022-4-29信息管理系29技術(shù)準備：壓縮=模型+編碼輸入模型編碼輸出符號概率代碼2022-4-29信息管理系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編碼表示上述

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

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

19、22-4-29信息管理系382022-4-29信息管理系392022-4-29信息管理系402022-4-29信息管理系412022-4-29信息管理系4271161050030111010Huffman碼2022-4-29信息管理系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 11

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

21、 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 anything.“- Gadsby by E.V.Wright, 1939.2022-4-29信息管理系46算術(shù)編碼假設(shè)某個字符的出現(xiàn)概率為 80

22、%，該字符事實上只需要 -log2(0.8) = 0.322 個二進制位進行編碼難道真的能只輸出 0.322 個 0 或 0.322 個 1 嗎？算術(shù)編碼的輸出是：一個小數(shù)算術(shù)編碼的輸出是：一個小數(shù)算術(shù)編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于0和1之間的二進制小數(shù)。例如算術(shù)編碼對某條信息的輸出為1010001111，那么它表示小數(shù)0.1010001111，也即十進制數(shù)0.642022-4-29信息管理系47算術(shù)編碼例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb第一步第一步：在沒有開始壓縮進程之前，假設(shè)我們對 a b c

23、 三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應(yīng)模型），即認為三者的出現(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/32022-4-29信息管理系48算術(shù)編碼第二步第二步：現(xiàn)在我們拿到第一個字符b，讓我們把目光投向b對應(yīng)的區(qū)間0.3333-0.6667。這時由于多了字符b，三個字符的概率分布變成：Pa=1/4，Pb=2/4，Pc=1/4。好，讓我們按照新的

24、概率分布比例劃分0.3333-0.6667這一區(qū)間，劃分的結(jié)果可以用圖形表示為：0.66670.58340.41670.3333Pc = 1/4Pb = 2/4Pa = 1/4例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb2022-4-29信息管理系49算術(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

25、/5Pb = 2/5Pa = 1/5例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb2022-4-29信息管理系50算術(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 三種，我們要壓縮保存的原始信息為 bccb2022-4-29信息管理系51算術(shù)編碼第五步第五步：輸入最后一個字符b，因為是最后一個字符，不用

26、再做進一步的劃分了，上一步中得到的b的區(qū)間為0.6390-0.6501，好，讓我們在這個區(qū)間內(nèi)隨便選擇一個容易變成二進制的數(shù)，例如0.64，將它變成二進制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)22022-4-29信息管理系52自適應(yīng)模型

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

28、2022-4-29信息管理系54階概念 對比 0 階自適應(yīng)模型，如果前 10000 個字符中 h 的出現(xiàn)次數(shù)為 82 次，則字符 h 的概率是 82/10000，我們用此概率對 h 進行編碼，需要 -log2(82/10000) = 6.930 位?？紤]上下文因素的優(yōu)勢顯而易見。2022-4-29信息管理系55階概念例: 要編碼字符 h 的前兩個字符是 gt，而在已經(jīng)編碼的文本中 gt 后面出現(xiàn) h 的概率是 80%，那么我們只需要 0.322 位就可以編碼輸出字符 h。此時，我們使用的模型叫做 2 階上下文自適應(yīng)模型. 同樣對于3階一樣.2022-4-29信息管理系56字典壓縮日常生活: 我

29、們常常跟人說“奧運會”、“IBM”、“TCP”之類的詞匯，說者和聽者都明白它們指的是“奧林匹克運動會”、“國際商業(yè)機器公司”和“傳輸控制協(xié)議”，這實際就是信息的壓縮。我們之所以可以順利使用這種壓縮方式而不產(chǎn)生語義上的誤解，是因為在說者和聽者的心中都有一個事先定義好的縮略語字典，我們在對信息進行壓縮（說）和解壓縮（聽）的過程中都對字典進行了查詢操作。字典壓縮模型正是基于這一思路設(shè)計實現(xiàn)的.2022-4-29信息管理系57字典壓縮最簡單的情況: 我們擁有一本預(yù)先定義好的字典。例如，我們要對一篇中文文章進行壓縮，我們手中已經(jīng)有一本現(xiàn)代漢語詞典。那么，我們掃描要壓縮的文章，并對其中的句子進行分詞操作，

30、對每一個獨立的詞語，我們在現(xiàn)代漢語詞典查找它的出現(xiàn)位置，如果找到，我們就輸出頁碼和該詞在該頁中的序號，如果沒有找到，我們就輸出一個新詞。這就是靜態(tài)字典模型的基本算法.2022-4-29信息管理系58字典壓縮靜態(tài)缺點:(1)靜態(tài)模型的適應(yīng)性不強，我們必須為每類不同的信息建立不同的字典；(2)對靜態(tài)模型，我們必須維護信息量并不算小的字典，這一額外的信息量影響了最終的壓縮效果。自適應(yīng)的方式: 將已經(jīng)編碼過的信息作為字典，如果要編碼的字符串曾經(jīng)出現(xiàn)過，就輸出該字符串的出現(xiàn)位置及長度，否則輸出新的字符串。2022-4-29信息管理系59字典壓縮例:2022-4-29信息管理系60LZ77算法 LZ77

31、算法在某種意義上又可以稱為“滑動窗口壓縮”，該算法將一個虛擬的，可以跟隨壓縮進程滑動的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長度。使用固定大小窗口進行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進程滑動詞典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。2022-4-29信息管理系61LZ77算法LZ77算法的基本流程：“滑動的窗口”1、從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到

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

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

34、繼字符c)即可還原出原始數(shù)據(jù)。2022-4-29信息管理系63LZ77算法三元組的編碼方法（編碼方式取決于數(shù)據(jù)的分布概率）：1. 對于第一個分量窗口內(nèi)的偏移，通常的經(jīng)驗是，偏移接近窗口尾部的情況要多于接近窗口頭部的情況。但對于普通的窗口大小來說，這一差別可以忽略不計，我們用固定的位數(shù)來表示它：即編碼off需要的位數(shù)為upper_bound(log2(MAX_WND_SIZE)2. 對于第二個分量字符串長度，它的值在大多數(shù)時候不會太大，大字符串的匹配的發(fā)生概率很小。顯然可以使用一種變長的編碼方式來表示該長度值。我們已經(jīng)知道，要輸出變長的編碼，該編碼必須滿足前綴編碼的條件。其實 Huffman 編

35、碼也可以在此處使用，但卻不是最好的選擇。適用于此處的好的編碼方案很多，我們將在稍后介紹其中兩種應(yīng)用非常廣泛的編碼：Golomb編碼和編碼。3. 對三元組的最后一個分量字符 c，因為其分布并無規(guī)律可循，我們只能老老實實地用 8 個二進制位對其編碼。2022-4-29信息管理系64假設(shè)對正整數(shù)x進行Golomb編碼，選擇參數(shù)m，令b = 2mq = INT(x - 1)/b)r = x - qb 1則x可以被編碼為兩部分，第一部分是由q個1加1個0組成，第二部分為m位二進制數(shù)，其值為 r。值值 xm = 0m = 1m = 2m = 3100 00 000 0002100 10 010 00131

36、1010 00 100 0104111010 10 110 011511110110 010 000 1006111110110 110 010 101711111101110 010 100 1108111111101110 110 110 111911111111011110 0110 0010 0002022-4-29信息管理系65假設(shè)對x編碼，令q = int( log2x )則編碼的前一部分是q個1加一個0，后一部分是q位長的二進制數(shù)，其值等于(x-2q )值值 x編碼編碼10210 0310 14110 005110 016110 107110 1181110 00091110 0

37、012022-4-29信息管理系66LZ77算法的其他問題其他的編碼方式：1. 輸出匹配串時不輸出后續(xù)字符2. 輸出0表示下面是一個匹配串，輸出1表示下面是一個單個字符3. 對匹配串長度加以限制如何查找匹配串：1. 限制匹配串的長度，在內(nèi)存中組織二叉有序樹2. 將窗口中每個長度為3的字符串建立字典索引3. 使用Hash表建立索引4. 使用字符樹建立索引窗口滑動時內(nèi)存中的索引重建問題：1. 建立環(huán)狀偏移2. 以環(huán)狀偏移為基礎(chǔ)建立窗口索引2022-4-29信息管理系67LZSS算法 LZ77通過輸出真實字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個方面，一

38、是空指針，二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個匹配串中的字符。 LZSS算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針（匹配串長度大于等于MIN_LENGTH），否則就輸出真實字符。另外要輸出額外的標志位區(qū)分是指針還是字符。2022-4-29信息管理系68LZSS編碼的基本流程1、從當前壓縮位置開始，考察未編碼的字符，并試圖在滑動窗口中找出最長的匹配字符串，如果匹配串長度len大于等于最小匹配串長度（len = MIN_LENGTH），則進行步驟 2，否則進行步驟 3。2、輸出指針二元組 ( off, len)。其中 off 為窗口中匹配字符串相對窗口邊界的偏移

39、，len 為匹配串的長度，然后將窗口向后滑動 len 個字符，繼續(xù)步驟 1。3、輸出當前字符c，然后將窗口向后滑動 1 個字符，繼續(xù)步驟 1。2022-4-29信息管理系69LZSS編碼舉例位置位置1234567891011字符字符AABBCBBAABC步驟步驟位置位置匹配串匹配串輸出輸出11A22AA33B44BB55C66BB（3，2）78AAB（1，3）811CC輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：編碼過程編碼過程MIN_LEN =22022-4-29信息管理系70LZSS算法 在相同的計算機環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡單。這也就是為什么這種算法成為開發(fā)新算法的基

40、礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差別僅僅是指針的長短和窗口的大小等有所不同。 LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。2022-4-29信息管理系71第二類詞典編碼 第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典 (dictionary of the phrases)”，這種短語可以是任意字符的組合。編碼數(shù)據(jù)過程中當遇到已經(jīng)在詞典中出現(xiàn)的“短語”時，編碼器就輸出這個詞典中的短語的“索引號”，而不是短

41、語本身。2022-4-29信息管理系72LZ78算法 LZ78的編碼思想是不斷地從字符流中提取新的字符串(String)，通俗地理解為新“詞條”，然后用“代號”也就是碼字(Code word)表示這個“詞條”。這樣一來，對字符流的編碼就變成了用碼字(Code word)去替換字符流(Char stream)，生成碼字流(Code stream)，從而達到壓縮數(shù)據(jù)的目的。 LZ78編碼器的輸出是碼字-字符(W,C)對，每次輸出一對到碼字流中，與碼字W相對應(yīng)的字符串(String)用字符C進行擴展生成新的字符串(String)，然后添加到詞典中。2022-4-29信息管理系73算法中用到的幾個術(shù)語

42、: 字符流(Charstream)：待編碼的數(shù)據(jù)序列。 字符(Character)：字符流中的基本數(shù)據(jù)單元。 前綴(Prefix)：在一個字符之前的字符序列。 綴-符串(String)：前綴字符。 碼字(Code word)：碼字流中的基本數(shù)據(jù)單元，代表詞典中的一串字符。 2022-4-29信息管理系74碼流(Codestream)：碼字和字符組成的序列，是編碼器的輸出。 詞典(Dictionary)：綴-符串表。按照詞典中的索引號對每條綴-符串(String)指定一個碼字(Code word)。 當前前綴(Current prefix)：在編碼算法中使用，指當前正在處理的前綴，用符號P表示。

43、 當前字符(Current character)：在編碼算法中使用，指當前前綴之后的字符，用符號C表示。 當前碼字(Current code word)：在譯碼算法中使用，指當前處理的碼字，用W表示當前碼字，String.W表示當前碼字的綴-符串。2022-4-29信息管理系75LZ78編碼算法步驟1：在開始時，詞典和當前前綴P都是空的； 步驟2：當前字符C：=字符流中的下一個字符； 步驟3：判斷P+C是否在詞典中 (1) 如果“是”：用C擴展P，讓P：= P+C ； (2) 如果“否”： 輸出與當前前綴P相對應(yīng)的碼字和當前字符C； 把字符串P+C添加到詞典中； 令P：=空值； (3) 判斷字

44、符流中是否還有字符需要編碼 如果“是”：返回到步驟2； 如果“否”：若當前前綴P不是空的，輸出相應(yīng)于當前前綴P的碼字，然后結(jié)束編碼。 2022-4-29信息管理系76LZ78編碼舉例位置位置123456789字符字符ABBCBCABA步驟步驟位置位置詞典詞典輸出輸出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：編碼過程：編碼過程：2022-4-29信息管理系77LZ78譯碼的具體算法如下： 步驟1：在開始時詞典是空的； 步驟2：當前碼字W：=碼字流中的下一個碼字； 步驟3：當前字符C：= 緊隨碼字之后的字符； 步驟4：

45、把當前碼字的綴-符串(string.W)輸出到字符流，然后輸出字符C； 步驟5：把string.W+C添加到詞典中； 步驟6：判斷碼字流中是否還有碼字要譯 (1) 如果“是”，就返回到步驟2； (2) 如果“否”，則結(jié)束。2022-4-29信息管理系78LZW算法 J.Ziv和A.Lempel在1978年首次發(fā)表了介紹第二類詞典編碼算法的文章。在他們的研究基礎(chǔ)上，Terry A.Welch在1984年發(fā)表了改進這種編碼算法的文章，因此把這種編碼方法稱為LZW(Lempel-Ziv Walch)壓縮編碼。 2022-4-29信息管理系79在編碼原理上，LZW與LZ78相比有如下差別： LZW只輸

46、出代表詞典中的字符串(String)的碼字(code word)。這就意味在開始時詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個字符。即在編碼匹配時，至少可以在詞典中找到長度為1的匹配串。 LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。2022-4-29信息管理系80LZW算法的詞典算法的詞典 LZW編碼器(軟件編碼器或硬件編碼器)就是通過管理這個詞典完成輸入與輸出之間的轉(zhuǎn)換。LZW編碼器的輸入是字符流(Char stream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼字流 (Code stream)，碼字代表單個字符或多個字符組成的字符串(Str

47、ing)。2022-4-29信息管理系81LZW編碼算法步驟1： 開始時的詞典包含所有可能的根(Root)，而當前前綴P是空的；步驟2： 當前字符(C) :=字符流中的下一個字符；步驟3： 判斷綴-符串P+C是否在詞典中(1) 如果“是”：P := P+C / (用C擴展P)；(2) 如果“否” 把代表當前前綴P的碼字輸出到碼字流; 把綴-符串P+C添加到詞典; 令P := C /(現(xiàn)在的P僅包含一個字符C);步驟4： 判斷碼字流中是否還有碼字要譯(1) 如果“是”，就返回到步驟2；(2) 如果“否” 把代表當前前綴P的碼字輸出到碼字流; 結(jié)束。2022-4-29信息管理系82LZW編碼舉例位

48、置位置123456789字符字符ABBABABAC步驟步驟位置位置碼字碼字詞典詞典輸出輸出1A2B3C114AB1225BB2336BA2447ABA4558ABAC763輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：2022-4-29信息管理系83LZW算法 LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因為它不需要執(zhí)行那么多的綴-符串比較操作。對LZW算法進一步的改進是增加可變的碼字長度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進措施之后的LZW算法。 LZW算法取得了專利，專利權(quán)的所有者是美國的一個大型計算機公司Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟

49、件生產(chǎn)公司之外，可以免費使用LZW算法。2022-4-29信息管理系84LZW特點如下： l)LZW壓縮技術(shù)對于可預(yù)測性不大的數(shù)據(jù)具有較好的處理效果，常用于GIF格式的圖像壓縮，其平均壓縮比在2)1以上，最高壓縮比可達到3：1。 2)對于數(shù)據(jù)流中連續(xù)重復出現(xiàn)的字節(jié)和字串，LZW壓縮技術(shù)具有很高的壓縮比。 3)除了用于圖像數(shù)據(jù)處理以外，LZW壓縮技術(shù)還被用于文本程序等數(shù)據(jù)壓縮領(lǐng)域。2022-4-29信息管理系85 4)LZW壓縮技術(shù)有很多變體，例如常見的ARC、RKARC、PKZIP高效壓縮程序。 5)對于任意寬度和像素位長度的圖像，都具有穩(wěn)定的壓縮過程。壓縮和解壓縮速度較快。 6)對機器硬件條

50、件要求不高，在 Intel 80386的計算機上即可進行壓縮和解壓縮。2022-4-29信息管理系86比較：LZ77算法LZ77算法的基本流程：“滑動的窗口”1、從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進行步驟 2，否則進行步驟 3。2、輸出三元符號組(off,len,c)。其中off為窗口中匹配字符串相對窗口邊界的偏移，len為可匹配的長度，c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟 1。3、輸出三元符號組(0,0,c)。其中c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟 1。2022-4-29信息管理系87L

51、Z77算法應(yīng)用實例：窗口大小為10個字符，剛編碼過的10個字符為“abcdbbccaa”，即將編碼的10個字符為 “abaeaaabaee”。1. 我們首先發(fā)現(xiàn)，可以和待編碼字符匹配的最長串為ab(off=0,len=2), ab的下一個字符為a，我們輸出三元組：(0,2,a)2. 現(xiàn)在窗口向后滑動3個字符，窗口中的內(nèi)容為：dbbccaaaba3. 下一個字符e在窗口中沒有匹配，我們輸出三元組：(0,0,e)4. 窗口向后滑動1個字符，其中內(nèi)容變?yōu)椋篵bccaaabae5. 我們馬上發(fā)現(xiàn)，要編碼的aaabae在窗口中存在(off=4,len=6)，其后的字符為e，我們可以輸出：(4,6,e)6

52、. 這樣，我們將可以匹配的字符串都變成了指向窗口內(nèi)的指針，并由此完成了對上述數(shù)據(jù)的壓縮。7. 解壓縮時，只要我們向壓縮時那樣維護好滑動的窗口，隨著三元組的不斷輸入，我們在窗口中找到相應(yīng)的匹配串，綴上后繼字符c輸出（如果off和len都為0則只輸出后繼字符c)即可還原出原始數(shù)據(jù)。2022-4-29信息管理系88LZ78編碼算法步驟1：在開始時，詞典和當前前綴P都是空的； 步驟2：當前字符C：=字符流中的下一個字符； 步驟3：判斷P+C是否在詞典中 (1) 如果“是”：用C擴展P，讓P：= P+C ； (2) 如果“否”： 輸出與當前前綴P相對應(yīng)的碼字和當前字符C； 把字符串P+C添加到詞典中；

53、令P：=空值； (3) 判斷字符流中是否還有字符需要編碼 如果“是”：返回到步驟2； 如果“否”：若當前前綴P不是空的，輸出相應(yīng)于當前前綴P的碼字，然后結(jié)束編碼。 2022-4-29信息管理系89LZ78編碼舉例位置位置123456789字符字符ABBCBCABA步驟步驟位置位置詞典詞典輸出輸出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：編碼過程：編碼過程：2022-4-29信息管理系90LZW編碼算法步驟1： 開始時的詞典包含所有可能的根(Root)，而當前前綴P是空的；步驟2： 當前字符(C) :=字符流中的下一

54、個字符；步驟3： 判斷綴-符串P+C是否在詞典中(1) 如果“是”：P := P+C / (用C擴展P)；(2) 如果“否” 把代表當前前綴P的碼字輸出到碼字流; 把綴-符串P+C添加到詞典; 令P := C /(現(xiàn)在的P僅包含一個字符C);步驟4： 判斷碼字流中是否還有碼字要譯(1) 如果“是”，就返回到步驟2；(2) 如果“否” 把代表當前前綴P的碼字輸出到碼字流; 結(jié)束。2022-4-29信息管理系91LZW編碼舉例位置位置123456789字符字符ABBABABAC步驟步驟位置位置碼字碼字詞典詞典輸出輸出1A2B3C114AB1225BB2336BA2447ABA4558ABAC763輸入數(shù)據(jù)流：輸入數(shù)據(jù)流：2022-4-29信息管理系92行程編碼（RLE） 行程編碼（Run-Length Encoding）：它通過將信源中相同符號序列轉(zhuǎn)換成一個計數(shù)字段再