信息論基礎(chǔ)-數(shù)據(jù)壓縮

1、第3章 數(shù)據(jù)壓縮和信源編碼最優(yōu)碼的實際構(gòu)造！1數(shù)據(jù)壓縮 “數(shù)據(jù)壓縮”在漢英詞典中的解釋： data compression (A method of reducing the amount of memory required to store data by encoding it and minimizing redundancy. Compressed data takes less time to transmit, but more computation time to restore it to its original form when needed for processi

2、ng.)2數(shù)據(jù)壓縮-作用 通俗地說，就是用最少的數(shù)碼來表示信號。其作用是：能較快地傳輸各種信號，如傳真、Modem通信等；在現(xiàn)有的通信干線并行開通更多的多媒體業(yè)務(wù)，如各種增值業(yè)務(wù)；緊縮數(shù)據(jù)存儲容量，如CDROM、VCD和DVD等；降低發(fā)信機功率，這對于多媒體移動通信系統(tǒng)尤為重要。由此看來，通信時間、傳輸帶寬、存儲空間甚至發(fā)射能量，都可能成為數(shù)據(jù)壓縮的對象。 3數(shù)據(jù)壓縮-目的 一、可以節(jié)省空間。 二、可以減少對帶寬的占用。 JPEG壓縮編碼技術(shù)的基本原理 ：JPEG專家組開發(fā)了兩種基本的壓縮算法，一種是采用以離散余弦變換（DCT-DiscreteCosine Transform）為基礎(chǔ)的有損壓縮

3、算法，另一種是以空間線性預(yù)測技術(shù)（DPCM）為基礎(chǔ)的無損壓縮算法?，F(xiàn)在應(yīng)用得較多的是有損壓縮算法。JPEG標(biāo)準(zhǔn)只處理單幀圖像，而不必顧及到前后左右?guī)瑢⒚繋瑘D像作為基礎(chǔ)進(jìn)行處理，利用了空間壓縮編碼原理。4數(shù)據(jù)壓縮-目的 一、可以節(jié)省空間。 二、可以減少對帶寬的占用。 MPEG編碼技術(shù)的基本原理 ：MPEG數(shù)字視頻編碼技術(shù)實質(zhì)上是一種統(tǒng)計方法。在時間和空間方向上，視頻列通常包含統(tǒng)計冗余度。MPEG壓縮技術(shù)所依賴的 基本統(tǒng)計特性為像素之間(interpel)的相關(guān)性，這里包含這樣一個設(shè)想：即在各連續(xù)幀之間存在簡單的相關(guān)性平移運動。5數(shù)據(jù)壓縮-類型 有損壓縮和無損壓縮（圖片格式 ） 有損壓縮 有損壓

4、縮可以減少圖像在內(nèi)存和磁盤中占用的空間，在屏幕上觀看圖像時，不會發(fā)現(xiàn)它對圖像的外觀產(chǎn)生太大的不利影響。因為人的眼睛對光線比較敏感，光線對景物的作用比顏色的作用更為重要，這就是有損壓縮技術(shù)的基本依據(jù)。 有損壓縮的特點是保持顏色的逐漸變化，刪除圖像中顏色的突然變化。生物學(xué)中的大量實驗證明，人類大腦會利用與附近最接近的顏色來填補所丟失的顏色。 6數(shù)據(jù)壓縮-類型 有損壓縮和無損壓縮（圖片格式 ） 有損壓縮 例如，對于藍(lán)色天空背景上的一朵白云，有損壓縮的方法就是刪除圖像中景物邊緣的某些顏色部分。當(dāng)在屏幕上看這幅圖時，大腦會利用在景物上看到的顏色填補所丟失的顏色部分。利用有損壓縮技術(shù)，某些數(shù)據(jù)被有意地刪除

5、了，而被取消的數(shù)據(jù)也不再恢復(fù)。 無可否認(rèn)，利用有損壓縮技術(shù)可以大大地壓縮文件的數(shù)據(jù)，但是會影響圖像質(zhì)量。如果使用了有損壓縮的圖像僅在屏幕上顯示，可能對圖像質(zhì)量影響不太大，至少對于人類眼睛的識別程度來說區(qū)別不大?？墒牵绻岩环?jīng)過有損壓縮技術(shù)處理的圖像用高分辨率打印機打印出來，那么圖像質(zhì)量就會有明顯的受損痕跡。 7數(shù)據(jù)壓縮-類型 有損壓縮和無損壓縮（圖片格式 ） 無損壓縮 無損壓縮的基本原理是相同的顏色信息只需保存一次。壓縮圖像的軟件首先會確定圖像中哪些區(qū)域是相同的，哪些是不同的。包括了重復(fù)數(shù)據(jù)的圖像(如藍(lán)天)就可以被壓縮，只有藍(lán)天的起始點和終結(jié)點需要被記錄下來。但是藍(lán)色可能還會有不同的深淺

