第5講 多媒體數(shù)據(jù)壓縮-lfz_第1頁
第5講 多媒體數(shù)據(jù)壓縮-lfz_第2頁
第5講 多媒體數(shù)據(jù)壓縮-lfz_第3頁
第5講 多媒體數(shù)據(jù)壓縮-lfz_第4頁
第5講 多媒體數(shù)據(jù)壓縮-lfz_第5頁
已閱讀5頁,還剩66頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

2024年3月20日第2章數(shù)據(jù)無損壓縮1of42第4章數(shù)據(jù)壓縮與編碼4.1數(shù)據(jù)的冗余4.1.1冗余概念4.1.2決策量4.1.3信息量4.1.4熵4.1.5數(shù)據(jù)冗余量4.2統(tǒng)計編碼4.2.1香農-范諾編碼4.2.2霍夫曼編碼4.2.3算術編碼4.3RLE編碼4.4詞典編碼4.4.1詞典編碼的思想4.4.2LZ77算法4.4.3LZSS算法4.4.4LZ78算法4.4.5LZW算法參考文獻和站點2024年3月20日第2章數(shù)據(jù)無損壓縮2of424.0數(shù)據(jù)無損壓縮概述數(shù)據(jù)可被壓縮的依據(jù)數(shù)據(jù)本身存在冗余聽覺系統(tǒng)的敏感度有限視覺系統(tǒng)的敏感度有限三種多媒體數(shù)據(jù)類型文字(text)數(shù)據(jù)——無損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)聲音(audio)數(shù)據(jù)——有損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)根據(jù)人的聽覺系統(tǒng)特性(Basedonhumanhearingsystem)圖像(image)/視像(video)數(shù)據(jù)——有損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)根據(jù)人的視覺系統(tǒng)特性(Basedonhumanvisualsystem)

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

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA/news/2001/february/26/1.html信息論之父介紹2024年3月20日第2章數(shù)據(jù)無損壓縮5of424.0數(shù)據(jù)無損壓縮概述(續(xù)3)ClaudeShannon

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

H0=log(n)其中,n是事件數(shù)決策量的單位由對數(shù)的底數(shù)決定Sh(Shannon):用于以2為底的對數(shù)Nat(naturalunit):用于以e為底的對數(shù)Hart(hartley):用于以10為底的對數(shù)2024年3月20日第2章數(shù)據(jù)無損壓縮8of424.1數(shù)據(jù)的冗余(續(xù)2)信息量(informationcontent)具有確定概率事件的信息的定量度量在數(shù)學上定義為

