ch數(shù)據(jù)無損壓縮演示文稿

ch數(shù)據(jù)無損壓縮演示文稿當(dāng)前1頁，總共40頁。優(yōu)選ch數(shù)據(jù)無損壓縮當(dāng)前2頁，總共40頁。第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.3RLE編碼2.4詞典編碼2.4.1詞典編碼的思想2.4.2LZ77算法2.4.3LZSS算法2.4.4LZ78算法2.4.5LZW算法參考文獻(xiàn)和站點(diǎn)當(dāng)前3頁，總共40頁。2.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)

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

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA信息論之父介紹當(dāng)前6頁，總共40頁。2.1數(shù)據(jù)的冗余冗余概念人為冗余在信息處理系統(tǒng)中，使用兩臺計(jì)算機(jī)做同樣的工作是提高系統(tǒng)可靠性的一種措施—此種冗余乃有意為之在數(shù)據(jù)存儲和傳輸中，為了檢測和恢復(fù)在數(shù)據(jù)存儲或數(shù)據(jù)傳輸過程中出現(xiàn)的錯(cuò)誤，根據(jù)使用的算法的要求，在數(shù)據(jù)存儲或數(shù)據(jù)傳輸之前把額外的數(shù)據(jù)添加到用戶數(shù)據(jù)中，這個(gè)額外的數(shù)據(jù)就是冗余數(shù)據(jù)—比如數(shù)字簽名、水印等等視聽冗余由于人的視覺系統(tǒng)和聽覺系統(tǒng)的局限性，在圖像數(shù)據(jù)和聲音數(shù)據(jù)中，有些數(shù)據(jù)確實(shí)是多余的，使用算法將其去掉后并不會丟失實(shí)質(zhì)性的信息或含義，對理解數(shù)據(jù)表達(dá)的信息幾乎沒有影響數(shù)據(jù)冗余不考慮數(shù)據(jù)來源時(shí)，單純數(shù)據(jù)集中也可能存在多余的數(shù)據(jù)，去掉這些多余數(shù)據(jù)并不會丟失任何信息，這種冗余稱為數(shù)據(jù)冗余，而且還可定量表達(dá)當(dāng)前7頁，總共40頁。2.1數(shù)據(jù)的冗余(續(xù)1)決策量(decisioncontent)在有限數(shù)目的互斥事件集合中，決策量是事件數(shù)的對數(shù)值在數(shù)學(xué)上表示為

H0=log(n)

其中，n是事件數(shù)決策量的單位由對數(shù)的底數(shù)決定Sh(Shannon):用于以2為底的對數(shù)Nat(naturalunit):用于以e為底的對數(shù)Hart(hartley)：用于以10為底的對數(shù)當(dāng)前8頁，總共40頁。2.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è)事件的信息量等于該集合的決策量當(dāng)前9頁，總共40頁。2.1數(shù)據(jù)的冗余(續(xù)3)熵(entropy)按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量的平均值，也稱事件的平均信息量(meaninformationcontent)用數(shù)學(xué)表示為當(dāng)前10頁，總共40頁。2.1數(shù)據(jù)的冗余(續(xù)4)數(shù)據(jù)的冗余量當(dāng)前11頁，總共40頁。2.2統(tǒng)計(jì)編碼 統(tǒng)計(jì)編碼給已知統(tǒng)計(jì)信息的符號分配代碼的數(shù)據(jù)無損壓縮方法編碼方法香農(nóng)-范諾編碼霍夫曼編碼算術(shù)編碼編碼特性香農(nóng)-范諾編碼和霍夫曼編碼的原理相同，都是根據(jù)符號集中各個(gè)符號出現(xiàn)的頻繁程度來編碼，出現(xiàn)次數(shù)越多的符號，給它分配的代碼位數(shù)越少算術(shù)編碼使用0和1之間的實(shí)數(shù)的間隔長度代表概率大小，概率越大間隔越長，編碼效率可接近于熵當(dāng)前12頁，總共40頁。2.2.1統(tǒng)計(jì)編碼——香農(nóng)-范諾編碼 香農(nóng)-范諾編碼(Shannon–Fanocoding)在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量在計(jì)算熵時(shí)，如果對數(shù)的底數(shù)用2，熵的單位就用“香農(nóng)(Sh)”，也稱“位(bit)”