6、，天空有時也可能被樹木、山峰或其他的對象掩蓋，這些就需要另外記錄。從本質(zhì)上看，無損壓縮的方法可以刪除一些重復(fù)數(shù)據(jù)，大大減少要在磁盤上保存的圖像尺寸。 8數(shù)據(jù)壓縮-類型 有損壓縮和無損壓縮（圖片格式 ） 無損壓縮 但是，無損壓縮的方法并不能減少圖像的內(nèi)存占用量，這是因為，當(dāng)從磁盤上讀取圖像時，軟件又會把丟失的像素用適當(dāng)?shù)念伾畔⑻畛溥M(jìn)來。如果要減少圖像占用內(nèi)存的容量，就必須使用有損壓縮方法。 無損壓縮方法的優(yōu)點是能夠比較好地保存圖像的質(zhì)量，但是相對來說這種方法的壓縮率比較低。但是，如果需要把圖像用高分辨率的打印機打印出來，最好還是使用無損壓縮幾乎所有的圖像文件都采用各自簡化的格式名作為文件擴(kuò)展名

7、。從擴(kuò)展名就可知道這幅圖像是按什么格式存儲的，應(yīng)該用什么樣的軟件去讀寫等等。 9數(shù)據(jù)壓縮-概要 在計算機科學(xué)和信息論中，數(shù)據(jù)壓縮或者信源編碼是按照特定的編碼機制用比未經(jīng)編碼少的數(shù)據(jù)位元（或者其它信息相關(guān)的單位）表示信息的過程。例如，如果我們將“compression”編碼為“comp”那么這篇文章可以用較少的數(shù)據(jù)位表示。一種流行的壓縮實例是許多計算機都在使用的ZIP 文件格式，它不僅僅提供了壓縮的功能，而且還作為歸檔工具Archiver）使用，能夠?qū)⒃S多文件存儲到同一個文件中。10數(shù)據(jù)壓縮-概要 對于任何形式的通信來說，只有當(dāng)信息的發(fā)送方和接受方都能夠理解編碼機制的時候壓縮數(shù)據(jù)通信才能夠工作。

8、例如，只有當(dāng)接受方知道這篇文章需要用英語字符解釋的時候這篇文章才有意義。同樣，只有當(dāng)接受方知道編碼方法的時候他才能夠理解壓縮數(shù)據(jù)。一些壓縮算法利用了這個特性，在壓縮過程中對數(shù)據(jù)進(jìn)行加密，例如利用密碼加密，以保證只有得到授權(quán)的一方才能正確地得到數(shù)據(jù)。11數(shù)據(jù)壓縮-概要 數(shù)據(jù)壓縮能夠?qū)崿F(xiàn)是因為多數(shù)現(xiàn)實世界的數(shù)據(jù)都有統(tǒng)計冗余。例如，字母“e”在英語中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。無損壓縮算法通常利用利用了統(tǒng)計冗余，這樣就能更加簡練地、但仍然是完整地表示發(fā)送方的數(shù)據(jù)。 如果允許一定程度的保真度損失，那么還可以實現(xiàn)進(jìn)一步的壓縮。例如，人們看圖畫或者電視畫面的時候可能并不會注

9、意到一些細(xì)節(jié)并不完善。同樣，兩個音頻錄音采樣序列可能聽起來一樣，但實際上并不完全一樣。有損壓縮算法在帶來微小差別的情況下使用較少的位數(shù)表示圖像、視頻或者音頻。12數(shù)據(jù)壓縮-概要 由于可以幫助減少如硬盤空間與連接帶寬這樣的昂貴資源的消耗，所以壓縮非常重要，然而壓縮需要消耗信息處理資源，這也可能是費用昂貴的。所以數(shù)據(jù)壓縮機制的設(shè)計需要在壓縮能力、失真度、所需計算資源以及其它需要考慮的不同因素之間進(jìn)行折衷。 一些機制是可逆的，這樣就可以恢復(fù)原始的數(shù)據(jù)，這種機制稱為無損數(shù)據(jù)壓縮；另外一些機制為了實現(xiàn)更高的壓縮率允許一定程度的數(shù)據(jù)損失，這種機制稱為有損數(shù)據(jù)壓縮。13數(shù)據(jù)壓縮-概要 然而，經(jīng)常有一些文件不

