多媒體技術(shù)基礎(chǔ)3版2章數(shù)據(jù)無損壓縮.ppt

多媒體技術(shù)基礎(chǔ)(第3版) 第2章數(shù)據(jù)無損壓縮,張奇 復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 2015年4月,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,2 of 72,第2章 數(shù)據(jù)無損壓縮目錄,2.1 數(shù)據(jù)的冗余 2.1.1 冗余概念 2.1.2 決策量 2.1.3 信息量 2.1.4 熵 2.1.5 數(shù)據(jù)冗余量 2.2 統(tǒng)計(jì)編碼 2.2.1 香農(nóng)-范諾編碼 2.2.2 霍夫曼編碼 2.2.3 算術(shù)編碼,2.3 RLE編碼 2.4 詞典編碼 2.4.1 詞典編碼的思想 2.4.2 LZ77算法 2.4.3 LZSS算法 2.4.4 LZ78算法 2.4.5 LZW算法 參考文獻(xiàn)和站點(diǎn),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,3 of 72,2.0 數(shù)據(jù)無損壓縮概述,數(shù)據(jù)可被壓縮的依據(jù) 數(shù)據(jù)本身存在冗余 聽覺系統(tǒng)的敏感度有限 視覺系統(tǒng)的敏感度有限 三種多媒體數(shù)據(jù)類型 文字 (text)數(shù)據(jù)無損壓縮 根據(jù)數(shù)據(jù)本身的冗余(Based on data redundancy) 聲音(audio)數(shù)據(jù)有損壓縮 根據(jù)數(shù)據(jù)本身的冗余(Based on data redundancy) 根據(jù)人的聽覺系統(tǒng)特性( Based on human hearing system) 圖像(image)/視像(video) 數(shù)據(jù)有損壓縮 根據(jù)數(shù)據(jù)本身的冗余(Based on data redundancy) 根據(jù)人的視覺系統(tǒng)特性(Based on human visual system),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,4 of 72,2.0 數(shù)據(jù)無損壓縮概述(續(xù)1),數(shù)據(jù)無損壓縮的理論信息論(information theory) 1948年創(chuàng)建的數(shù)學(xué)理論的一個(gè)分支學(xué)科，研究信息的編碼、傳輸和存儲(chǔ) 該術(shù)語源于Claude Shannon (香農(nóng))發(fā)表的“A Mathematical Theory of Communication”論文題目，提議用二進(jìn)制數(shù)據(jù)對(duì)信息進(jìn)行編碼 最初只應(yīng)用于通信工程領(lǐng)域，后來擴(kuò)展到包括計(jì)算在內(nèi)的其他多個(gè)領(lǐng)域，如信息的存儲(chǔ)、信息的檢索等。在通信方面，主要研究數(shù)據(jù)量、傳輸速率、信道容量、傳輸正確率等問題。 數(shù)據(jù)無損壓縮的方法 霍夫曼編碼(Huffman coding ) 算術(shù)編碼(arithmetic coding) 行程長(zhǎng)度編碼(run-length coding) 詞典編碼(dictionary coding) ,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,5 of 72,2.0 數(shù)據(jù)無損壓縮概述(續(xù)2),The Father of Information Theory Claude Elwood Shannon Born: 30 April 1916 in Gaylord, Michigan, USA Died: 24 Feb 2001 in Medford, Massachusetts, USA,/news/2001/february/26/1.html,信息論之父介紹,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,6 of 72,2.0 數(shù)據(jù)無損壓縮概述(續(xù)3),Claude Shannon The founding father of electronic communications age；American mathematical engineer In 19361940, MIT: Masters thesis, A symbolic analysis of relay and switching circuits Doctoral thesis: on theoretical genetics In 1948: A mathematical theory of communication, landmark, climax (An important feature of Shannons theory: concept of entropy ),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,7 of 72,2.1 數(shù)據(jù)的冗余,冗余概念 人為冗余 在信息處理系統(tǒng)中，使用兩臺(tái)計(jì)算機(jī)做同樣的工作是提高系統(tǒng)可靠性的一種措施 在數(shù)據(jù)存儲(chǔ)和傳輸中，為了檢測(cè)和恢復(fù)在數(shù)據(jù)存儲(chǔ)或數(shù)據(jù)傳輸過程中出現(xiàn)的錯(cuò)誤，根據(jù)使用的算法的要求，在數(shù)據(jù)存儲(chǔ)或數(shù)據(jù)傳輸之前把額外的數(shù)據(jù)添加到用戶數(shù)據(jù)中，這個(gè)額外的數(shù)據(jù)就是冗余數(shù)據(jù) 視聽冗余 由于人的視覺系統(tǒng)和聽覺系統(tǒng)的局限性，在圖像數(shù)據(jù)和聲音數(shù)據(jù)中，有些數(shù)據(jù)確實(shí)是多余的，使用算法將其去掉后并不會(huì)丟失實(shí)質(zhì)性的信息或含義，對(duì)理解數(shù)據(jù)表達(dá)的信息幾乎沒有影響 數(shù)據(jù)冗余 不考慮數(shù)據(jù)來源時(shí)，單純數(shù)據(jù)集中也可能存在多余的數(shù)據(jù)，去掉這些多余數(shù)據(jù)并不會(huì)丟失任何信息，這種冗余稱為數(shù)據(jù)冗余，而且還可定量表達(dá),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,8 of 72,2.1 數(shù)據(jù)的冗余(續(xù)1),決策量(decision content) 在有限數(shù)目的互斥事件集合中，決策量是事件數(shù)的對(duì)數(shù)值 在數(shù)學(xué)上表示為 H0=log(n) 其中，n是事件數(shù) 決策量的單位由對(duì)數(shù)的底數(shù)決定 Sh (Shannon): 用于以2為底的對(duì)數(shù) Nat (natural unit): 用于以e為底的對(duì)數(shù) Hart (hartley)：用于以10為底的對(duì)數(shù),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,9 of 72,2.1 數(shù)據(jù)的冗余(續(xù)2),信息量(information content) 具有確定概率事件的信息的定量度量 在數(shù)學(xué)上定義為 其中， 是事件出現(xiàn)的概率 舉例：假設(shè)X=a,b,c是由3個(gè)事件構(gòu)成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分別是事件a, b和c出現(xiàn)的概率，這些事件的信息量分別為， I(a)=log2(1/0.50)=1 sh I(b)=log2(1/0.25)=2 sh I(c)=log2(1/0.25)=2 sh 一個(gè)等概率事件的集合，每個(gè)事件的信息量等于該集合的決策量,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,10 of 72,2.1 數(shù)據(jù)的冗余(續(xù)3),熵(entropy) 按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量的平均值，也稱事件的平均信息量(mean information content) 用數(shù)學(xué)表示為,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,11 of 72,2.1 數(shù)據(jù)的冗余(續(xù)4),數(shù)據(jù)的冗余量,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,12 of 72,2.2 統(tǒng)計(jì)編碼,統(tǒng)計(jì)編碼 給已知統(tǒng)計(jì)信息的符號(hào)分配代碼的數(shù)據(jù)無損壓縮方法 編碼方法 香農(nóng)-范諾編碼 霍夫曼編碼 算術(shù)編碼 編碼特性 香農(nóng)-范諾編碼和霍夫曼編碼的原理相同，都是根據(jù)符號(hào)集中各個(gè)符號(hào)出現(xiàn)的頻繁程度來編碼，出現(xiàn)次數(shù)越多的符號(hào)，給它分配的代碼位數(shù)越少 算術(shù)編碼使用0和1之間的實(shí)數(shù)的間隔長(zhǎng)度代表概率大小，概率越大間隔越長(zhǎng)，編碼效率可接近于熵,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,13 of 72,2.2.1 統(tǒng)計(jì)編碼香農(nóng)-范諾編碼,香農(nóng)-范諾編碼(ShannonFano coding) 在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量 在計(jì)算熵時(shí)，如果對(duì)數(shù)的底數(shù)用2，熵的單位就用“香農(nóng)(Sh)”，也稱“位(bit)” ?！拔弧笔?948年Shannon首次使用的術(shù)語。例如,最早闡述和實(shí)現(xiàn)“從上到下”的熵編碼方法的人是Shannon(1948年)和Fano(1949年)，因此稱為香農(nóng)-范諾(Shannon- Fano)編碼法,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,14 of 72,2.2.1 香農(nóng)-范諾編碼,香農(nóng)-范諾編碼舉例 有一幅40個(gè)像素組成的灰度圖像，灰度共有5級(jí)，分別用符號(hào)A，B，C，D和E表示。40個(gè)像素中出現(xiàn)灰度A的像素?cái)?shù)有15個(gè)，出現(xiàn)灰度B的像素?cái)?shù)有7個(gè)，出現(xiàn)灰度C的像素?cái)?shù)有7個(gè)，其余情況見表2-1 (1) 計(jì)算該圖像可能獲得的壓縮比的理論值 (2) 對(duì)5個(gè)符號(hào)進(jìn)行編碼 (3) 計(jì)算該圖像可能獲得的壓縮比的實(shí)際值 表2-1 符號(hào)在圖像中出現(xiàn)的數(shù)目,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,15 of 72,2.2.1 香農(nóng)-范諾編碼(續(xù)1),(1) 壓縮比的理論值 按照常規(guī)的編碼方法，表示5個(gè)符號(hào)最少需要3位，如用000表示A，001表示B，100表示E，其余3個(gè)代碼 (101，110，111)不用。這就意味每個(gè)像素用3位，編碼這幅圖像總共需要120位。按照香農(nóng)理論，這幅圖像的熵為,這個(gè)數(shù)值表明，每個(gè)符號(hào)不需要用3位構(gòu)成的代碼表示，而用2.196位就可以，因此40個(gè)像素只需用87.84位就可以，因此在理論上，這幅圖像的的壓縮比為120:87.841.37:1，實(shí)際上就是3:2.1961.37,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,16 of 72,2.2.1 香農(nóng)-范諾編碼(續(xù)2),(2) 符號(hào)編碼 對(duì)每個(gè)符號(hào)進(jìn)行編碼時(shí)采用“從上到下”的方法。首先按照符號(hào)出現(xiàn)的頻度或概率排序，如A，B，C，D和E，見表2-2。然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)，如圖2-1所示,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,17 of 72,2.2.1 香農(nóng)-范諾編碼(續(xù)3),（3）壓縮比的實(shí)際值 按照這種方法進(jìn)行編碼需要的總位數(shù)為30+14+14+18+1591，實(shí)際的壓縮比為120:911.32 : 1,圖2-1 香農(nóng)-范諾算法編碼舉例,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,18 of 72,2.2.2 統(tǒng)計(jì)編碼霍夫曼編碼,霍夫曼編碼(Huffman coding) 霍夫曼(D.A. Huffman)在1952年提出和描述的“從下到上”的熵編碼方法 根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少 廣泛用在JPEG, MPEG, H.26X等各種信息編碼標(biāo)準(zhǔn)中,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,19 of 72,2.2.2 霍夫曼編碼 Case Study 1,霍夫曼編碼舉例1 現(xiàn)有一個(gè)由5個(gè)不同符號(hào)組成的30個(gè)符號(hào)的字符串：BABACACADADABBCBABEBEDDABEEEBB 計(jì)算 (1) 該字符串的霍夫曼碼 (2) 該字符串的熵 (3) 該字符串的平均碼長(zhǎng) (4) 編碼前后的壓縮比,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,20 of 72,2.2.2 霍夫曼編碼 Case Study 1 (續(xù)1),符號(hào)出現(xiàn)的概率,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,21 of 72,2.2.2 霍夫曼編碼 Case Study 1 (續(xù)2),(1) 計(jì)算該字符串的霍夫曼碼 步驟：按照符號(hào)出現(xiàn)概率大小的順序?qū)Ψ?hào)進(jìn)行排序 步驟：把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)P1 步驟：重復(fù)步驟，得到節(jié)點(diǎn)P2，P3，P4， PN，形成一棵樹，其中的PN稱為根節(jié)點(diǎn) 步驟：從根節(jié)點(diǎn)PN開始到每個(gè)符號(hào)的樹葉，從上到下 標(biāo)上0(上枝)和1(下枝)，至于哪個(gè)為1哪個(gè)為0則 無關(guān)緊要，但通常把概率大的標(biāo)成1，概率小的 標(biāo)成0 步驟：從根節(jié)點(diǎn)PN開始順著樹枝到每個(gè)葉子分別寫出 每個(gè)符號(hào)的代碼,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,22 of 72,2.2.2 霍夫曼編碼 Case Study 1 (續(xù)3),符號(hào) B (10) A (8) E (5) D (4) C (3),P1 (7),P2 (12),P3 (18),P4 (30),0,1,1,0,1,0,1,0,代碼 B(11) A(10) E(00) D(011) C(010),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,23 of 72,2.2.2 霍夫曼編碼 Case Study 1 (續(xù)4),30個(gè)字符組成的字符串需要67位,5個(gè)符號(hào)的代碼,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,24 of 72,2.2.2 霍夫曼編碼 Case Study 1 (續(xù)5),(2) 計(jì)算該字符串的熵 其中， 是事件 的集合， 并滿足,H(S) =(8/30)log2(30/8) + (10/30)log2(30/10) + (3/30)log2(30/3) + (4/30)log2(30/4) + (5/30)log2(30/5) = 30lg30 (8lg8 10lg10 3lg3 4 lg4 5 lg5) / (30log22) = ( 44.313624.5592)/ 9.0308 2.1874 (Sh),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,25 of 72,2.2.2 霍夫曼編碼 Case Study 1 (續(xù)6),(3) 計(jì)算該字符串的平均碼長(zhǎng) 平均碼長(zhǎng)： (28210333425)/30 2.233 位/符號(hào),壓縮比: 90/67=1.34:1,平均碼長(zhǎng)：67/30=2.233位,(4) 計(jì)算編碼前后的壓縮比 編碼前：5個(gè)符號(hào)需3位，30個(gè)字符，需要90位 編碼后：共67位,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,26 of 72,2.2.2 霍夫曼編碼 Case Study 2,霍夫曼編碼舉例2 編碼前 N = 8 symbols: a,b,c,d,e,f,g,h, 3 bits per symbol (N =23=8) P(a) = 0.01, P(b)=0.02, P(c)=0.05, P(d)=0.09, P(e)=0.18, P(f)=0.2, P(g)=0.2, P(h)=0.25 計(jì)算 (1) 該字符串的霍夫曼碼 (2) 該字符串的熵 (3) 該字符串的平均碼長(zhǎng) (4) 編碼效率,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,27 of 72,2.2.2 霍夫曼編碼 Case Study 2 (續(xù)1),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,28 of 72,2.2.2 霍夫曼編碼 Case Study 2 (續(xù)2),Average length per symbol (before coding):,(2) Entropy:,(3) Average length per symbol (with Huffman coding):,(4) Efficiency of the code:,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,29 of 72,2.2.3 統(tǒng)計(jì)編碼算術(shù)編碼,算術(shù)編碼(arithmetic coding) 給已知統(tǒng)計(jì)信息的符號(hào)分配代碼的數(shù)據(jù)無損壓縮技術(shù) 基本思想是用0和1之間的一個(gè)數(shù)值范圍表示輸入流中的一個(gè)字符，而不是給輸入流中的每個(gè)字符分別指定一個(gè)碼字 實(shí)質(zhì)上是為整個(gè)輸入字符流分配一個(gè)“碼字”，因此它的編碼效率可接近于熵,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,30 of 72,2.2.3 算術(shù)編碼舉例,例2.3（取自教材） 假設(shè)信源符號(hào)為00, 01, 10, 11，它們的概率分別為 0.1, 0.4, 0.2, 0.3 對(duì)二進(jìn)制消息序列10 00 11 00 10 11 01 進(jìn)行算術(shù)編碼,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,31 of 72,2.2.3 算術(shù)編碼舉例(續(xù)1),表2-4 例2.3的信源符號(hào)概率和初始編碼間隔,初始化 根據(jù)信源符號(hào)的概率把間隔0, 1)分成如表2-4所示的4個(gè)子間隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)。其中x, y)的表示半開放間隔，即包含x不包含y，x稱為低邊界或左邊界，y稱為高邊界或右邊界,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,32 of 72,2.2.3 算術(shù)編碼舉例(續(xù)2),確定符號(hào)的編碼范圍 編碼時(shí)輸入第1個(gè)符號(hào)是10，找到它的編碼范圍是0.5, 0.7 消息中第2個(gè)符號(hào)00的編碼范圍是0, 0.1)，它的間隔就取0.5, 0.7)的第一個(gè)十分之一作為新間隔0.5, 0.52) 編碼第3個(gè)符號(hào)11時(shí)，取新間隔為0.514, 0.52) 編碼第4個(gè)符號(hào)00時(shí)，取新間隔為0.514, 0.5146) 依此類推 消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù) 整個(gè)編碼過程如圖2-3所示 編碼和譯碼的全過程分別見表2-5和表2-6,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,33 of 72,2.2.3 算術(shù)編碼舉例(續(xù)3),圖2-3 例2.3的算術(shù)編碼過程,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,34 of 72,2.2.3 算術(shù)編碼舉例(續(xù)4),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,35 of 72,2.2.3 算術(shù)編碼舉例(續(xù)5),2019年6月26日,第2章 數(shù)據(jù)無損壓縮,36 of 72,2.3 RLE編碼,行程長(zhǎng)度編碼(Run-Length Coding) 一種無損壓縮數(shù)據(jù)編碼技術(shù)，它利用重復(fù)的數(shù)據(jù)單元有相同的數(shù)值這一特點(diǎn)對(duì)數(shù)據(jù)進(jìn)行壓縮。對(duì)相同的數(shù)值只編碼一次，同時(shí)計(jì)算出相同值重復(fù)出現(xiàn)的次數(shù)。在JPEG，MPEG，H.261和H.263等壓縮方法中，RLE用來對(duì)圖像數(shù)據(jù)變換和量化后的系數(shù)進(jìn)行編碼 例: 假設(shè)有一幅灰度圖像第n行的像素值如圖2-5所示。用RLE編碼方法得到的代碼為：80315084180,圖2-5 RLE編碼概念,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,37 of 72,2.3 RLE編碼(續(xù)),Assumption: Long sequences of identical symbols. Example,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,38 of 72,2.4 詞典編碼,詞典編碼(dictionary coding) 文本中的詞用它在詞典中表示位置的號(hào)碼代替的一種無損數(shù)據(jù)壓縮方法。采用靜態(tài)詞典編碼技術(shù)時(shí)，編碼器需要事先構(gòu)造詞典，解碼器要事先知道詞典。采用動(dòng)態(tài)辭典編碼技術(shù)時(shí), 編碼器將從被壓縮的文本中自動(dòng)導(dǎo)出詞典，解碼器解碼時(shí)邊解碼邊構(gòu)造解碼詞典 兩種類型的編碼算法 具體算法 LZ77算法 LZSS算法 LZ78算法 LZW算法,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,39 of 72,2.4 詞典編碼(續(xù)1),第一類編碼算法 用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分 編碼器的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”,圖2-6 第一類詞典編碼概念,2019年6月26日,第2章 數(shù)據(jù)無損壓縮,40 of 72,2.4 詞典編碼(續(xù)2),第二類編碼算法 從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典(dictionary of the phrases)” 編碼器輸出詞典中的短語“索引號(hào)”，而不是短語,圖2-7 第二類詞典編碼概念,41,LZ77算法,第一類詞典編碼里：所指的“詞典”是指用以前處理過的數(shù)據(jù)來表示編碼過程中遇到的重復(fù)部分。 這類編碼中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年開發(fā)和發(fā)表的稱為L(zhǎng)Z77算法為基礎(chǔ)的 Jacob Ziv, Abraham Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, 23(3):337-343, May 1977.,42,LZ77算法,LZ77 算法在某種意義上又可以稱為“滑動(dòng)窗口壓縮”，該算法將一個(gè)虛擬的，可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長(zhǎng)度。,43,LZ77,首先介紹算法中用到的幾個(gè)術(shù)語： 輸入數(shù)據(jù)流(input stream)：要被壓縮的字符序列。 字符(character)：輸入數(shù)據(jù)流中的基本單元。 編碼位置(coding position)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開始字符。 前向緩沖存儲(chǔ)器(Lookahead buffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。 窗口(window)：指包含W個(gè)字符的窗口，字符從編碼位置開始向后數(shù)，也就是最后處理的字符數(shù)。 指針(pointer)：指向窗口中的匹配串，一般含有長(zhǎng)度。,W=5,B=4,44,圖例,輸入數(shù)據(jù)流,45,LZ77算法核心,LZ77編碼算法的核心：查找從前向緩沖存儲(chǔ)器開始的最長(zhǎng)的匹配串。編碼算法的具體執(zhí)行步驟如下： 把編碼位置設(shè)置到輸入數(shù)據(jù)流的開始位置。 查找窗口中最長(zhǎng)的匹配串。 以“(Pointer, Length) Characters”的格式輸出，其中Pointer是指向窗口中匹配串的指針，Length表示匹配字符的長(zhǎng)度，Characters是前向緩沖存儲(chǔ)器中的不匹配的第1個(gè)字符。 如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移(Length+1)個(gè)字符，然后返回到步驟2。,46,指針表示,(Pointer, Length) Characters 表示匹配的（字符位置，長(zhǎng)度）下一個(gè)不匹配的字符 指針可以以“(Back_chars, Chars_length) Explicit_character”格式輸出。 其中，(Back_chars, Chars_length)是指向匹配串的指針，告訴譯碼器“在這個(gè)窗口中向后退Back_chars個(gè)字符然后拷貝Chars_length個(gè)字符到輸出”，Explicit_character是真實(shí)字符。,47,例子,W=5,B=2,每次移動(dòng)窗口和編碼位置Len+1,48,LZ77的問題,LZ77通過輸出真實(shí)字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個(gè)解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個(gè)方面， 一是空指針 例如前一個(gè)例子中 (0,0) C 二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。,49,LZSS算法,1982年由Storer和Szymanski改進(jìn)LZ77 LZSS算法以比較有效的方法解決這個(gè)問題， 它的思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度長(zhǎng)就輸出指針，否則就輸出真實(shí)字符。由于輸出的壓縮數(shù)據(jù)流中包含有指針和字符本身，為了區(qū)分它們就需要有額外的標(biāo)志位，即ID位。,50,LZSS編碼算法步驟,把編碼位置置于輸入數(shù)據(jù)流的開始位置。 在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串 Pointer ：=匹配串指針。 Length ：=匹配串長(zhǎng)度。 判斷匹配串長(zhǎng)度Length是否大于等于最小匹配串長(zhǎng)度(LengthMIN_LENGTH) ， 如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。 如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。 如果前向緩沖存儲(chǔ)器不是空的，就返回到步驟2,51,例子,編碼過程(MIN_LENGTH = 2，W=10, B=3),Len=12,52,LZSS與LZ77比較,在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。這也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同。 LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。,53,LZ78原理,LZ78的編碼思想是不斷地從字符流中提取新的字符串(String)，通俗地理解為新“詞條”，然后用“代號(hào)”也就是碼字(Code word)表示這個(gè)“詞條”。這樣一來，對(duì)字符流的編碼就變成了用碼字(Code word)去替換字符流(Char stream)，生成碼字流(Code stream)，從而達(dá)到壓縮數(shù)據(jù)的目的。,54,LZ77與LZ78比較,LZ77利用滑動(dòng)窗口里的內(nèi)容作為字典，找最長(zhǎng)子串 LZ78動(dòng)態(tài)構(gòu)建字典,55,LZ78編碼,在編碼開始時(shí)詞典是空的，不包含任何字符串(string)。在這種情況下編碼器就輸出一個(gè)表示空字符串的特殊碼字(例如“0”)和字符流中(Charstream)的第一個(gè)字符C，并把這個(gè)字符C添加到詞典中作為一個(gè)由一個(gè)字符組成的字符串(string)。在編碼過程中，如果出現(xiàn)類似沒有任何匹配的情況，也照此辦理。 在詞典中已經(jīng)包含某些字符串(String)之后，如果“當(dāng)前前綴P +當(dāng)前字符C”已經(jīng)在詞典中，就用字符C來擴(kuò)展這個(gè)前綴，這樣的擴(kuò)展操作一直重復(fù)到獲得一個(gè)在詞典中沒有的字符串(String)為止。 此時(shí)就輸出表示當(dāng)前前綴P的碼字(Code word)和字符C，并把P+C添加到詞典中，然后開始處理字符流(Charstream)中的下一個(gè)字符。,56,算法,在開始時(shí)，詞典和當(dāng)前前綴P都是空的。 當(dāng)前字符C ：=字符流中的下一個(gè)字符。 判斷P+C是否在詞典中： (1) 如果“是”：用C擴(kuò)展P，讓P ：= P+C ； (2) 如果“否”： 輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字和當(dāng)前字符C； 把字符串P+C 添加到詞典中。 令P ：=空值。 (3) 判斷字符流中是否還有字符需要編碼 如果“是”：返回到步驟2。 如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。,57,LZ78編碼輸出,LZ78編碼器的輸出是碼字-字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的字符串(String)用字符C進(jìn)行擴(kuò)展生成新的字符串(String)，然后添加到詞典中。,58,例子,59,LZ78與LZ77,LZ78在每個(gè)編碼步驟中減少了string比較數(shù)目 LZ77需要找最長(zhǎng)匹配子串 壓縮率與LZ77類似。,60,LZW,Terry A.Weltch在1984年發(fā)表了改進(jìn)LZ78的文章，因此把這種編碼方法稱為L(zhǎng)ZW (Lempel-Ziv Walch),61,LZW與LZ78編碼原理差別,LZW只輸出代表詞典中的字符串(String)的碼字(code word)。這就意味在開始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。 由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每個(gè)編碼步驟開始時(shí)都使用一字符前綴(one-character prefix)，因此至少可以在詞典中找到長(zhǎng)度為1的匹配串。,62,LZW的詞典,LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。這張轉(zhuǎn)換表用來存放稱為前綴(Prefix)的字符序列，并且為每個(gè)表項(xiàng)分配一個(gè)碼字(Code word)，或者叫做序號(hào)。 Welch的論文中用了12位碼字，12位可以有4096個(gè)不同的12位代碼，這就是說，轉(zhuǎn)換表有4096個(gè)表項(xiàng)，其中256個(gè)表項(xiàng)用來存放已定義的字符，剩下3840個(gè)表項(xiàng)用來存放前綴(Prefix)。,63,例子,64,LZW編碼,LZW編碼器就是通過管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換。 LZW編碼器的輸入是字符流(Char stream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼字流 (Code stream)，碼字代表單個(gè)字符或多個(gè)字符組成的字符串(String)。LZ78輸出是碼字+字符,193,65,貪婪分析算法,LZW采用greedy parsing algorithm 每一次分析都要串行地檢查來自字符流(Charstream)的字符串，從中分解出已經(jīng)識(shí)別的最長(zhǎng)的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長(zhǎng)的前綴(Prefix)。 用已知的前綴(Prefix)加上下一個(gè)輸入字符C也就是當(dāng)前字符(Current character)作為該前綴的擴(kuò)展字符，形成新的擴(kuò)展字符串。 判斷新的串是否在詞典中 是：繼續(xù)輸入C 否：加入詞典，分配碼字,66,具體執(zhí)行步驟,開始時(shí)詞典包含所有可能的根(Root)，當(dāng)前前綴P是空的； 當(dāng)前字符(C) ：=字符流中的下一個(gè)字符； 判斷綴-符串P+C是否在詞典中 如果“是”：P ：= P+C / (用C擴(kuò)展P) ； 如果“否” 把代表當(dāng)前前綴P的碼字輸出到碼字流; 把綴-符串P+C添加到詞典; 令P ：= C /(現(xiàn)在的P僅包含一個(gè)字符C);,67,4. 判斷字符流中是否還有字符需要編碼 (1) 如果“是”，就返回到步驟2； (2) 如果“否” 把代表當(dāng)前前綴P的碼字輸出到碼字流; 結(jié)束。 注意：每個(gè)輸出的碼字對(duì)應(yīng)于詞典中的一個(gè)詞條，因?yàn)橹挥挟?dāng)出現(xiàn)新的字符串的時(shí)候才輸出碼字。,68,69,LZW的特點(diǎn),1) 對(duì)于一段短語，它只輸出一個(gè)數(shù)字，即字典中的序號(hào)。（這個(gè)數(shù)字的位數(shù)決定了字典的最大容量，當(dāng)它的位數(shù)取得太大時(shí)，比如 24 位以上，對(duì)于短匹配占多數(shù)的情況，壓縮率可能很低。取得太小時(shí)，比如 8 位，字典的容量受到限制。所以同樣需要取舍。）