?！拔弧笔?948年Shannon首次使用的術(shù)語。例如最早闡述和實(shí)現(xiàn)“從上到下”的熵編碼方法的人是Shannon(1948年)和Fano(1949年)，因此稱為香農(nóng)-范諾(Shannon-Fano)編碼法當(dāng)前13頁，總共40頁。2.2.1香農(nóng)-范諾編碼香農(nóng)-范諾編碼舉例有一幅40個(gè)像素組成的灰度圖像，灰度共有5級，分別用符號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)對5個(gè)符號進(jìn)行編碼(3)計(jì)算該圖像可能獲得的壓縮比的實(shí)際值表2-1符號在圖像中出現(xiàn)的數(shù)目符號ABCDE出現(xiàn)的次數(shù)157765出現(xiàn)的概率15/407/407/406/405/40當(dāng)前14頁，總共40頁。2.2.1香農(nóng)-范諾編碼(續(xù)1)(1)壓縮比的理論值按照常規(guī)的編碼方法，表示5個(gè)符號最少需要3位，如用000表示A，001表示B，…，100表示E，其余3個(gè)代碼(101，110，111)不用。這就意味每個(gè)像素用3位，編碼這幅圖像總共需要120位。按照香農(nóng)理論，這幅圖像的熵為這個(gè)數(shù)值表明，每個(gè)符號不需要用3位構(gòu)成的代碼表示，而用2.196位就可以，因此40個(gè)像素只需用87.84位就可以，因此在理論上，這幅圖像的的壓縮比為120:87.84≈1.37:1，實(shí)際上就是3:2.196≈1.37當(dāng)前15頁，總共40頁。2.2.1香農(nóng)-范諾編碼(續(xù)2)(2)符號編碼對每個(gè)符號進(jìn)行編碼時(shí)采用“從上到下”的方法。首先按照符號出現(xiàn)的頻度或概率排序，如A，B，C，D和E，見表2-2。然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)，如圖2-1所示當(dāng)前16頁，總共40頁。2.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)-范諾算法編碼舉例

當(dāng)前17頁，總共40頁。2.2.2統(tǒng)計(jì)編碼——霍夫曼編碼 霍夫曼編碼(Huffmancoding)霍夫曼(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)中當(dāng)前18頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy1霍夫曼編碼舉例1現(xiàn)有一個(gè)由5個(gè)不同符號組成的30個(gè)符號的字符串：BABACACADADABBCBABEBEDDABEEEBB計(jì)算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼前后的壓縮比當(dāng)前19頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy1(續(xù)1)符號出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.585?A81.907?C33.322?D42.907?E52.585?合計(jì)30符號出現(xiàn)的概率當(dāng)前20頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy1(續(xù)2)(1)計(jì)算該字符串的霍夫曼碼步驟①：按照符號出現(xiàn)概率大小的順序?qū)Ψ栠M(jìn)行排序步驟②：把概率最小的兩個(gè)符號組成一個(gè)節(jié)點(diǎn)P1步驟③：重復(fù)步驟②，得到節(jié)點(diǎn)P2，P3，P4，……，

PN，形成一棵樹，其中的PN稱為根節(jié)點(diǎn)步驟④：從根節(jié)點(diǎn)PN開始到每個(gè)符號的樹葉，從上到下

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

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

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