10、能被無損數(shù)據(jù)壓縮算法壓縮，實際上對于不含可以辨別樣式的數(shù)據(jù)任何壓縮算法都不能壓縮。試圖壓縮已經(jīng)經(jīng)過壓縮的數(shù)據(jù)通常得到的結(jié)果實際上是擴(kuò)展數(shù)據(jù)，試圖壓縮經(jīng)過加密的數(shù)據(jù)通常也會得到這種結(jié)果。 實際上，有損數(shù)據(jù)壓縮也會最終達(dá)到不能工作的地步。我們來舉一個極端的例子，壓縮算法每次去掉文件最后一個字節(jié)，那么經(jīng)過這個算法不斷的壓縮直至文件變空，壓縮算法將不能繼續(xù)工作。14數(shù)據(jù)壓縮-應(yīng)用 一種非常簡單的壓縮方法是行程長度編碼，這種方法使用數(shù)據(jù)及數(shù)據(jù)長度這樣簡單的編碼代替同樣的連續(xù)數(shù)據(jù)，這是無損數(shù)據(jù)壓縮的一個實例。這種方法經(jīng)常用于辦公計算機以更好地利用磁盤空間、或者更好地利用計算機網(wǎng)絡(luò)中的帶寬。對于電子表格、文

11、本、可執(zhí)行文件等這樣的符號數(shù)據(jù)來說，無損是一個非常關(guān)鍵的要求，因為除了一些有限的情況，大多數(shù)情況下即使是一個數(shù)據(jù)位的變化都是無法接受的。15數(shù)據(jù)壓縮-應(yīng)用 對于視頻和音頻數(shù)據(jù)，只要不損失數(shù)據(jù)的重要部分一定程度的質(zhì)量下降是可以接受的。通過利用人類感知系統(tǒng)的局限，能夠大幅度得節(jié)約存儲空間并且得到的結(jié)果質(zhì)量與原始數(shù)據(jù)質(zhì)量相比并沒有明顯的差別。這些有損數(shù)據(jù)壓縮方法通常需要在壓縮速度、壓縮數(shù)據(jù)大小以及質(zhì)量損失這三者之間進(jìn)行折衷。 有損圖像壓縮用于數(shù)碼相機中，大幅度地提高了存儲能力，同時圖像質(zhì)量幾乎沒有降低。用于DVD的有損MPEG-2編解碼視頻壓縮也實現(xiàn)了類似的功能。16數(shù)據(jù)壓縮-應(yīng)用 在有損音頻壓縮中

12、，心理聲學(xué)的方法用來去除信號中聽不見或者很難聽見的成分。人類語音的壓縮經(jīng)常使用更加專業(yè)的技術(shù)，因此人們有時也將“語音壓縮”或者“語音編碼”作為一個獨立的研究領(lǐng)域與“音頻壓縮”區(qū)分開來。不同的音頻和語音壓縮標(biāo)準(zhǔn)都屬于音頻編解碼范疇。例如語音壓縮用于因特網(wǎng)電話，而音頻壓縮被用于CD翻錄并且使用 MP3 播放器解碼。17數(shù)據(jù)壓縮-理論 壓縮的理論基礎(chǔ)是信息論（它與算法信息論密切相關(guān)）以及率失真理論，這個領(lǐng)域的研究工作主要是由 Claude Shannon 奠定的，他在二十世紀(jì)四十年代末期及五十年代早期發(fā)表了這方面的基礎(chǔ)性的論文。Doyle 和 Carlson 在2000年寫道數(shù)據(jù)壓縮“是所有的工程領(lǐng)

13、域最簡單、最優(yōu)美的設(shè)計理論之一”。密碼學(xué)與編碼理論也是密切相關(guān)的學(xué)科，數(shù)據(jù)壓縮的思想與統(tǒng)計推斷也有很深的淵源。18數(shù)據(jù)壓縮-理論 許多無損數(shù)據(jù)壓縮系統(tǒng)都可以看作是四步模型，有損數(shù)據(jù)壓縮系統(tǒng)通常包含更多的步驟，例如它包括預(yù)測、頻率變換以及量化。Lempel-Ziv（LZ）壓縮方法是最流行的無損存儲算法之一。DEFLATE是 LZ 的一個變體，它針對解壓速度與壓縮率進(jìn)行了優(yōu)化，雖然它的壓縮速度可能非常緩慢，PKZIP、gzip 以及 PNG 都在使用EFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的專利，直到2003年6月專利到期限，這種方法用于 GIF 圖像。 19數(shù)