其中,是事件出現(xiàn)的概率舉例:假設X={a,b,c}是由3個事件構成的集合,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一個等概率事件的集合,每個事件的信息量等于該集合的決策量2024年3月20日第2章數(shù)據(jù)無損壓縮9of424.1數(shù)據(jù)的冗余(續(xù)3)熵(entropy)按照香農(Shannon)的理論,在有限的互斥和聯(lián)合窮舉事件的集合中,熵為事件的信息量的平均值,也稱事件的平均信息量(meaninformationcontent)用數(shù)學表示為2024年3月20日第2章數(shù)據(jù)無損壓縮10of424.1數(shù)據(jù)的冗余(續(xù)4)數(shù)據(jù)的冗余量2024年3月20日第2章數(shù)據(jù)無損壓縮11of424.2統(tǒng)計編碼 統(tǒng)計編碼給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮方法編碼方法香農-范諾編碼霍夫曼編碼算術編碼編碼特性香農-范諾編碼和霍夫曼編碼的原理相同,都是根據(jù)符號集中各個符號出現(xiàn)的頻繁程度來編碼,出現(xiàn)次數(shù)越多的符號,給它分配的代碼位數(shù)越少算術編碼使用0和1之間的實數(shù)的間隔長度代表概率大小,概率越大間隔越長,編碼效率可接近于熵2024年3月20日第2章數(shù)據(jù)無損壓縮12of424.2.1統(tǒng)計編碼——香農-范諾編碼 香農-范諾編碼(Shannon–Fanocoding)在香農的源編碼理論中,熵的大小表示非冗余的不可壓縮的信息量在計算熵時,如果對數(shù)的底數(shù)用2,熵的單位就用“香農(Sh)”,也稱“位(bit)”?!拔弧笔?948年Shannon首次使用的術語。例如最早闡述和實現(xiàn)“從上到下”的熵編碼方法的人是Shannon(1948年)和Fano(1949年),因此稱為香農-范諾(Shannon-Fano)編碼法2024年3月20日第2章數(shù)據(jù)無損壓縮13of424.2.1香農-范諾編碼香農-范諾編碼舉例有一幅40個像素組成的灰度圖像,灰度共有5級,分別用符號A,B,C,D和E表示。40個像素中出現(xiàn)灰度A的像素數(shù)有15個,出現(xiàn)灰度B的像素數(shù)有7個,出現(xiàn)灰度C的像素數(shù)有7個,其余情況見表2-1(1)計算該圖像可能獲得的壓縮比的理論值(2)對5個符號進行編碼(3)計算該圖像可能獲得的壓縮比的實際值表2-1符號在圖像中出現(xiàn)的數(shù)目符號ABCDE出現(xiàn)的次數(shù)157765出現(xiàn)的概率15/407/407/406/405/402024年3月20日第2章數(shù)據(jù)無損壓縮14of424.2.1香農-范諾編碼(續(xù)1)(1)壓縮比的理論值按照常規(guī)的編碼方法,表示5個符號最少需要3位,如用000表示A,001表示B,…,100表示E,其余3個代碼(101,110,111)不用。這就意味每個像素用3位,編碼這幅圖像總共需要120位。按照香農理論,這幅圖像的熵為這個數(shù)值表明,每個符號不需要用3位構成的代碼表示,而用4.196位就可以,因此40個像素只需用87.84位就可以,因此在理論上,這幅圖像的的壓縮比為120:87.84≈1.37:1,實際上就是3:4.196≈1.372024年3月20日第2章數(shù)據(jù)無損壓縮15of424.2.1香農-范諾編碼(續(xù)2)(2)符號編碼對每個符號進行編碼時采用“從上到下”的方法。首先按照符號出現(xiàn)的頻度或概率排序,如A,B,C,D和E,見表2-2。然后使用遞歸方法分成兩個部分,每一部分具有近似相同的次數(shù),如圖2-1所示2024年3月20日第2章數(shù)據(jù)無損壓縮16of424.2.1香農-范諾編碼(續(xù)3)(3)壓縮比的實際值按照這種方法進行編碼需要的總位數(shù)為30+14+14+18+15=91,實際的壓縮比為120:91≈1.32:1圖2-1香農-范諾算法編碼舉例

2024年3月20日第2章數(shù)據(jù)無損壓縮17of424.2.2統(tǒng)計編碼——霍夫曼編碼 霍夫曼編碼(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“從下到上”的熵編碼方法根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多,其編碼的位數(shù)就越少廣泛用在JPEG,MPEG,H.26X等各種信息編碼標準中2024年3月20日第2章數(shù)據(jù)無損壓縮18of424.2.2霍夫曼編碼—CaseStudy1霍夫曼編碼舉例1現(xiàn)有一個由5個不同符號組成的30個符號的字符串:BABACACADADABBCBABEBEDDABEEEBB計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼前后的壓縮比2024年3月20日第2章數(shù)據(jù)無損壓縮19of424.2.2霍夫曼編碼—CaseStudy1(續(xù)1)符號出現(xiàn)的次數(shù)log2(1/pi)分配的代碼需要的位數(shù)B101.585?A81.907?C33.322?D44.907?E54.585?合計30符號出現(xiàn)的概率2024年3月20日第2章數(shù)據(jù)無損壓縮20of424.2.2霍夫曼編碼—CaseStudy1(續(xù)2)(1)計算該字符串的霍夫曼碼步驟①:按照符號出現(xiàn)概率大小的順序對符號進行排序步驟②:把概率最小的兩個符號組成一個節(jié)點P1步驟③:重復步驟②,得到節(jié)點P2,P3,P4,……,

PN,形成一棵樹,其中的PN稱為根節(jié)點步驟④:從根節(jié)點PN開始到每個符號的樹葉,從上到下

標上0(上枝)和1(下枝),至于哪個為1哪個為0則

無關緊要,但通常把概率大的標成1,概率小的

標成0步驟⑤:從根節(jié)點PN開始順著樹枝到每個葉子分別寫出

每個符號的代碼2024年3月20日第2章數(shù)據(jù)無損壓縮21of424.2.2霍夫曼編碼—CaseStudy1(續(xù)3)符號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)2024年3月20日第2章數(shù)據(jù)無損壓縮22of424.2.2霍夫曼編碼—CaseStudy1(續(xù)4)符號出現(xiàn)的次數(shù)log2(1/pi)分配的代碼需要的位數(shù)B101.5851120A81.9071016C33.3220109D44.90701112E54.5850010合計301.06730個字符組成的字符串需要67位5個符號的代碼2024年3月20日第2章數(shù)據(jù)無損壓縮23of424.2.2霍夫曼編碼—CaseStudy1(續(xù)5)

