第2章數(shù)據(jù)無(wú)損壓縮課件

多媒體技術(shù)基礎(chǔ)(第3版)

第2章數(shù)據(jù)無(wú)損壓縮2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮2of72第2章數(shù)據(jù)無(wú)損壓縮目錄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.3RLE編碼2.4詞典編碼2.4.1詞典編碼的思想2.4.2LZ77算法2.4.3LZSS算法2.4.4LZ78算法2.4.5LZW算法參考文獻(xiàn)和站點(diǎn)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮3of722.0數(shù)據(jù)無(wú)損壓縮概述數(shù)據(jù)可被壓縮的依據(jù)數(shù)據(jù)本身存在冗余聽(tīng)覺(jué)系統(tǒng)的敏感度有限視覺(jué)系統(tǒng)的敏感度有限三種多媒體數(shù)據(jù)類型文字(text)數(shù)據(jù)——無(wú)損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)聲音(audio)數(shù)據(jù)——有損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)根據(jù)人的聽(tīng)覺(jué)系統(tǒng)特性(Basedonhumanhearingsystem)圖像(image)/視像(video)數(shù)據(jù)——有損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)根據(jù)人的視覺(jué)系統(tǒng)特性(Basedonhumanvisualsystem)

2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮4of722.0數(shù)據(jù)無(wú)損壓縮概述(續(xù)1)數(shù)據(jù)無(wú)損壓縮的理論——信息論(informationtheory)1948年創(chuàng)建的數(shù)學(xué)理論的一個(gè)分支學(xué)科，研究信息的編碼、傳輸和存儲(chǔ)該術(shù)語(yǔ)源于ClaudeShannon(香農(nóng))發(fā)表的“AMathematicalTheoryofCommunication”論文題目，提議用二進(jìn)制數(shù)據(jù)對(duì)信息進(jìn)行編碼最初只應(yīng)用于通信工程領(lǐng)域，后來(lái)擴(kuò)展到包括計(jì)算在內(nèi)的其他多個(gè)領(lǐng)域，如信息的存儲(chǔ)、信息的檢索等。在通信方面，主要研究數(shù)據(jù)量、傳輸速率、信道容量、傳輸正確率等問(wèn)題。數(shù)據(jù)無(wú)損壓縮的方法霍夫曼編碼(Huffmancoding)算術(shù)編碼(arithmeticcoding)行程長(zhǎng)度編碼(run-lengthcoding)詞典編碼(dictionarycoding)……2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮5of722.0數(shù)據(jù)無(wú)損壓縮概述(續(xù)2)TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2019inMedford,Massachusetts,USAbell-labs/news/2019/february/26/1.html信息論之父介紹2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮6of722.0數(shù)據(jù)無(wú)損壓縮概述(續(xù)3)ClaudeShannon

——Thefoundingfatherofelectroniccommunicationsage；AmericanmathematicalengineerIn1936~1940,MIT:Master'sthesis,AsymbolicanalysisofrelayandswitchingcircuitsDoctoralthesis:ontheoreticalgeneticsIn1948:Amathematicaltheoryofcommunication,landmark,climax(AnimportantfeatureofShannon'stheory:conceptofentropy)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮7of722.1數(shù)據(jù)的冗余冗余概念人為冗余在信息處理系統(tǒng)中，使用兩臺(tái)計(jì)算機(jī)做同樣的工作是提高系統(tǒng)可靠性的一種措施在數(shù)據(jù)存儲(chǔ)和傳輸中，為了檢測(cè)和恢復(fù)在數(shù)據(jù)存儲(chǔ)或數(shù)據(jù)傳輸過(guò)程中出現(xiàn)的錯(cuò)誤，根據(jù)使用的算法的要求，在數(shù)據(jù)存儲(chǔ)或數(shù)據(jù)傳輸之前把額外的數(shù)據(jù)添加到用戶數(shù)據(jù)中，這個(gè)額外的數(shù)據(jù)就是冗余數(shù)據(jù)視聽(tīng)冗余由于人的視覺(jué)系統(tǒng)和聽(tīng)覺(jué)系統(tǒng)的局限性，在圖像數(shù)據(jù)和聲音數(shù)據(jù)中，有些數(shù)據(jù)確實(shí)是多余的，使用算法將其去掉后并不會(huì)丟失實(shí)質(zhì)性的信息或含義，對(duì)理解數(shù)據(jù)表達(dá)的信息幾乎沒(méi)有影響數(shù)據(jù)冗余不考慮數(shù)據(jù)來(lái)源時(shí)，單純數(shù)據(jù)集中也可能存在多余的數(shù)據(jù)，去掉這些多余數(shù)據(jù)并不會(huì)丟失任何信息，這種冗余稱為數(shù)據(jù)冗余，而且還可定量表達(dá)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮8of722.1數(shù)據(jù)的冗余(續(xù)1)決策量(decisioncontent)在有限數(shù)目的互斥事件集合中，決策量是事件數(shù)的對(duì)數(shù)值在數(shù)學(xué)上表示為