14、據(jù)壓縮-理論 另外值得一提的是 LZR (LZ-Renau) 方法，它是 Zip 方法的基礎(chǔ)。LZ R方法使用基于表格的壓縮模型，其中表格中的條目用重復(fù)的數(shù)據(jù)串替換。對于大多數(shù)的 LZ 方法來說，這個表格是從最初的輸入數(shù)據(jù)動態(tài)生成的。這個表格經(jīng)常采用霍夫曼編碼維護(hù)（例如，SHRI、LZX）。 目前一個性能良好基于 LZ 的編碼機制是 LZX，它用于微軟公司的 CAB 格式。20數(shù)據(jù)壓縮-理論 最好的壓縮工具將概率模型預(yù)測結(jié)果用于算術(shù)編碼。算術(shù)編碼由 Jorma Rissanen 發(fā)明，并且由 Witten、Neal 以及 Cleary 將它轉(zhuǎn)變成一個實用的方法。這種方法能夠?qū)崿F(xiàn)比眾人皆知的哈夫

15、曼算法更好的壓縮，并且它本身非常適合于自適應(yīng)數(shù)據(jù)壓縮，自適應(yīng)數(shù)據(jù)壓縮的預(yù)測與上下文密切相關(guān)。算術(shù)編碼已經(jīng)用于二值圖像壓縮標(biāo)準(zhǔn) JBIG、文檔壓縮標(biāo)準(zhǔn) DejaVu。文本 輸入系統(tǒng) Dasher 是一個逆算術(shù)編碼器。有效輸入信息文本的界面 21數(shù)據(jù)壓縮和信源編碼3.1 等長碼 3.2 變長編碼 3.3 哈夫曼碼 3.4 算術(shù)碼 香農(nóng)-費諾碼3.5 通用信源編碼 LZW算法習(xí)題三 22數(shù)據(jù)壓縮和信源編碼信源編碼定理（定理2.4.1）設(shè)X1，X2為無記憶信源，服從共同分布p(x) ，則 當(dāng)碼率 時，存在碼率為R的編碼，使得當(dāng)n時，誤差碼率Pe0.最優(yōu)碼的存在性23數(shù)據(jù)壓縮和信源編碼將信道編碼和譯碼看

16、成是信道的一部分，而突出信源編碼；24數(shù)據(jù)壓縮和信源編碼通過信源編碼，用盡可能少的信道符號來表達(dá)信源，即對信源數(shù)據(jù)用最有效的表達(dá)方式表達(dá)，盡可能減少編碼后的數(shù)據(jù)的剩余度；25數(shù)據(jù)壓縮和信源編碼3.1 等長碼 3.2 變長編碼 3.3 哈夫曼碼 3.4 算術(shù)碼 香農(nóng)-費諾碼3.5 通用信源編碼 LZW算法習(xí)題三 26等長碼定義： 設(shè)為信源字母表，=0,1,D-1為D進(jìn)碼元（碼符號）集. 映射f : nk (x1 , xn)(u1 , uk) 等長編碼；若k不唯一，則為變長編碼. 映射： k n稱為相應(yīng)的譯碼； 稱上述編碼為D元碼.分組碼27等長碼定義（續(xù)）： f(xn)=uk稱為碼字，k為碼長；

17、 R=k/nlogD稱為f的編碼速率，即碼率； 由f編出的所有碼字的集合稱為碼字集： C=f(xn), xn n 若任一碼字只能被唯一譯成所對應(yīng)的信源符號序列，稱這類編碼為唯一可譯碼.又稱信源的信息率-信源編碼后平均每個碼元載荷的最大信息量28等長碼1. 若進(jìn)行二元等長編碼，則碼字長至少為2；從而： 熵H(X) =1.75; 碼率R=k/nlogD=2H(X).29等長碼2. 若進(jìn)行二元不等長編碼. 變長編碼的平均碼長：L=p(i)l(i)=1.75; 熵H(X) =1.75; 碼率R=L/nlogD=H(X).30數(shù)據(jù)壓縮和信源編碼3.1 等長碼 3.2 變長編碼 3.3 哈夫曼碼 3.4

