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

ch數(shù)據(jù)無損壓縮演示文稿當前1頁，總共40頁。優(yōu)選ch數(shù)據(jù)無損壓縮當前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)計編碼2.2.1香農(nóng)-范諾編碼2.2.2霍夫曼編碼2.2.3算術編碼2.3RLE編碼2.4詞典編碼2.4.1詞典編碼的思想2.4.2LZ77算法2.4.3LZSS算法2.4.4LZ78算法2.4.5LZW算法參考文獻和站點當前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)

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

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA信息論之父介紹當前6頁，總共40頁。2.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ù)—比如數(shù)字簽名、水印等等視聽冗余由于人的視覺系統(tǒng)和聽覺系統(tǒng)的局限性，在圖像數(shù)據(jù)和聲音數(shù)據(jù)中，有些數(shù)據(jù)確實是多余的，使用算法將其去掉后并不會丟失實質(zhì)性的信息或含義，對理解數(shù)據(jù)表達的信息幾乎沒有影響數(shù)據(jù)冗余不考慮數(shù)據(jù)來源時，單純數(shù)據(jù)集中也可能存在多余的數(shù)據(jù)，去掉這些多余數(shù)據(jù)并不會丟失任何信息，這種冗余稱為數(shù)據(jù)冗余，而且還可定量表達當前7頁，總共40頁。2.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ù)當前8頁，總共40頁。2.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一個等概率事件的集合，每個事件的信息量等于該集合的決策量當前9頁，總共40頁。2.1數(shù)據(jù)的冗余(續(xù)3)熵(entropy)按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量的平均值，也稱事件的平均信息量(meaninformationcontent)用數(shù)學表示為當前10頁，總共40頁。2.1數(shù)據(jù)的冗余(續(xù)4)數(shù)據(jù)的冗余量當前11頁，總共40頁。2.2統(tǒng)計編碼 統(tǒng)計編碼給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮方法編碼方法香農(nóng)-范諾編碼霍夫曼編碼算術編碼編碼特性香農(nóng)-范諾編碼和霍夫曼編碼的原理相同，都是根據(jù)符號集中各個符號出現(xiàn)的頻繁程度來編碼，出現(xiàn)次數(shù)越多的符號，給它分配的代碼位數(shù)越少算術編碼使用0和1之間的實數(shù)的間隔長度代表概率大小，概率越大間隔越長，編碼效率可接近于熵當前12頁，總共40頁。2.2.1統(tǒng)計編碼——香農(nóng)-范諾編碼 香農(nóng)-范諾編碼(Shannon–Fanocoding)在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量在計算熵時，如果對數(shù)的底數(shù)用2，熵的單位就用“香農(nóng)(Sh)”，也稱“位(bit)”

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

當前17頁，總共40頁。2.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等各種信息編碼標準中當前18頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy1霍夫曼編碼舉例1現(xiàn)有一個由5個不同符號組成的30個符號的字符串：BABACACADADABBCBABEBEDDABEEEBB計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼前后的壓縮比當前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?合計30符號出現(xiàn)的概率當前20頁，總共40頁。2.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開始順著樹枝到每個葉子分別寫出

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

2.1874(Sh)當前24頁，總共40頁。2.2.2霍夫曼編碼—CaseStudy1(續(xù)6)(3)

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

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

＝2.233位/符號

壓縮比:90/67=1.34:1

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

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

(withHuffmancoding):(4)Efficiencyofthecode:當前27頁，總共40頁。2.2.3統(tǒng)計編碼——算術編碼 算術編碼(arithmeticcoding)給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮技術算術編碼是把一個信源表示為實軸上0和1之間的一個區(qū)間，信源集合中的每一個元素都用來縮短這個區(qū)間。實質(zhì)上是為整個輸入字符流分配一個“碼字”，因此它的編碼效率可接近于熵當前28頁，總共40頁。2.2.3算術編碼舉例[例2.3]假設信源符號為{00,01,10,11}，它們的概率分別為{0.1,0.4,0.2,0.3}對二進制消息序列10001100101101…進行算術編碼當前29頁，總共40頁。2.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例2.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稱為高邊界或右邊界當前30頁，總共40頁。2.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-6當前31頁，總共40頁。2.2.3算術編碼舉例(續(xù)3)圖2-3例2.3的算術編碼過程當前32頁，總共40頁。2.2.3算術編碼舉例(續(xù)4)當前33頁，總共40頁。2.2.3算術編碼舉例(續(xù)5)當前34頁，總共40頁。算術編碼的特點①不必預先定義概率模型,自適應模式具有獨特的優(yōu)點;

②信源符號概率接近時,建議使用算術編碼

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

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