(2)計算該字符串的熵

其中,是事件的集合,

并滿足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=

4.1874(Sh)2024年3月20日第2章數(shù)據(jù)無損壓縮24of424.2.2霍夫曼編碼—CaseStudy1(續(xù)6)(3)

計算該字符串的平均碼長平均碼長:

=(2×8+2×10+3×3+3×4+2×5)/30

=4.233位/符號

壓縮比:90/67=1.34:1

平均碼長:67/30=4.233位(4)計算編碼前后的壓縮比編碼前:5個符號需3位,30個字符,需要90位編碼后:共67位2024年3月20日第2章數(shù)據(jù)無損壓縮25of424.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計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼效率2024年3月20日第2章數(shù)據(jù)無損壓縮26of424.2.2霍夫曼編碼—CaseStudy2(續(xù)1)2024年3月20日第2章數(shù)據(jù)無損壓縮27of424.2.2霍夫曼編碼—CaseStudy2(續(xù)2)Averagelengthpersymbol

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

(withHuffmancoding):(4)Efficiencyofthecode:2024年3月20日第2章數(shù)據(jù)無損壓縮28of424.2.3統(tǒng)計編碼——算術編碼 算術編碼(arithmeticcoding)給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮技術基本思想是用0和1之間的一個數(shù)值范圍表示輸入流中的一個字符,而不是給輸入流中的每個字符分別指定一個碼字實質上是為整個輸入字符流分配一個“碼字”,因此它的編碼效率可接近于熵2024年3月20日第2章數(shù)據(jù)無損壓縮29of424.2.3算術編碼舉例[例4.3](取自教材)假設信源符號為{00,01,10,11},它們的概率分別為{0.1,0.4,0.2,0.3}對二進制消息序列10001100101101…進行算術編碼2024年3月20日第2章數(shù)據(jù)無損壓縮30of424.2.3算術編碼舉例(續(xù)1)符號00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]表2-4例4.3的信源符號概率和初始編碼間隔