18、算術(shù)碼 香農(nóng)-費諾碼3.5 通用信源編碼 LZW算法習(xí)題三 31變長編碼該編碼的平均碼長L=1.5=R H(X);是否說明該碼更加實用呢？考查：對收到的碼字序列001001譯碼？32變長編碼必須要求編碼是唯一可譯的；這是變長碼編碼要滿足的第一個要求！ 對于所編出的變長碼，怎樣才能說明它是否是唯一可譯的？33變長編碼定義： 前綴若一個碼字與另一個碼字的前面部分相同，則稱其為另一碼字的前綴； 0，01；01，01134變長編碼定義： 前綴若一個碼字與另一個碼字的前面部分相同，則稱其為另一碼字的前綴； 0，01；01，01135變長編碼定義： 前綴若一個碼字與另一個碼字的前面部分相同，則稱其為另一碼

19、字的前綴； 0，01； 01，011 其中，較長碼的剩余部分稱為較短碼的 尾隨后綴.36變長編碼如何確定一個變長編碼的所有尾隨后綴？ 步驟：考查碼C中最短碼字是否是其它碼字的前綴若是，列出所有的尾隨后綴，再考查這 些尾隨后綴是否是其它碼字的前綴；若不是，考查次長的碼字.37變長編碼哪些碼是否為唯一可譯碼？若是請說明；否則，請構(gòu)造一個有二義的碼字序列.判定：尾隨后綴集中沒有碼字！38變長編碼定義:若f 編出的碼字集中，沒有一個碼字是其它碼字的前綴，則稱f 編出的碼為即時碼.即時碼一定是唯一可譯碼，反之不然！39作業(yè)P75 3) 以及課堂練習(xí).40 變長編碼碼樹圖即時碼的樹圖構(gòu)造法：給每個節(jié)點伸出

20、的樹枝從上向下標(biāo)上碼符號 0，1，而只對終結(jié)點安排碼字：從根出發(fā)到終結(jié)點走過的路徑所對應(yīng)的碼符號組成；中間節(jié)點不安排碼字.41 0001100101110111110變長編碼0000001111111碼樹圖42用樹的概念可導(dǎo)出即時碼存在的條件，即各碼字的長度li應(yīng)符合克萊夫特不等式：定理3.2.1 克萊夫特（Kraft，1949）不等式含m個碼字，碼長為 l1 , l2 , , lm的D進(jìn)碼是一個即時碼，則它滿足Kraft不等式 反之，存在給定碼長的即時碼； 變長編碼該不等式對唯一可譯碼成立！43變長編碼的平均碼長：若信源 ，編碼后的碼子為 ，碼長分別為 ，則平均碼長為： 變長編碼它是傳輸信源

21、符號平均需用的碼元數(shù)！編碼效率-衡量各種編碼的優(yōu)劣44變長信源編碼問題就是 求使得給定信源平均碼長最小的唯一可譯的變長碼.注意：Kraft不等式是一個存在定理，不是唯一可譯碼的判定定理. 存在長度滿足Kraft不等式的碼不是即時碼：變長編碼最優(yōu)碼！45例1：考慮二元碼C=0,11,100,110，|D|=2.可以驗證其碼字長度1，2，3，3滿足Kraft不等式；但不是即時碼，因為它不是唯一可譯碼.變長編碼46如何用Kraft不等式的證明過程構(gòu)造即時碼.例2.令U=0,1,2,且 l1=l2=1，l3=2，l4=l5=4，l6=5. 可以證明他們滿足Kraft不等式； 能夠構(gòu)造U上具有對應(yīng)碼字長

22、度的即時 碼：變長編碼47由li的取值得到：(a1 , a2 , a3 , a4 , a5)=(2,1,0,2,1);任取a1個長度為1的碼元：0，1；任取a2個長度為2，并且不以已經(jīng)出現(xiàn)的碼字為 前綴的碼元：20；任取a4個長度為4，的碼元：2100，2101；任取a5個長度為5，的碼元：21020.變長編碼是即時碼48在有些編碼選擇中，我們會面臨一些最優(yōu)選擇的問題。比如下面這樣的問題：我們要編碼字符串“7F1234567AB”，使得編碼結(jié)果序列最短?？墒褂玫木幋a方案已給定，有兩種選擇： 每個數(shù)字或字符對應(yīng)一個定長碼，比如1-1001100 ，F(xiàn)-1010100