H0=log(n)其中，n是事件數(shù)決策量的單位由對(duì)數(shù)的底數(shù)決定Sh(Shannon):用于以2為底的對(duì)數(shù)Nat(naturalunit):用于以e為底的對(duì)數(shù)Hart(hartley)：用于以10為底的對(duì)數(shù)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮9of722.1數(shù)據(jù)的冗余(續(xù)2)信息量(informationcontent)具有確定概率事件的信息的定量度量在數(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)=1shI(b)=log2(1/0.25)=2shI(c)=log2(1/0.25)=2sh一個(gè)等概率事件的集合，每個(gè)事件的信息量等于該集合的決策量2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮10of722.1數(shù)據(jù)的冗余(續(xù)3)熵(entropy)按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量的平均值，也稱事件的平均信息量(meaninformationcontent)用數(shù)學(xué)表示為2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮11of722.1數(shù)據(jù)的冗余(續(xù)4)數(shù)據(jù)的冗余量2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮12of722.2統(tǒng)計(jì)編碼 統(tǒng)計(jì)編碼給已知統(tǒng)計(jì)信息的符號(hào)分配代碼的數(shù)據(jù)無(wú)損壓縮方法編碼方法香農(nóng)-范諾編碼霍夫曼編碼算術(shù)編碼編碼特性香農(nóng)-范諾編碼和霍夫曼編碼的原理相同，都是根據(jù)符號(hào)集中各個(gè)符號(hào)出現(xiàn)的頻繁程度來(lái)編碼，出現(xiàn)次數(shù)越多的符號(hào)，給它分配的代碼位數(shù)越少算術(shù)編碼使用0和1之間的實(shí)數(shù)的間隔長(zhǎng)度代表概率大小，概率越大間隔越長(zhǎng)，編碼效率可接近于熵2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮13of722.2.1統(tǒng)計(jì)編碼——香農(nóng)-范諾編碼 香農(nóng)-范諾編碼(Shannon–Fanocoding)在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量在計(jì)算熵時(shí)，如果對(duì)數(shù)的底數(shù)用2，熵的單位就用“香農(nóng)(Sh)”，也稱“位(bit)”?！拔弧笔?948年Shannon首次使用的術(shù)語(yǔ)。例如最早闡述和實(shí)現(xiàn)“從上到下”的熵編碼方法的人是Shannon(1948年)和Fano(1949年)，因此稱為香農(nóng)-范諾(Shannon-Fano)編碼法2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮14of722.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è)，其余情況見(jiàn)表2-1(1)計(jì)算該圖像可能獲得的壓縮比的理論值(2)對(duì)5個(gè)符號(hào)進(jìn)行編碼(3)計(jì)算該圖像可能獲得的壓縮比的實(shí)際值表2-1符號(hào)在圖像中出現(xiàn)的數(shù)目符號(hào)ABCDE出現(xiàn)的次數(shù)157765出現(xiàn)的概率15/407/407/406/405/402023年10月26日第2章數(shù)據(jù)無(wú)損壓縮15of722.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.84≈1.37:1，實(shí)際上就是3:2.196≈1.372023年10月26日第2章數(shù)據(jù)無(wú)損壓縮16of722.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，見(jiàn)表2-2。然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)，如圖2-1所示2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮17of722.2.1香農(nóng)-范諾編碼(續(xù)3)（3）壓縮比的實(shí)際值按照這種方法進(jìn)行編碼需要的總位數(shù)為30+14+14+18+15＝91，實(shí)際的壓縮比為120:91≈1.32:1圖2-1香農(nóng)-范諾算法編碼舉例