初始化根據(jù)信源符號的概率把間隔[0,1)分成如表2-4所示的4個子間隔:[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)。其中[x,y)的表示半開放間隔,即包含x不包含y,x稱為低邊界或左邊界,y稱為高邊界或右邊界2024年3月20日第2章數(shù)據(jù)無損壓縮31of424.2.3算術編碼舉例(續(xù)2)確定符號的編碼范圍編碼時輸入第1個符號是10,找到它的編碼范圍是[0.5,0.7]消息中第2個符號00的編碼范圍是[0,0.1),它的間隔就取[0.5,0.7)的第一個十分之一作為新間隔[0.5,0.52)編碼第3個符號11時,取新間隔為[0.514,0.52)編碼第4個符號00時,取新間隔為[0.514,0.5146)依此類推……消息的編碼輸出可以是最后一個間隔中的任意數(shù)整個編碼過程如圖2-3所示編碼和譯碼的全過程分別見表2-5和表2-62024年3月20日第2章數(shù)據(jù)無損壓縮32of424.2.3算術編碼舉例(續(xù)3)圖2-3例4.3的算術編碼過程2024年3月20日第2章數(shù)據(jù)無損壓縮33of424.2.3算術編碼舉例(續(xù)4)2024年3月20日第2章數(shù)據(jù)無損壓縮34of424.2.3算術編碼舉例(續(xù)5)2024年3月20日第2章數(shù)據(jù)無損壓縮35of424.3RLE編碼行程長度編碼(Run-LengthCoding)一種無損壓縮數(shù)據(jù)編碼技術,它利用重復的數(shù)據(jù)單元有相同的數(shù)值這一特點對數(shù)據(jù)進行壓縮。對相同的數(shù)值只編碼一次,同時計算出相同值重復出現(xiàn)的次數(shù)。在JPEG,MPEG,H.261和H.263等壓縮方法中,RLE用來對圖像數(shù)據(jù)變換和量化后的系數(shù)進行編碼例:假設有一幅灰度圖像第n行的像素值如圖2-5所示。用RLE編碼方法得到的代碼為:80315084180圖2-5RLE編碼概念2024年3月20日第2章數(shù)據(jù)無損壓縮36of424.3RLE編碼(續(xù))Assumption:Longsequencesofidenticalsymbols.Example,2024年3月20日第2章數(shù)據(jù)無損壓縮37of424.4詞典編碼詞典編碼(dictionarycoding)文本中的詞用它在詞典中表示位置的號碼代替的一種無損數(shù)據(jù)壓縮方法。采用靜態(tài)詞典編碼技術時,編碼器需要事先構造詞典,解碼器要事先知道詞典。采用動態(tài)辭典編碼技術時,編碼器將從被壓縮的文本中自動導出詞典,解碼器解碼時邊解碼邊構造解碼詞典兩種類型的編碼算法具體算法LZ77算法LZSS算法LZ78算法LZW算法2024年3月20日第2章數(shù)據(jù)無損壓縮38of424.4詞典編碼(續(xù)1)第一類編碼算法用已經出現(xiàn)過的字符串替代重復的部分編碼器的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”圖2-6第一類詞典編碼概念2024年3月20日第2章數(shù)據(jù)無損壓縮39of424.4詞典編碼(續(xù)2)第二類編碼算法從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典(dictionaryofthephrases)”編碼器輸出詞典中的短語“索引號”,而不是短語圖2-7第二類詞典編碼概念40LZ77算法第一類詞典編碼里:所指的“詞典”是指用以前處理過的數(shù)據(jù)來表示編碼過程中遇到的重復部分。這類編碼中的所有算法都是以AbrahamLempel和JakobZiv在1977年開發(fā)和發(fā)表的稱為LZ77算法為基礎的JacobZiv,AbrahamLempel,AUniversalAlgorithmforSequentialDataCompression,IEEETransactionsonInformationTheory,23(3):337-343,May1977.41LZ77算法LZ77算法在某種意義上又可以稱為“滑動窗口壓縮”,該算法將一個虛擬的,可以跟隨壓縮進程滑動的窗口作為詞典,要壓縮的字符串如果在該窗口中出現(xiàn),則輸出其出現(xiàn)位置和長度。42LZ77首先介紹算法中用到的幾個術語:輸入數(shù)據(jù)流(inputstream):要被壓縮的字符序列。字符(character):輸入數(shù)據(jù)流中的基本單元。編碼位置(codingposition):輸入數(shù)據(jù)流中當前要編碼的字符位置,指前向緩沖存儲器中的開始字符。前向緩沖存儲器(Lookaheadbuffer):存放從編碼位置到輸入數(shù)據(jù)流結束的字符序列的存儲器。窗口(window):指包含W個字符的窗口,字符從編碼位置開始向后數(shù),也就是最后處理的字符數(shù)。指針(pointer):指向窗口中的匹配串,一般含有長度。AABCBBABCAW=5已編碼未編碼B=443圖例輸入數(shù)據(jù)流44LZ77算法核心LZ77編碼算法的核心:查找從前向緩沖存儲器開始的最長的匹配串。編碼算法的具體執(zhí)行步驟如下:把編碼位置設置到輸入數(shù)據(jù)流的開始位置。查找窗口中最長的匹配串。以“(Pointer,Length)Characters”的格式輸出,其中Pointer是指向窗口中匹配串的指針,Length表示匹配字符的長度,Characters是前向緩沖存儲器中的不匹配的第1個字符。如果前向緩沖存儲器不是空的,則把編碼位置和窗口向前移(Length+1)個字符,然后返回到步驟2。45指針表示(Pointer,Length)Characters表示匹配的(字符位置,長度)下一個不匹配的字符指針可以以“(Back_chars,Chars_length)Explicit_character”格式輸出。其中,(Back_chars,Chars_length)是指向匹配串的指針,告訴譯碼器“在這個窗口中向后退Back_chars個字符然后拷貝Chars_length個字符到輸出”,Explicit_character是真實字符。46例子位置123456789字符AABCBBABCCBABBCBAA編碼步驟編碼位置匹配串前向緩沖中第一個字符輸出(ptr,len)ch11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)CW=5,B=2每次移動窗口和編碼位置Len+1Len=0Len=1Len=0Len=147LZ77的問題LZ77通過輸出真實字符解決了在窗口中出現(xiàn)沒有匹配串的問題,但這個解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個方面,一是空指針例如前一個例子中(0,0)C二是編碼器可能輸出額外的字符,這種字符是指可能包含在下一個匹配串中的字符。48LZSS算法1982年由Storer和Szymanski改進LZ77LZSS算法以比較有效的方法解決這個問題,它的思想是如果匹配串的長度比指針本身的長度長就輸出指針,否則就輸出真實字符。由于輸出的壓縮數(shù)據(jù)流中包含有指針和字符本身,為了區(qū)分它們就需要有額外的標志位,即ID位。49LZSS編碼算法步驟

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