23、 每兩個連續(xù)數(shù)字可以對應(yīng)一個定長碼。比如12-1001100，23-1101100 注意，給定的編碼方案里，上面兩種情況下定長碼均等長(例子中為長度為7)。這里，我們看到，如果要編碼結(jié)果序列最短。就需要盡量多的使用第二個方案。變長編碼49這里有兩種極限情況： 比如ABECDDDEFG.FHE這樣的字串只能按第一種方案進(jìn)行,因為它沒有連續(xù)數(shù)字出現(xiàn). 比如1234235345.32這樣的字串,如果有偶數(shù)個數(shù)字的話,我們完全可以按第二種方案進(jìn)行. 那么既有字符,又有數(shù)字的情況,就有一個選擇的問題, 所以這里的問題就是我們?nèi)绾巫R別可以使用第二個方案的字串。 變長編碼50/user1/1946/arch

24、ives/2006/31023.html作者 fineamy 變長編碼51變長信源編碼問題就是 求使得給定信源平均碼長最小的唯一可譯的變長碼.但是滿足Kraft不等式的碼長集未必是最優(yōu)的，即其平均碼長未必是最小的！變長編碼52定理3.2.2（最優(yōu)碼碼長的下界估計）：隨機變量X的任何D進(jìn)即時碼的平均碼長L應(yīng)滿足， 變長編碼等號成立的充要條件53證明：記如果C是即時碼，則根據(jù)Kraft不等式，有變長編碼54定義3.2.3 相對冗余度作業(yè)：P75 1)變長編碼55定理3.2.2（最優(yōu)碼碼長的下界估計）：隨機變量X的任何D進(jìn)即時碼的平均碼長L應(yīng)滿足， 變長編碼等號成立的充要條件對于出現(xiàn)概率大的信息符號

25、，編以短字長的碼,對于出現(xiàn)概率小的信息符號編以長字長的碼，如果碼字長度嚴(yán)格按照符號概率的大小的相反順序排列，則平均碼字長一定小于按任何其他符號順序排列方式得到的碼字長度。56某地的 A 同學(xué) 要給另外一方 B 同學(xué) 傳遞信息,信息必須以二進(jìn)制編碼 ( 即01編碼 ) 的方式傳遞.假設(shè) A 傳遞給 B 的所有字符只有 a,b,c,d 四個,且不包含空格.一種顯而易見的編碼方法是: a-00; b-01; c-10; d-11;這樣保證不會產(chǎn)生翻譯錯誤的情況發(fā)生,而平均每個字符需要 2 個 Bit 的帶寬.然而這種方法不是最優(yōu)的 ; 借助統(tǒng)計規(guī)律, 就可以構(gòu)造出保證不會產(chǎn)生錯誤,然而卻能更省帶寬的

26、編碼方式:變長編碼57給出一個例子:假設(shè) P(x=a)=1/2; P(x=b)=1/4; P(x=c)=1/8; P(x=d)=1/8;即對大量的信息作出統(tǒng)計后 , 發(fā)現(xiàn) a 出現(xiàn)的頻率最高,平均每兩個字符中就出現(xiàn)一個 a; b 其次; c,d再次之.如此對a的編碼進(jìn)行 縮水 處理: a-1; b-01; c-001; d-000;這樣仍然能保證不會譯錯, 而且,平均每個字符需要 1*1/2+2*1/4+3*1/8+3*1/8=7/4 = 1.75 Bit這樣就節(jié)省了寶貴的 0.25 Bit上述的編碼方式稱為 Huffman 編碼變長編碼58數(shù)據(jù)壓縮和信源編碼3.1 等長碼 3.2 變長編碼

27、3.3 哈夫曼碼 3.4 算術(shù)碼 香農(nóng)-費諾碼3.5 通用信源編碼 LZW算法習(xí)題三 59數(shù)據(jù)壓縮和信源編碼 哈夫曼編碼/譯碼器。設(shè)計一個哈夫曼編碼/譯碼器程序，對一個文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件（壓縮文件，后綴.cod）；反過來，可將一個壓縮文件譯碼還原為一個文本文件(.txt)。 http:/camel520duck/blog/item/57295c163366af4c21a4e97a.html 60數(shù)據(jù)壓縮和信源編碼 步驟： （1）輸入一個待壓縮的文本文件名，統(tǒng)計文本文件中各字符的個數(shù)作為權(quán)值，生成哈夫曼樹； （2）將文本文件利用哈夫曼樹進(jìn)行編碼，生成壓縮文件（后綴名co