2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮18of722.2.2統(tǒng)計(jì)編碼——霍夫曼編碼 霍夫曼編碼(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“從下到上”的熵編碼方法根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來(lái)壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少?gòu)V泛用在JPEG,MPEG,H.26X等各種信息編碼標(biāo)準(zhǔn)中2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮19of722.2.2霍夫曼編碼—CaseStudy1霍夫曼編碼舉例1現(xiàn)有一個(gè)由5個(gè)不同符號(hào)組成的30個(gè)符號(hào)的字符串：BABACACADADABBCBABEBEDDABEEEBB計(jì)算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(zhǎng)(4)編碼前后的壓縮比2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮20of722.2.2霍夫曼編碼—CaseStudy1(續(xù)1)符號(hào)出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.585?A81.907?C33.322?D42.907?E52.585?合計(jì)30符號(hào)出現(xiàn)的概率2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮21of722.2.2霍夫曼編碼—CaseStudy1(續(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，形成一棵樹(shù)，其中的PN稱為根節(jié)點(diǎn)步驟④：從根節(jié)點(diǎn)PN開(kāi)始到每個(gè)符號(hào)的樹(shù)葉，從上到下

標(biāo)上0(上枝)和1(下枝)，至于哪個(gè)為1哪個(gè)為0則

無(wú)關(guān)緊要，但通常把概率大的標(biāo)成1，概率小的

標(biāo)成0步驟⑤：從根節(jié)點(diǎn)PN開(kāi)始順著樹(shù)枝到每個(gè)葉子分別寫(xiě)出

每個(gè)符號(hào)的代碼2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮22of722.2.2霍夫曼編碼—CaseStudy1(續(xù)3)符號(hào)B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代碼B(11)A(10)E(00)D(011)C(010)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮23of722.2.2霍夫曼編碼—CaseStudy1(續(xù)4)符號(hào)出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合計(jì)301.06730個(gè)字符組成的字符串需要67位5個(gè)符號(hào)的代碼2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮24of722.2.2霍夫曼編碼—CaseStudy1(續(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–(8×lg8＋

10×lg10＋

3×lg3＋

4

×lg4＋5lg5)]/(30×log22)

=(44.3136－24.5592)/9.0308＝

2.1874(Sh)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮25of722.2.2霍夫曼編碼—CaseStudy1(續(xù)6)(3)

計(jì)算該字符串的平均碼長(zhǎng)平均碼長(zhǎng)：

＝(2×8＋2×10＋3×3＋3×4＋2×5)/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位2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮26of722.2.2霍夫曼編碼—CaseStudy2霍夫曼編碼舉例2編碼前N=8symbols:{a,b,c,d,e,f,g,h},3bitspersymbol(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)編碼效率2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮27of722.2.2霍夫曼編碼—CaseStudy2(續(xù)1)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮28of722.2.2霍夫曼編碼—CaseStudy2(續(xù)2)Averagelengthpersymbol

(beforecoding):(2)Entropy:(3)Averagelengthpersymbol

(withHuffmancoding):(4)Efficiencyofthecode:2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮29of722.2.3統(tǒng)計(jì)編碼——算術(shù)編碼 算術(shù)編碼(arithmeticcoding)給已知統(tǒng)計(jì)信息的符號(hào)分配代碼的數(shù)據(jù)無(wú)損壓縮技術(shù)基本思想是用0和1之間的一個(gè)數(shù)值范圍表示輸入流中的一個(gè)字符，而不是給輸入流中的每個(gè)字符分別指定一個(gè)碼字實(shí)質(zhì)上是為整個(gè)輸入字符流分配一個(gè)“碼字”，因此它的編碼效率可接近于熵2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮30of722.2.3算術(shù)編碼舉例[例2.3]（取自教材）假設(shè)信源符號(hào)為{00,01,10,11}，它們的概率分別為{0.1,0.4,0.2,0.3}對(duì)二進(jìn)制消息序列10001100101101…進(jìn)行算術(shù)編碼2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮31of722.2.3算術(shù)編碼舉例(續(xù)1)符號(hào)00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,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)的表示半開(kāi)放間隔，即包含x不包含y，x稱為低邊界或左邊界，y稱為高邊界或右邊界2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮32of722.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è)編碼過(guò)程如圖2-3所示編碼和譯碼的全過(guò)程分別見(jiàn)表2-5和表2-62023年10月26日第2章數(shù)據(jù)無(wú)損壓縮33of722.2.3算術(shù)編碼舉例(續(xù)3)圖2-3例2.3的算術(shù)編碼過(guò)程2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮34of722.2.3算術(shù)編碼舉例(續(xù)4)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮35of722.2.3算術(shù)編碼舉例(續(xù)5)2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮36of722.3RLE編碼行程長(zhǎng)度編碼(Run-LengthCoding)一種無(wú)損壓縮數(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用來(lái)對(duì)圖像數(shù)據(jù)變換和量化后的系數(shù)進(jìn)行編碼例:假設(shè)有一幅灰度圖像第n行的像素值如圖2-5所示。用RLE編碼方法得到的代碼為：80315084180圖2-5RLE編碼概念2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮37of722.3RLE編碼(續(xù))Assumption:Longsequencesofidenticalsymbols.Example,2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮38of722.4詞典編碼詞典編碼(dictionarycoding)文本中的詞用它在詞典中表示位置的號(hào)碼代替的一種無(wú)損數(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算法2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮39of722.4詞典編碼(續(xù)1)第一類編碼算法用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分編碼器的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的“指針”圖2-6第一類詞典編碼概念2023年10月26日第2章數(shù)據(jù)無(wú)損壓縮40of722.4詞典編碼(續(xù)2)第二類編碼算法從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)詞典(dictionaryofthephrases)”編碼器輸出詞典中的短語(yǔ)“索引號(hào)”，而不是短語(yǔ)圖2-7第二類詞典編碼概念41LZ77算法第一類詞典編碼里：所指的“詞典”是指用以前處理過(guò)的數(shù)據(jù)來(lái)表示編碼過(guò)程中遇到的重復(fù)部分。這類編碼中的所有算法都是以AbrahamLempel和JakobZiv在1977年開(kāi)發(fā)和發(fā)表的稱為L(zhǎng)Z77算法為基礎(chǔ)的JacobZiv,AbrahamLempel,AUniversalAlgorithmforSequentialDataCompression,IEEETransactionsonInformationTheory,23(3):337-343,May1977.42LZ77算法LZ77算法在某種意義上又可以稱為“滑動(dòng)窗口壓縮”，該算法將一個(gè)虛擬的，可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長(zhǎng)度。43LZ77首先介紹算法中用到的幾個(gè)術(shù)語(yǔ)：輸入數(shù)據(jù)流(inputstream)：要被壓縮的字符序列。字符(character)：輸入數(shù)據(jù)流中的基本單元。編碼位置(codingposition)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開(kāi)始字符。前向緩沖存儲(chǔ)器(Lookaheadbuffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。窗口(window)：指包含W個(gè)字符的窗口，字符從編碼位置開(kāi)始向后數(shù)，也就是最后處理的字符數(shù)。指針(pointer)：指向窗口中的匹配串，一般含有長(zhǎng)度。AABCBBABCAW=5已編碼未編碼B=444圖例輸入數(shù)據(jù)流45LZ77算法核心LZ77編碼算法的核心：查找從前向緩沖存儲(chǔ)器開(kāi)始的最長(zhǎng)的匹配串。編碼算法的具體執(zhí)行步驟如下：把編碼位置設(shè)置到輸入數(shù)據(jù)流的開(kāi)始位置。查找窗口中最長(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例子位置123456789字符AABCBBABCCBABBCBAA編碼步驟編碼位置匹配串前向緩沖中第一個(gè)字符輸出(ptr,len)ch11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)CW=5,B=2每次移動(dòng)窗口和編碼位置Len+1Len=0Len=1Len=0Len=148LZ77的問(wèn)題LZ77通過(guò)輸出真實(shí)字符解決了在窗口中出現(xiàn)沒(méi)有匹配串的問(wèn)題，但這個(gè)解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個(gè)方面，一是空指針例如前一個(gè)例子中(0,0)C二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。49LZSS算法1982年由Storer和Szymanski改進(jìn)LZ77LZSS算法以比較有效的方法解決這個(gè)問(wèn)題，它的思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度長(zhǎng)就輸出指針，否則就輸出真實(shí)字符。由于輸出的壓縮數(shù)據(jù)流中包含有指針和字符本身，為了區(qū)分它們就需要有額外的標(biāo)志位，即ID位。50LZSS編碼算法步驟

把編碼位置置于輸入數(shù)據(jù)流的開(kāi)始位置。在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串

①Pointer：=匹配串指針。

②Length：=匹配串長(zhǎng)度。判斷匹配串長(zhǎng)度Length是否大于等于最小匹配串長(zhǎng)度(Length≥MIN_LENGTH)，

如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。

如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。如果前向緩沖存儲(chǔ)器不是空的，就返回到步驟251例子位置1234567891011字符AABBCBBAABC步驟位置匹配串輸出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC編碼過(guò)程(MIN_LENGTH=2，W=10,B=3)Len=1<252LZSS與LZ77比較在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。這也就是為什么這種算法成為開(kāi)發(fā)新算法的基礎(chǔ)，許多后來(lái)開(kāi)發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip,GZip,ARJ,LHArc和ZOO等等，其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同。LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。53LZ78原理LZ78的編碼思想是不斷地從字符流中提取新的字符串(String)，通俗地理解為新“詞條”，然后用“代號(hào)”也就是碼字(Codeword)表示這個(gè)“詞條”。這樣一來(lái)，對(duì)字符流的編碼就變成了用碼字(Codeword)去替換字符流(Charstream)，生成碼字流(Codestream)，從而達(dá)到壓縮數(shù)據(jù)的目的。54LZ77與LZ78比較LZ77利用滑動(dòng)窗口里的內(nèi)容作為字典，找最長(zhǎng)子串LZ78動(dòng)態(tài)構(gòu)建字典55LZ78編碼在編碼開(kāi)始時(shí)詞典是空的，不包含任何字符串(string)。在這種情況下編碼器就輸出一個(gè)表示空字符串的特殊碼字(例如“0”)和字符流中(Charstream)的第一個(gè)字符C，并把這個(gè)字符C添加到詞典中作為一個(gè)由一個(gè)字符組成的字符串(string)。在編碼過(guò)程中，如果出現(xiàn)類似沒(méi)有任何匹配的情況，也照此辦理。在詞典中已經(jīng)包含某些字符串(String)之后，如果“當(dāng)前前綴P+當(dāng)前字符C”已經(jīng)在詞典中，就用字符C來(lái)擴(kuò)展這個(gè)前綴，這樣的擴(kuò)展操作一直重復(fù)到獲得一個(gè)在詞典中沒(méi)有的字符串(String)為止。此時(shí)就輸出表示當(dāng)前前綴P的碼字(Codeword)和字符C，并把P+C添加到詞典中，然后開(kāi)始處理字符流(Charstream)中的下一個(gè)字符。56算法

在開(kāi)始時(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é)束編碼。57LZ78編碼輸出LZ78編碼器的輸出是碼字-字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的字符串(String)用字符C進(jìn)行擴(kuò)展生成新的字符串(String)，然后添加到詞典中。58例子位置123456789字符ABBCBCABA步驟位置當(dāng)前字符C當(dāng)前前綴P添加詞典輸出11A－，－A(0,A)22B－，－B(0,B)33BC－，BBC,－BC(2,C)45BCA－，BBCBCA，－BCA(3,A)58BA－，BBA，－BA(2,A)59LZ78與LZ77LZ78在每個(gè)編碼步驟中減少了string比較數(shù)目LZ77需要找最長(zhǎng)匹配子串壓縮率與LZ77類似。60LZWTerryA.Weltch在1984年發(fā)表了改進(jìn)LZ78的文章，因此把這種編碼方法稱為L(zhǎng)ZW(Lempel-ZivWalch)61LZW與LZ78編碼原理差別①LZW只輸出代表詞典中的字符串(String)的碼字(codeword)。這就意味在開(kāi)始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。②由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每個(gè)編碼步驟開(kāi)始時(shí)都使用一字符前綴(one-characterprefix)，因此至少可以在詞典中找到長(zhǎng)度為1的匹配串。62LZW的詞典LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來(lái)完成的。這張轉(zhuǎn)換表用來(lái)存放稱為前綴(Prefix)的字符序列，并且為每個(gè)表項(xiàng)分配一個(gè)碼字(Codeword)，或者叫做序號(hào)。Welch的論文中用了12位碼字，12位可以有4096個(gè)不同的12位代碼，這就是說(shuō)，轉(zhuǎn)換表有4096個(gè)表項(xiàng)，其中256個(gè)表項(xiàng)用來(lái)存放已定義的字符，剩下3840個(gè)表項(xiàng)用來(lái)存放前綴(Prefix)。63例子碼字(Codeword)前綴(Prefix)1

……193A194B……255

……1305abcdefxyF01234……64LZW編碼LZW編碼器就是通過(guò)管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換。LZW編碼器的輸入是字符流(Charstream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼字流(Codestream)，碼字代表單個(gè)字符或多個(gè)字符組成的字符串(String)。LZ78輸出是碼字+字符CBABBCBAA193…65貪婪分析算法LZW采用greedyparsingalgorithm每一次分析都要串行地檢查來(lái)自字符流(Charstream)的字符串，從中分解出已經(jīng)識(shí)別的最長(zhǎng)的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長(zhǎng)的前綴(Prefix)。用已知的前綴(Prefix)加上下一個(gè)輸入字符C也就是當(dāng)前字符(Currentcharacter)作為該前綴的擴(kuò)展字符，形成新的擴(kuò)展字符串。判斷新的串是否在詞典中是：繼續(xù)輸入C否：加入詞典，分配碼字66具體執(zhí)行步驟開(kāi)始時(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);674.判斷字符流中是否還有字符需要編碼(1)如果“是”，就返回到步驟2；(2)如果“否”①把代表當(dāng)前前綴P的碼字輸出到碼字流;②結(jié)束。注意：每個(gè)輸出的碼字對(duì)應(yīng)于詞典中的一個(gè)詞條，因?yàn)橹挥挟?dāng)出現(xiàn)新的字符串的時(shí)候才輸出碼字。68位置123456789字符ABBABABAC步驟位置詞典當(dāng)前字符C當(dāng)前前綴P輸出

(1)A

－

－

(2)B

－

－

(3)C

－

－

11(4)ABABAAB,B(1)22(5)BBBBB,B(2)33(6)BAABA,A(2)44(7)ABAB