①Pointer:=匹配串指針。

②Length:=匹配串長度。判斷匹配串長度Length是否大于等于最小匹配串長度(Length≥MIN_LENGTH),

如果“是”:輸出指針,然后把編碼位置向前移動Length個字符。

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

在開始時,詞典和當前前綴P都是空的。當前字符C:=字符流中的下一個字符。判斷P+C是否在詞典中:(1)如果“是”:用C擴展P,讓P:=P+C;(2)如果“否”:①輸出與當前前綴P相對應的碼字和當前字符C;②把字符串P+C添加到詞典中。③令P:=空值。(3)判斷字符流中是否還有字符需要編碼①如果“是”:返回到步驟2。②如果“否”:若當前前綴P不是空的,輸出相應于當前前綴P的碼字,然后結束編碼。56LZ78編碼輸出LZ78編碼器的輸出是碼字-字符(W,C)對,每次輸出一對到碼字流中,與碼字W相對應的字符串(String)用字符C進行擴展生成新的字符串(String),然后添加到詞典中。57例子位置123456789字符ABBCBCABA步驟位置當前字符C當前前綴P添加詞典輸出11A-,-A(0,A)22B-,-B(0,B)33BC-,BBC,-BC(2,C)45BCA-,BBCBCA,-BCA(3,A)58BA-,BBA,-BA(2,A)58LZ78與LZ77LZ78在每個編碼步驟中減少了string比較數(shù)目LZ77需要找最長匹配子串壓縮率與LZ77類似。59LZWTerryA.Weltch在1984年發(fā)表了改進LZ78的文章,因此把這種編碼方法稱為LZW(Lempel-ZivWalch)60LZW與LZ78編碼原理差別①LZW只輸出代表詞典中的字符串(String)的碼字(codeword)。這就意味在開始時詞典不能是空的,它必須包含可能在字符流出現(xiàn)中的所有單個字符,即前綴根(Root)。②由于所有可能出現(xiàn)的單個字符都事先包含在詞典中,每個編碼步驟開始時都使用一字符前綴(one-characterprefix),因此至少可以在詞典中找到長度為1的匹配串。61LZW的詞典LZW編碼是圍繞稱為詞典的轉換表來完成的。這張轉換表用來存放稱為前綴(Prefix)的字符序列,并且為每個表項分配一個碼字(Codeword),或者叫做序號。Welch的論文中用了12位碼字,12位可以有4096個不同的12位代碼,這就是說,轉換表有4096個表項,其中256個表項用來存放已定義的字符,剩下3840個表項用來存放前綴(Prefix)。62例子碼字(Codeword)前綴(Prefix)1

……193A194B……255

……1305abcdefxyF01234……63LZW編碼LZW編碼器就是通過管理這個詞典完成輸入與輸出之間的轉換。LZW編碼器的輸入是字符流(Charstream),字符流可以是用8位ASCII字符組成的字符串,而輸出是用n位(例如12位)表示的碼字流(Codestream),碼字代表單個字符或多個字符組成的字符串(String)。LZ78輸出是碼字+字符CBABBCBAA193…64貪婪分析算法LZW采用greedyparsingalgorithm每一次分析都要串行地檢查來自字符流(Charstream)的字符串,從中分解出已經識別的最長的字符串,也就是已經在詞典中出現(xiàn)的最長的前綴(Prefix)。用已知的前綴(Prefix)加上下一個輸入字符C也就是當前字符(Currentcharacter)作為該前綴的擴展字符,形成新的擴展字符串。判斷新的串是否在詞典中是:繼續(xù)輸入C否:加入詞典,分配碼字65具體執(zhí)行步驟開始時詞典包含所有可能的根(Root),當前前綴P是空的;當前字符(C):=字符流中的下一個字符;判斷綴-符串P+C是否在詞典中如果“是”:P:=P+C//(用C擴展P);如果“否”①把代表當前前綴P的碼字輸出到碼字流;②把綴-符串P+C添加到詞典;③令P:=C//(現(xiàn)在的P僅包含一個字符C);664.判斷字符流中是否還有字符需要編碼(1)如果“是”,就返回到步驟2;(2)如果“否”①把代表當前前綴P的碼字輸出到碼字流;②結束。注意:每個輸出的碼字對應于詞典中的一個詞條,因為只有當出現(xiàn)新的字符串的時候才輸出碼字。67位置123456789字符ABBABABAC步驟位置詞典當前字符C當前前綴P輸出

(1)A

(2)B

(3)C

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論