28、d） （3）輸入一個待解壓的壓縮文件名稱,并利用相應(yīng)的哈夫曼樹將編碼序列譯碼； （4）顯示指定的壓縮文件和文本文件的內(nèi)容。 61數(shù)據(jù)壓縮和信源編碼哈夫曼編碼(Huffman Coding)是可變長編碼(VLC)的一種。 Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼 在計算機信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱熵編碼法），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的

29、字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。 62數(shù)據(jù)壓縮和信源編碼 例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。 當(dāng)利用哈夫曼編碼對一篇英文進(jìn)行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均占用一個字節(jié)（byte），即8個位。 二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現(xiàn)對于英文中各個字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。 63數(shù)據(jù)壓縮和信源編碼 哈夫曼壓縮是個無損的壓縮算法，一般

30、用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。 /camel520duck/blog/item/57295c163366af4c21a4e97a.html 作者：著述的鴨子非了 壓縮1M數(shù)據(jù)少于100ms（P3處理器，主頻1G）。64一、二進(jìn)制哈夫曼編碼1.步驟(1) 信源符號按概率分布大小，以遞減次序排列； (2) 取兩個最小的概率，分別賦以“0”,“1”;然后把這兩個概率值相加，作為新概率值與其他概率重新排序(3) 按重排

31、概率值，重復(fù)(2), 直到概率和達(dá)到1為止(4) 由后向前排列碼序，即得哈夫曼編碼哈夫曼（Huffman）碼652. 例題 x1 0.4 x2 0.2 x3 0.2 x4 0.1 x5 0.1平均碼長碼方差12=E(li-L)2=p(xi) (li-L)2 =1.31.001010101X:p(x)(0.4,0.2,0.2,0.1,0.1)（合并后概率下放）哈夫曼（Huffman）碼0110000010001166方法一：合并后的新符號排在其它相同概率符號的后面；哈夫曼（Huffman）碼67 3. 上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4

32、0.1011 x5 0.101.0010101（合并后概率上放）哈夫曼（Huffman）碼68 3. 上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均碼長 結(jié)論 碼方差22 = 0.16 兩法平均碼長相同，故信息率R、冗余度相同；但碼方差不同，碼方差小要好.01.0010101（合并后概率上放）哈夫曼（Huffman）碼69方法二：合并后的新符號排在其它相同概率符號的前面.哈夫曼（Huffman）碼70兩種編碼的平均碼長是一樣的，都是2.2，那一種更好呢，我們可以計算一下平均碼長的方差。定義碼字長

33、度的方差2：哈夫曼（Huffman）碼71可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。第一種方法編出的5個碼字有4種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；顯然，第二種編碼方法更簡單、更容易實現(xiàn)，所以更好。結(jié)論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。哈夫曼（Huffman）碼72 3. 上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均碼長 結(jié)論 碼

34、方差22 = 0.16 兩法平均碼長相同，故信息率R、冗余度相同；但碼方差不同，碼方差小要好.01.0010101（合并后概率上放）哈夫曼（Huffman）碼73定理：在變長編碼中，若各碼字長度嚴(yán)格按照所對應(yīng)符號出現(xiàn)概率的大小逆序排列，則其平均長度為最小。結(jié)論：霍夫曼編碼方法，它完全依據(jù)字符出現(xiàn)概率來構(gòu)造平均長度最短的異字頭碼字，有時稱之為最佳編碼。 哈夫曼（Huffman）碼74 應(yīng)該指出的是，由霍夫曼編碼過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能。此外，由于碼長不等，還存在一個輸入與輸出的速率匹配問題。解決的辦法是設(shè)置一定容量的緩沖

35、寄存器。而隨著微電子與計算技術(shù)的發(fā)展，霍夫曼編碼已可做成單片IC，并成為許多國際標(biāo)準(zhǔn)中的主要技術(shù)內(nèi)核之一。能夠用較低的處理代價，來換取昂貴的通信開銷，是完全值得的。哈夫曼（Huffman）碼方差最小者最佳75 應(yīng)該指出的是，由霍夫曼編碼過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能。此外，由于碼長不等，還存在一個輸入與輸出的速率匹配問題。解決的辦法是設(shè)置一定容量的緩沖寄存器。而隨著微電子與計算技術(shù)的發(fā)展，霍夫曼編碼已可做成單片IC，并成為許多國際標(biāo)準(zhǔn)中的主要技術(shù)內(nèi)核之一。能夠用較低的處理代價，來換取昂貴的通信開銷，是完全值得的。哈夫曼（Huffman）碼方差最