每個(gè)符號的代碼當(dāng)前21頁，總共40頁。2.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)當(dāng)前22頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy1(續(xù)4)符號出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合計(jì)301.06730個(gè)字符組成的字符串需要67位5個(gè)符號的代碼當(dāng)前23頁，總共40頁。2.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)當(dāng)前24頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy1(續(xù)6)(3)

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

＝(2×8＋2×10＋3×3＋3×4＋2×5)/30

＝2.233位/符號

壓縮比:90/67=1.34:1

平均碼長：67/30=2.233位(4)計(jì)算編碼前后的壓縮比編碼前：5個(gè)符號需3位，30個(gè)字符，需要90位編碼后：共67位當(dāng)前25頁，總共40頁。2.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)該字符串的平均碼長(4)編碼效率當(dāng)前26頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy2(續(xù)2)Averagelengthpersymbol

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

(withHuffmancoding):(4)Efficiencyofthecode:當(dāng)前27頁，總共40頁。2.2.3統(tǒng)計(jì)編碼——算術(shù)編碼 算術(shù)編碼(arithmeticcoding)給已知統(tǒng)計(jì)信息的符號分配代碼的數(shù)據(jù)無損壓縮技術(shù)算術(shù)編碼是把一個(gè)信源表示為實(shí)軸上0和1之間的一個(gè)區(qū)間，信源集合中的每一個(gè)元素都用來縮短這個(gè)區(qū)間。實(shí)質(zhì)上是為整個(gè)輸入字符流分配一個(gè)“碼字”，因此它的編碼效率可接近于熵當(dāng)前28頁，總共40頁。2.2.3算術(shù)編碼舉例[例2.3]假設(shè)信源符號為{00,01,10,11}，它們的概率分別為{0.1,0.4,0.2,0.3}對二進(jìn)制消息序列10001100101101…進(jìn)行算術(shù)編碼當(dāng)前29頁，總共40頁。2.2.3算術(shù)編碼舉例(續(xù)1)符號00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]表2-4例2.3的信源符號概率和初始編碼間隔

初始化根據(jù)信源符號的概率把間隔[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稱為高邊界或右邊界當(dāng)前30頁，總共40頁。2.2.3算術(shù)編碼舉例(續(xù)2)確定符號的編碼范圍編碼時(shí)輸入第1個(gè)符號是10，找到它的編碼范圍是[0.5,0.7]消息中第2個(gè)符號00的編碼范圍是[0,0.1)，它的間隔就取[0.5,0.7)的第一個(gè)十分之一作為新間隔[0.5,0.52)編碼第3個(gè)符號11時(shí)，取新間隔為[0.514,0.52)編碼第4個(gè)符號00時(shí)，取新間隔為[0.514,0.5146)依此類推……消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)整個(gè)編碼過程如圖2-3所示編碼和譯碼的全過程分別見表2-5和表2-6當(dāng)前31頁，總共40頁。2.2.3算術(shù)編碼舉例(續(xù)3)圖2-3例2.3的算術(shù)編碼過程當(dāng)前32頁，總共40頁。2.2.3算術(shù)編碼舉例(續(xù)4)當(dāng)前33頁，總共40頁。2.2.3算術(shù)編碼舉例(續(xù)5)當(dāng)前34頁，總共40頁。算術(shù)編碼的特點(diǎn)①不必預(yù)先定義概率模型,自適應(yīng)模式具有獨(dú)特的優(yōu)點(diǎn);

②信源符號概率接近時(shí),建議使用算術(shù)編碼

,這種情況下其效率高于Huffman編碼;

當(dāng)前35頁，總共40頁。算術(shù)編碼特點(diǎn)續(xù)③算術(shù)編碼繞過了用一個(gè)特定的代碼替代一個(gè)輸入符號的想法,用一個(gè)浮點(diǎn)輸出數(shù)值代替一個(gè)流的輸入符號,較長的復(fù)雜的消息輸出的數(shù)值中就需要更多的位數(shù)。④算術(shù)編碼實(shí)現(xiàn)方法復(fù)雜一些,但