36、小者最佳760.60010.030.371.00101010101010100 x5 0.070101 x6 0.0600010 x7 0.0500011 x8 0.04011 x3 0.10000 x4 0.1001 x2 0.18 1 x1 0.4010010110101010000000001000011哈夫曼（Huffman）碼4.例題X:p(x)(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04)77二、D進(jìn)制哈夫曼編碼1. 編碼步驟同二進(jìn)制，但需注意兩點：每次取最小的D個概率,分別賦以0,1, D-1；信源符號個數(shù)r必須滿足：r=(

37、D-1)+D. 當(dāng)r不滿足時，在信源符號集中補充一些對應(yīng)概率為0的符號.哈夫曼（Huffman）碼78 2.例題某離散無記憶信源符號集a1,a2,a3,a4,a5,a6,a7,a8，已知所對應(yīng)的概率，試對其進(jìn)行四元編碼！ 哈夫曼（Huffman）碼有誤！79解：其中D=4. 若取=2可得大于9但與9最接近的正整數(shù)10，因此在編碼是加入一個零概率符號.對其進(jìn)行四元編碼： 哈夫曼（Huffman）碼80 哈夫曼（Huffman）碼81哈夫曼碼考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮；哈夫曼碼的編碼方法都不惟一；哈夫曼碼對信源的統(tǒng)計特性沒

38、有特殊要求，編碼效率比較高，因此綜合性較優(yōu).哈夫曼（Huffman）碼82Huffman碼在具體實用時，設(shè)備較復(fù)雜.在編碼器中需要增加緩沖寄存器，因為每個信源符號所對應(yīng)的碼符號長度不一，負(fù)責(zé)會造成輸入和輸出不能保持平衡.優(yōu)點：提高編碼效率；缺點：需要大量緩沖設(shè)備來存儲這些變長碼，然后再以恒定的碼率進(jìn)行傳送；在傳輸?shù)倪^程中如果出現(xiàn)了誤碼，容易引起錯誤擴(kuò)散，所以要求有優(yōu)質(zhì)的信道。哈夫曼（Huffman）碼83作業(yè)： P 76 8)哈夫曼（Huffman）碼84哈夫曼碼為設(shè)計最優(yōu)的唯一可譯變長碼提供了一種有效的方法！對單義代碼有：定理不是說單義代碼的平均碼長L不能大于上限，只是說小于上限的單義代碼總

39、是存在的?，F(xiàn)在考慮信息論中的一個更好的上限：哈夫曼（Huffman）碼85定理 (信源編碼的基本定理).設(shè): A一a1 , a1 ,. , am; XKX = x1, x2, . , xn的延長; WKW=W1,W2,.,Wn的延長，其平均長度為l; P(wi)一P(xi)，P(W)一IIP(Wi)，i=1，,n;如果要求WK為單義代碼，則，也叫做無失真編碼的基本定理。它說明:如果我們把X延長后再對K元組(K為延長長度)進(jìn)行編碼，那么不必利用數(shù)據(jù)前后的關(guān)聯(lián)，只要K足夠大，則代表每消息單元X的平均符號個數(shù)l/K可以任意趨于下限。哈夫曼（Huffman）碼86它說明:如果我們把X延長后再對K元組(

40、K為延長長度)進(jìn)行編碼，那么不必利用數(shù)據(jù)前后的關(guān)聯(lián)，只要K足夠大，則代表每消息單元X的平均符號個數(shù)l/K可以任意趨于下限。有了最佳編碼方法，我們就可以舉一個簡單例子來說明L/K趨于下限的情況：哈夫曼（Huffman）碼87【例】只有兩種灰度的傳真機，其輸出信號非“白”即“黑”，故可令 X=x1.x2=白，黑至于它們的概率P(x1),P(x2)則視所傳內(nèi)容而定。假設(shè)對于某頁文件，有P(x1)=0. 9，P(x2)=0. 3則當(dāng)不考慮信號間的關(guān)聯(lián)時，可求出該信源的一階熵即編碼下限為H(x)=一0. 9 log 0. 9一0. 1 log0. 1=0.469 (bit/pel)哈夫曼（Huffman）碼88此時W=0,1，無論采用定長編