統(tǒng)計(jì)編碼(2015)

1、1 1壓縮編碼技術(shù)壓縮編碼技術(shù) 2數(shù)據(jù)壓縮的類型可逆的無(wú)失真編碼可逆的無(wú)失真編碼不可逆的有失真編碼不可逆的有失真編碼不允許在壓縮過(guò)程中丟失信息。利用消息或消息序列出現(xiàn)概不允許在壓縮過(guò)程中丟失信息。利用消息或消息序列出現(xiàn)概率的分布特性，注重尋找概率與碼字長(zhǎng)度間的最優(yōu)匹配。率的分布特性，注重尋找概率與碼字長(zhǎng)度間的最優(yōu)匹配。語(yǔ)音、圖像或其他物理過(guò)程的量化采樣。語(yǔ)音、圖像或其他物理過(guò)程的量化采樣。本章討論的內(nèi)容3對(duì)于計(jì)算機(jī)文件對(duì)于計(jì)算機(jī)文件邏輯壓縮邏輯壓縮(Logical Compression)物理壓縮物理壓縮(Physical Compression)由數(shù)據(jù)自身特點(diǎn)及設(shè)計(jì)者技巧來(lái)決定的由數(shù)據(jù)自身特

2、點(diǎn)及設(shè)計(jì)者技巧來(lái)決定的 “壓縮表示壓縮表示法法”，這種技巧在數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中特別有效。，這種技巧在數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中特別有效。減少計(jì)算機(jī)文件內(nèi)部冗余度的統(tǒng)計(jì)編碼方法。減少計(jì)算機(jī)文件內(nèi)部冗余度的統(tǒng)計(jì)編碼方法。本章討論的內(nèi)容44.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計(jì)編碼方法統(tǒng)計(jì)編碼方法54.1 4.1 統(tǒng)計(jì)編碼方法的基本原理統(tǒng)計(jì)編碼方法的基本原理文件的冗余度類型文件的冗余度類型編碼器的數(shù)學(xué)描述編碼器的數(shù)學(xué)描述變長(zhǎng)碼的基本分析變長(zhǎng)碼的基本分析唯一可譯碼的存在唯一可譯碼的存在6計(jì)算機(jī)文件字

3、符集合(如文本);二進(jìn)制符號(hào)集合(如數(shù)據(jù));壓縮必須壓縮必須“透明透明”，恢復(fù)后的文件不允許有任何失真。，恢復(fù)后的文件不允許有任何失真。7 文件的冗余度類型文件的冗余度類型冗余度，專指對(duì)數(shù)據(jù)解釋一無(wú)所知時(shí)由數(shù)據(jù)流中即可觀察到的，與具體應(yīng)用背景無(wú)關(guān)。了解文件的冗余度，意在考慮有針對(duì)性的編碼方法。了解文件的冗余度，意在考慮有針對(duì)性的編碼方法。8冗余類型冗余類型 字符分布字符分布(Character Distribution) 字符重復(fù)字符重復(fù)(Character Repetition)在典型的字符串中，某些符號(hào)要比其他符號(hào)出現(xiàn)的更頻繁，在一份具體的文件中字符不會(huì)以等概率出現(xiàn)，字符的分布明顯地因文件

4、而異，影響到字符的統(tǒng)計(jì)特性。對(duì)于字符重復(fù)所形成的符號(hào)串常常有更緊湊的編碼方式，例如：格式化文件中的空白、報(bào)表中的空格串和零串、業(yè)務(wù)圖表中的線圖包含成片的空白等。 字符分布字符分布(Character Distribution) 字符重復(fù)字符重復(fù)(Character Repetition)9 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy)這四類冗余度之間有重疊這四類冗余度之間有重疊某些符號(hào)序列會(huì)以較高的頻率反復(fù)出現(xiàn)，可用較少的位數(shù)表示，從而得到時(shí)間和空間的凈節(jié)約。若某些字符總是在各數(shù)據(jù)塊中可預(yù)見(jiàn)的位置上出現(xiàn)，那么

5、這些字符至少是部分冗余的 ，例如：光柵掃描圖像中含有的豎線、報(bào)表文件中的某些字段的記錄幾乎總是相同的等等。 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Posit

6、ional Redundancy) 高使用率模式高使用率模式(High-usage Patterns)10一份零件報(bào)表中的冗余度的類型零件名: HEX NUT 1/4 20說(shuō) 明: STEEL, STANDARD THREAD顏色碼:倉(cāng) 庫(kù): 45th STREET貨 位: 4R9存貨量: 0020再進(jìn)貨量:0010文字長(zhǎng)度可變,字母分布不同;空字段同樣的名字在文件中多次出現(xiàn);數(shù)值字段, 有限的字符變化;11u 編碼器的數(shù)學(xué)描述編碼器的數(shù)學(xué)描述 4.1 4.1 統(tǒng)計(jì)編碼方法的基本原理統(tǒng)計(jì)編碼方法的基本原理 消息集X：元素 x 叫做信號(hào)單元或消息； 輸出集W (代碼、碼組或碼書(shū))：元素 w叫做碼

7、字； 碼字的符號(hào)集A：元素 a 叫做碼元或者符號(hào)； 以符號(hào) A 構(gòu)建代碼 W ; 建立 XW 對(duì)應(yīng)關(guān)系;12例例4-1X =x1, x2 , x3, A =0, 1, W =w1, w2, w3A2 =00, 01, 10, 11假設(shè)用構(gòu)成代碼構(gòu)成代碼W , W 到到 A2 的映射關(guān)系為的映射關(guān)系為 (完成步驟完成步驟):R1 = (w1,01), (w2,10), (w3,11)R2 =(x1 ,w1), (x2 ,w2), (x3 ,w3)建立建立X 與與 W 的映射關(guān)系為的映射關(guān)系為 (完成步驟完成步驟):若若xi(dk,dk+1, 1in, 0kJ-1, 為一模擬信號(hào)為一模擬信號(hào), ,

8、 該該編碼器實(shí)際就是一個(gè)量化器。編碼器實(shí)際就是一個(gè)量化器。編碼就是信息集編碼就是信息集X 到到 碼字集碼字集W 的一個(gè)映射的一個(gè)映射建立建立X 與與 W 的映射關(guān)系為的映射關(guān)系為 (完成步驟完成步驟):13編碼，就是將不同的消息用 不同的碼字來(lái)代替，或稱為從消息集到碼字集的一種映射(分組編碼或塊碼的概念)。 碼長(zhǎng): 組成碼字的符號(hào)個(gè)數(shù), Li=2, 1i3, 等長(zhǎng)(或定長(zhǎng))編碼: 采用相同長(zhǎng)度的不同碼字去 代表一個(gè)消息集合中的不同消息; M元編碼(或M進(jìn)制):取M個(gè)不同字符來(lái)組成碼字, 最常用的有二元編碼(或二進(jìn)制)。 14 變長(zhǎng)碼的基本分析變長(zhǎng)碼的基本分析對(duì)一個(gè)消息集合中的不同消息，采用不同

9、長(zhǎng)度的碼字表示。不等長(zhǎng)(或變長(zhǎng))編碼：采用變長(zhǎng)碼可以提高編碼效率，即對(duì)相同的信息量所需的平均編碼長(zhǎng)度可以短一些。151()njjjlP aL平均碼長(zhǎng)：對(duì)對(duì)P(aj)大的大的aj 用短碼用短碼;對(duì)對(duì)P(aj)小的小的aj 用長(zhǎng)碼用長(zhǎng)碼; 當(dāng)這些信息符號(hào)互不相關(guān)時(shí)當(dāng)這些信息符號(hào)互不相關(guān)時(shí),平均碼長(zhǎng)比等長(zhǎng)編碼的碼長(zhǎng)短平均碼長(zhǎng)比等長(zhǎng)編碼的碼長(zhǎng)短161843年，莫爾斯電報(bào)碼年，莫爾斯電報(bào)碼字母莫爾斯碼鉛字?jǐn)?shù)E12000T9000A 8000I 8000N 8000O 8000S 8000H 6400R 6200D 4400L 4000U 3400C 3000字母莫爾斯碼鉛字?jǐn)?shù)M 3000F 2500W

10、2000Y 2000G 1700P 1700B 1600V 1200K 800Q 500J 400X 400Z 200表4.1莫爾斯碼17莫爾斯碼的形成莫爾斯碼的形成: 首先找到各消息符號(hào)的統(tǒng)計(jì)特性: 再根據(jù)各符號(hào)出現(xiàn)的概率分布分 配不同長(zhǎng)度的碼字:變長(zhǎng)碼在編碼時(shí)要預(yù)先知道各種信息符號(hào)出現(xiàn)的概率,解碼也遠(yuǎn)比等長(zhǎng)碼復(fù)雜:正確識(shí)別碼字起點(diǎn)不容易;存在唯一可譯性問(wèn)題;譯碼實(shí)時(shí)性問(wèn)題;勻速輸入輸出匹配的緩存問(wèn)題; 18定義定義 4-1若W 中任一有限長(zhǎng)的碼字序列(即有限長(zhǎng)的一串W) ,可唯一地分割成一個(gè)一個(gè)碼字,稱為單義可譯或唯一可譯的,W 也叫做單義代碼。單義可譯碼（唯一可譯碼）單義可譯碼（唯一可譯

11、碼）19例例4-2考慮以下幾種變長(zhǎng)碼：信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111 碼A不是一一對(duì)應(yīng) ; 碼B是一一對(duì)應(yīng)，但構(gòu)成的序列不能被唯一分割;01110(0,1,1,1,0) (0,1,11,0) (0,11,1,0) (0,111,0)20100111011010(10, 0, 111, 0, 110, 10) 碼C是唯一可譯的;信源字母碼B碼C碼Da1a2a3a401111110101101110010110111 碼D是在碼B各碼字(除了w1)之前加一

12、個(gè)碼元“0”, 成為唯一可譯的, 但平均碼長(zhǎng)增加0.5bit;21 碼F 即使從尾開(kāi)始判斷, 也不是唯一可譯的;信源字母碼E碼Fa1a2a3a4001011111010101111101111010(10, 111, 10, 10)(101, 111, 0, 10)問(wèn)題: 什么樣的碼才是唯一可譯的? 碼E的譯碼要求等到收到全部序列, 才能從尾開(kāi)始進(jìn)行判決, 產(chǎn)生了時(shí)間上延時(shí)和存儲(chǔ)容量的增加;0111111 111(a1 1111) (a2111) ( a311)22 唯一可譯碼的存在唯一可譯碼的存在定理 4.1(Kraft不等式)長(zhǎng)度為L(zhǎng)1, L2, Ln 的 m 進(jìn)制唯一可譯碼存在的充分必要

13、條件是:含義：要求 Li 比較大(碼長(zhǎng)不能過(guò)短)，意味著碼字可能的組合數(shù)多,不為別的碼字的字首。11niLim(4.1-1)目前還沒(méi)有一個(gè)明確的判斷唯一可譯碼的準(zhǔn)則, 只有一個(gè)判斷不是唯一可譯碼的準(zhǔn)則。含義：要求 Li 比較大(碼長(zhǎng)不能過(guò)短)，意味著碼字可能的組合數(shù)多,不為別的碼字的字首。23Kraft不等式：只涉及唯一可譯碼的存在問(wèn)題而并不涉及具體的碼?？捎脕?lái)判定某一組碼不是唯一可譯的，但不能判定是唯一可譯的。不滿足Kraft不等式的碼肯定不是唯一可譯碼，而滿足的也不一定就是唯一可譯的，但可以肯定若按這樣的Li 分配碼組，則必存在有一個(gè)唯一可譯碼(也可能不止一個(gè))對(duì)應(yīng)于信源符號(hào)。24碼A碼B

14、碼C碼D碼E碼F 的值7/411/4115/1611是否滿足Kraft不等式是否唯一可譯例例4-3對(duì)于例4-2,有:412iLi25問(wèn)題: 如何來(lái)確定碼字長(zhǎng)度?如何在確定了碼字長(zhǎng)度后找出唯一可譯碼?定理 4.2(按符號(hào))變長(zhǎng)編碼定理)對(duì)于符號(hào)熵為H(X)的離散無(wú)記憶信源進(jìn)行m 進(jìn)制不等長(zhǎng)編碼, 一定存在一種無(wú)失真編碼方法, 其碼字平均長(zhǎng)度 l 滿足:mXHlmXHlog)(1log)(4.1-2)小于上限的唯一可譯碼總是存在的。26當(dāng)m=2，有(二進(jìn)制編碼定理):此時(shí)l 叫編碼速率, 有時(shí)又叫比特率。對(duì)于m進(jìn)制的不等長(zhǎng)編碼的編碼速率定義為：mlRlog(4.1-4)(bit) )(1)(XHl

15、XH(4.1-3)定理4.2改述為：若H(X)R H(X)+, 就存在唯一可譯的變長(zhǎng)碼;若R 1.75 碼長(zhǎng)的一種設(shè)計(jì)為: L1 = 1, L2 = 2, L3 = L4 = 3信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111滿足上述碼長(zhǎng)設(shè)計(jì)的碼如：例4.2中的碼C、E、F（滿足Kraft不等式）。如何做出具體的變長(zhǎng)碼是變長(zhǎng)碼的構(gòu)造問(wèn)題。28 唯一可譯碼的構(gòu)造唯一可譯碼的構(gòu)造唯一可譯碼的基本要求:碼字非續(xù)長(zhǎng)對(duì)碼字序列能做出唯一正確的分割。充分條件碼字非續(xù)長(zhǎng)對(duì)碼字序列能做

16、出唯一正確的分割。29若W 中任一碼字都不是另一個(gè)碼字的字頭；或換句話說(shuō),任一碼字都不是由另一個(gè)碼字加上若干個(gè)碼元所構(gòu)成，則W 就叫作非續(xù)長(zhǎng)碼字或異字頭碼(Prefix Condition Code)。定義 4-2碼字非續(xù)長(zhǎng)30例4.2中:信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111碼A、碼B、碼D、碼E和碼F都含有續(xù)長(zhǎng)碼，或同字頭碼；碼C是異字頭碼。31u 唯一可譯碼唯一可譯碼4.1 4.1 統(tǒng)計(jì)編碼方法的基本原理統(tǒng)計(jì)編碼方法的基本原理32不過(guò)非異字頭碼也并非一定

17、不是唯一可譯，碼D和碼E就唯一可譯；碼D：各碼組靠“逗號(hào)”（碼元0）分開(kāi)；碼E：為碼C的“鏡像”，具有“異后尾”，從 后向前即具有唯一可譯性。異字頭條件保證譯出的碼字是唯一的且具有“即時(shí)性”，減少了譯碼延時(shí)。33異字頭性質(zhì)只是碼字可分離的充分條件，非續(xù)長(zhǎng)碼也只是唯一可譯代碼集合的一個(gè)子集。唯一可譯碼非續(xù)長(zhǎng)碼圖4.3 唯一可譯碼與非續(xù)長(zhǎng)碼34二進(jìn)制編碼二進(jìn)制編碼通?？捎枚M(jìn)碼樹(shù)(二叉樹(shù))來(lái)表示各碼字的構(gòu)成(根)(節(jié)點(diǎn))圖4.4 二進(jìn)碼樹(shù)C(節(jié)點(diǎn))D(節(jié)點(diǎn))串接的最大枝數(shù)為書(shū)的節(jié)數(shù)， 圖4.4的節(jié)數(shù)為3。35用碼樹(shù)表述任何一個(gè)代碼W, 異字頭條件就成為: W中所有的碼字中所有的碼字 wi 均只對(duì)應(yīng)

18、地配置在終端節(jié)點(diǎn)上。均只對(duì)應(yīng)地配置在終端節(jié)點(diǎn)上。圖4.5 碼C的樹(shù)結(jié)構(gòu)(異字頭碼)根001110010110111根011100(011)(111)11(0)(01)碼E的樹(shù)結(jié)構(gòu)(非異字頭碼)3611niLim此時(shí)碼C為用盡的異字頭碼, 有:倘若有一碼字為(0,10,110), 則該碼為非用盡的異字頭碼, 有:11niLim37按照Kraft 不等式的要求，對(duì)n個(gè)消息x1, x2, ,xn分配了編碼長(zhǎng)度L1,L2, ,Ln, 即可用二進(jìn)碼樹(shù)來(lái)生成異字頭碼, 生成規(guī)律是: 從根出發(fā)開(kāi)始生出2枝 ; 每一枝用一個(gè)碼元aj A=0,1來(lái)表示; 枝盡節(jié)來(lái),節(jié)外生枝; 在第Li級(jí)端節(jié)點(diǎn)(Li級(jí)節(jié)點(diǎn)共有2

19、Li個(gè))上,配置信 號(hào)單元 xi , i=1,2, , n ; 從根開(kāi)始直奔對(duì)應(yīng)的端節(jié)點(diǎn),沿途(聯(lián)枝)所遇到 的碼元 aj 所構(gòu)成的符號(hào),即為對(duì)應(yīng)于該信號(hào)單元 xi 的碼字 wi 。異字頭碼無(wú)譯碼延時(shí)，構(gòu)造簡(jiǎn)單。38結(jié)論：任一唯一可譯碼，總可以用與各相應(yīng)碼字長(zhǎng)度一樣的異字頭碼代替。異字頭碼雖然只是唯一可譯碼的一種，但它具有代表性和普遍意義，在信息保持編碼中廣泛應(yīng)用。長(zhǎng)度為L(zhǎng)1,L2, ,Ln的M進(jìn)制異字頭碼存在的充要條件，也使Kraft不等式成立。394.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計(jì)

20、編碼方法統(tǒng)計(jì)編碼方法40Shannon-Fano 編碼編碼 貝爾實(shí)驗(yàn)室的 Claude Shannon 和 MIT 的 R.M.Fano 幾乎同時(shí)提出了最早的對(duì)符號(hào)進(jìn)行有效編碼從而實(shí)現(xiàn)數(shù)據(jù)壓縮的 Shannon-Fano 編碼方法。信源字母概率a1a2a3a41/2=0.51/4=0.251/8=0.1251/8=0.125對(duì)于例4.2中的信源:Shannon-Fano 編碼的核心是構(gòu)造二進(jìn)碼樹(shù)，構(gòu)造的方式非常簡(jiǎn)單： 411) 將給定符號(hào)按照其概率從大到小排序 2) 將序列分成上下兩部分，使得上部概率總和盡可能接近下部概率總和,有：a1 0.5a2 0.25a3 0.125a4 0.125a1

21、 0.5 -a2 0.25a3 0.125a4 0.125Shannon-Fano 編碼步驟編碼步驟424) 分別對(duì)左右子樹(shù)重復(fù)2 、3兩步，直到所有的符號(hào)都成為二進(jìn)碼樹(shù)的終端節(jié)點(diǎn)為止。現(xiàn)在如下的二進(jìn)碼樹(shù)：3) 把第2步中劃分出的上部作為二進(jìn)碼樹(shù)的左子樹(shù)，記 0，下部作為二進(jìn)碼樹(shù)的右子樹(shù)，記 1。 a1 0.5 0-a2 0.25 1a3 0.125a4 0.125a1 0.5 0-a2 0.25 1 0 -a3 0.125 1 0-a4 0.125 143a1 - 0 a2 10 a3 - 110 a4 - 111 根001110a1a2a3a4于是得到了此信息的編碼表：得到的碼表就是碼C4

22、4習(xí)題：二進(jìn)制費(fèi)諾編碼 信信源源符符號(hào)號(hào) 概概率率 編編碼碼 碼碼字字 碼碼長(zhǎng)長(zhǎng) x1 0.32 0 00 2 x2 0.22 0 1 01 2 x3 0.18 0 10 2 x4 0.16 0 110 3 x5 0.08 0 1110 4 x6 0.04 1 1 1 1 1111 4 123456,()0.320.220.180.160.080.04XxxxxxxP X解：編碼過(guò)程如下表。對(duì)該信源編二進(jìn)制費(fèi)諾碼。平均碼長(zhǎng)平均碼長(zhǎng) 碼元碼元/符號(hào)符號(hào) 編碼效率編碼效率61( )2.4iiiLp x L()2.350.982.4H XL設(shè)有一單符號(hào)離散信源454.2 霍夫曼編碼霍夫曼編碼1952

23、年 ，霍夫曼(D.A.Huffman) 提出霍夫曼編碼, 又稱最佳編碼根據(jù)字符出現(xiàn)概率來(lái)構(gòu)造平均長(zhǎng)度根據(jù)字符出現(xiàn)概率來(lái)構(gòu)造平均長(zhǎng)度最短的異字頭碼字。最短的異字頭碼字。 46 霍夫曼碼的構(gòu)造霍夫曼碼的構(gòu)造理論基礎(chǔ)定理定理4.3在變長(zhǎng)編碼中,若碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小逆序排列,則其平均長(zhǎng)度最短。47編碼步驟：編碼步驟： 將信源符號(hào)概率按遞減順序排列將信源符號(hào)概率按遞減順序排列; ; 將兩個(gè)最小的概率進(jìn)行相加，并繼續(xù)這一步驟，直到概率將兩個(gè)最小的概率進(jìn)行相加，并繼續(xù)這一步驟，直到概率 達(dá)到達(dá)到1.0為止為止; ; 在每對(duì)組合中的上部指定為在每對(duì)組合中的上部指定為1(或或0), ,下部

24、指定為下部指定為0(或或1); ; 畫(huà)出每個(gè)信源符號(hào)概率到畫(huà)出每個(gè)信源符號(hào)概率到1.0處的路徑處的路徑, ,記下沿路徑的記下沿路徑的1和和0 ; 對(duì)于每個(gè)信源符號(hào)都寫出對(duì)于每個(gè)信源符號(hào)都寫出1 1、0 0序列，則序列，則從右到左從右到左就得到霍就得到霍 夫曼編碼。夫曼編碼。48例例4-6對(duì)一個(gè)7符號(hào)信源A=a1,a2, ,a7, 求其霍夫曼編碼信源符號(hào) 出現(xiàn)概率 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 碼長(zhǎng) 碼 字 2 11 2 10 3 011 3 010 3 001 4 0001 4 00000.26010.11010

25、.35010.390110.61101.00049011a3根例4-6的Huffman二進(jìn)碼樹(shù)11a110a2010a4001a50001a60000a750例4-6的信源熵為:霍夫曼編碼的平均字長(zhǎng)為:(bit) 61. 2)(log)()(71iiiapapAH(bit) 72.2)(71iiiLapl編碼效率:( )2.6196 %2.72H Al51另例另例1對(duì)一個(gè)對(duì)一個(gè)7符號(hào)信源符號(hào)信源A=a1,a2, ,a7, 求其霍夫曼編碼求其霍夫曼編碼:信源符號(hào) 出現(xiàn)概率 a1 0.35 a2 0.20 a3 0.15 a4 0.12 a5 0.10 a6 0.05 a7 0.03 碼長(zhǎng) 碼 字

26、 2 00 2 10 3 010 3 011 3 110 4 1110 4 11110.080.180.270.620.381.00111111000000關(guān)鍵：在每一步，總是最低概率的兩個(gè)符號(hào)構(gòu)成一對(duì)。關(guān)鍵：在每一步，總是最低概率的兩個(gè)符號(hào)構(gòu)成一對(duì)。52注意注意：哈夫曼的編法并不唯一哈夫曼的編法并不唯一每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”0”和和“1”1”碼碼元是任意的，所以可得到不同的碼字。只要元是任意的，所以可得到不同的碼字。只要在各次縮減信在各次縮減信源中保持碼元分配的一致性源中保持碼元分配的一致性，即能得到可分離碼字。即能得到可分離碼字。不同

27、的碼元分配，得到的具體碼字不同，但碼長(zhǎng)不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)k ki i不變，不變，平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別；平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別；縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來(lái)說(shuō)，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排列，編出這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的的碼都是正確的，但得到的碼字不相同碼字不相同。不同的編法得到不同的編法得到的的碼字長(zhǎng)度碼字長(zhǎng)度k ki i也不盡相同也不盡相同。53 單符號(hào)離散無(wú)記憶信源單符號(hào)離散無(wú)記憶信源對(duì)其編二進(jìn)制哈夫曼碼。對(duì)其

28、編二進(jìn)制哈夫曼碼。解：解：方法一方法一 合并后的新符號(hào)排在其它相同概率符號(hào)之后合并后的新符號(hào)排在其它相同概率符號(hào)之后12345,()0.40.20.20.10.1XxxxxxP X另例另例254 這兩種編碼哪一種更好呢？這兩種編碼哪一種更好呢？我們來(lái)計(jì)算一下二者的碼長(zhǎng)。我們來(lái)計(jì)算一下二者的碼長(zhǎng)。方法二：方法二：合并后的新符號(hào)排在其它相同概率符號(hào)的前面。合并后的新符號(hào)排在其它相同概率符號(hào)的前面。552221() ( )()qiiiiE lLP slL引入碼字長(zhǎng)度偏離平均碼長(zhǎng)的方差的概念：36. 1 2)2 . 24(1 . 0)2 . 23(2 . 0 )2 . 22(2 . 0)2 . 21

29、(4 . 0 22222方法一：16. 0 2)2 . 23(1 . 0 2)2 . 22(2 . 0)2 . 22(4 . 02222方法二：兩種編碼的平均碼長(zhǎng)是一樣的，都是兩種編碼的平均碼長(zhǎng)是一樣的，都是2.2，那一種更好呢，我，那一種更好呢，我們可以計(jì)算一下平均碼長(zhǎng)的方差。們可以計(jì)算一下平均碼長(zhǎng)的方差。56n可見(jiàn)：第二種編碼方法的碼長(zhǎng)方差要小許多。意味著第二種可見(jiàn)：第二種編碼方法的碼長(zhǎng)方差要小許多。意味著第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。第一種方法編出的第一種方法編出的5 5個(gè)碼字有個(gè)碼字有4 4種不同的碼長(zhǎng)；種不同的碼長(zhǎng)；第二

30、種方法編出的碼長(zhǎng)只有第二種方法編出的碼長(zhǎng)只有2 2種不同的碼長(zhǎng)；種不同的碼長(zhǎng)；顯然，顯然，第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。57結(jié)論：在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由結(jié)論：在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能合并后的新符號(hào)盡可能排在靠前的位置排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。數(shù)減少，使短碼得到充分利用。58Huffman編碼和譯碼過(guò)程編碼和譯碼過(guò)程編碼編碼輸出輸出Huffma

31、nHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號(hào)序列信源符號(hào)序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號(hào)序列信源符號(hào)序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號(hào)序列信源符號(hào)序列解碼解碼解碼后的解碼后的字符序列字符序列Huff

32、man碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號(hào)序列信源符號(hào)序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號(hào)序列信源符號(hào)序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表Huffman碼表碼表信源符號(hào)序列信源符號(hào)序列解碼后的解碼后的字符序列字符序列Huffman碼表碼表信源符號(hào)序列信源符號(hào)序列解碼后的解碼后的字符序列字符序列H

33、uffman碼表碼表信源符號(hào)序列信源符號(hào)序列Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器Huffman碼表碼表輸出輸出HuffmanHuffman碼流碼流接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流解碼后的解碼后的字符序列字符序列Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流信源符號(hào)序列信源符號(hào)序列解碼后的解碼后的字符序列字符序列Huffman碼表碼

34、表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表信源符號(hào)序列信源符號(hào)序列解碼后的解碼后的字符序列字符序列Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流59 信源編碼基本定理信源編碼基本定理霍夫曼編碼霍夫曼編碼定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)段當(dāng)信源符號(hào)的概率當(dāng)信源符號(hào)的概率 pj=2-k編碼效率等于編碼效率等于100%定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)段編碼效率等于編碼效率等于100%定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)段編碼效率等于編碼效率等于100%定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)

35、段編碼效率等于編碼效率等于100%定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)段編碼效率等于編碼效率等于100%定長(zhǎng)的數(shù)據(jù)段定長(zhǎng)的數(shù)據(jù)段變長(zhǎng)的代碼變長(zhǎng)的代碼( (只能分配接只能分配接近近log2pj的整數(shù)長(zhǎng)碼字的整數(shù)長(zhǎng)碼字) )60例4-7:對(duì)于二值圖像，如傳真機(jī)文件，輸出非“黑”即“白”，有：X=x1，x2=白，黑，其概率與所傳文件有關(guān)，假設(shè)對(duì)某頁(yè)文件，有P(x1)=0.9, P(x2)=0.1 。不考慮信號(hào)間的關(guān)聯(lián)時(shí)，其信息熵為：不考慮信號(hào)間的關(guān)聯(lián)時(shí)，其信息熵為：()0.9log0.90.1 log0.10.469 (bit/pel)H X 此時(shí)此時(shí)W=0,1，無(wú)論用定長(zhǎng)碼還是最佳編碼，無(wú)論用定長(zhǎng)碼還是最佳編碼

36、, 平均碼長(zhǎng)至平均碼長(zhǎng)至少為少為l1=1 (bit) ；此時(shí)霍夫曼編碼無(wú)壓縮作用此時(shí)霍夫曼編碼無(wú)壓縮作用編碼效率為編碼效率為1 =H(X)/ l1=46.9 %61解決辦法:A =a1, , am ;X K - X =x1, , xn 的延長(zhǎng)的延長(zhǎng);W K - W =w1, , wn 的延長(zhǎng)的延長(zhǎng), , 其平均長(zhǎng)度為其平均長(zhǎng)度為lK ;P(wi)=P( xi), P(W)= P(wi), i=1,2, ,n ;如果要求如果要求W K 為單義代碼為單義代碼, , 則則: :(4.2-1)式式(4.2-1)也叫做無(wú)失真編碼的基本定理。也叫做無(wú)失真編碼的基本定理。定理定理4.4(信源編碼定理信源編碼

37、定理):( )( )1loglogH XlH XmKmK62含義：含義：如果我們把如果我們把 X 延長(zhǎng)后再對(duì)延長(zhǎng)后再對(duì) K 元組元組( K 為為延長(zhǎng)長(zhǎng)度延長(zhǎng)長(zhǎng)度)進(jìn)行編碼，那么不必利用數(shù)據(jù)前后的關(guān)聯(lián)，只要進(jìn)行編碼，那么不必利用數(shù)據(jù)前后的關(guān)聯(lián)，只要K 足夠大，則代表每消息單元足夠大，則代表每消息單元 X 的平均符號(hào)個(gè)數(shù)的平均符號(hào)個(gè)數(shù)l/K 可以任意趨向于下限?？梢匀我廒呄蛴谙孪蕖?3例例4-8: 利用最佳編碼利用最佳編碼, 以例以例4-7來(lái)說(shuō)明來(lái)說(shuō)明l/K趨向于下限的情況。趨向于下限的情況。把把 X 延長(zhǎng)到延長(zhǎng)到 X 2 ，假定信源是離散無(wú)記憶信源，有圖假定信源是離散無(wú)記憶信源，有圖4.7所所示

38、示 X 2 的最佳編碼：的最佳編碼：圖圖4.7 2單元延長(zhǎng)信號(hào)的最佳編碼單元延長(zhǎng)信號(hào)的最佳編碼P(x1, x1) = P(x1)P( x1) =0.81P(x1, x2) = P(x1)P( x2) =0.09P(x2, x1) = P(x2)P( x1) =0.09P(x2, x2) = P(x2)P( x2) =0.010.100.191.00111000W 2 01011011164W 2平均長(zhǎng)度為平均長(zhǎng)度為:l2 =0.81+0.092+0.093+0.013=1.29 bit/pelW 2的每一個(gè)元素代表兩個(gè)消息單元的每一個(gè)元素代表兩個(gè)消息單元,因此平均每一個(gè)消因此平均每一個(gè)消息單元

39、的符號(hào)個(gè)數(shù)是息單元的符號(hào)個(gè)數(shù)是:l2 /2 = 1.29/2 = 0.645 bit/pel2 =H(X)/ l2=72.7 %編碼效率提高到編碼效率提高到: :65把 X 延長(zhǎng)到 X 3 ，有圖4.8所示 X 3 的最佳編碼：圖4.8 3單元延長(zhǎng)信號(hào)的最佳編碼P(x1, x1, x1) =0.729P(x1, x1, x2) =0.081P(x1, x2, x1) =0.081P(x2, x1, x1) =0.0810.0100.109111000P(x1, x2, x2) =0.009P(x2, x1, x2) =0.009P(x2, x2, x1) =0.009P(x2, x2, x2)

40、 =0.0010.0180.0280.1620.2711.0000111001W 311111111101110111010110001110066W 3平均長(zhǎng)度為:l3 =0.729+0.08133 +5( 30.09+0.001)=1.598 bit/pelW 3的每一個(gè)元素代表三個(gè)消息單元, 因此平均每一個(gè)消息單元的符號(hào)個(gè)數(shù)是:l3 /3 = 1.598/3 = 0.5327 bit/pel3 =H(X)/ l3=88.0 %編碼效率提高到:繼續(xù)下去,就可使 lK /K 0.469, 或=100% 67進(jìn)一步減小 l/K , 利用信號(hào)的前后關(guān)聯(lián)減小下限, 即利用:H(X, Y )H(X)

41、+H(Y)(3.2-13)H(X | Y )H(X)(3.2-11b)或:可以減小下限,從而減小l/K要求知道P(X), P(X,Y) 或 P(X|Y) 才能進(jìn)行最佳編碼。如果信號(hào)繼續(xù)有關(guān)聯(lián)可供利用，繼續(xù)延長(zhǎng)，會(huì)使下限變得很小。68信源編碼理論信源編碼理論 給定消息單元集合X、符號(hào)集合A和X的概率分布P(X)， 可以采用最佳編碼，使代碼W 的平均長(zhǎng)度滿足; 如果把X 延長(zhǎng)至 X K ,則不必考慮信號(hào)前后的關(guān)聯(lián)性, 就可以是代表一個(gè)消息單元的符號(hào)個(gè)數(shù) l /K 任意接近 下限 H(X)/logm; 如果利用延長(zhǎng)信號(hào)X K的前后關(guān)聯(lián),可使下限減小。具體實(shí)現(xiàn)時(shí)，如果將信號(hào)延長(zhǎng)得過(guò)長(zhǎng)，會(huì)使實(shí)際設(shè)備復(fù)雜

42、到不合理的程度。1log)(,log)(mXHmXHl69霍夫曼編碼選擇模型霍夫曼編碼選擇模型靜態(tài)統(tǒng)計(jì)模型 在編碼前統(tǒng)計(jì)要編碼的信息中所有字符的出現(xiàn)概率，然后根據(jù)統(tǒng)計(jì)出的信息建立編碼樹(shù)，進(jìn)行編碼 。70缺點(diǎn)缺點(diǎn) 對(duì)數(shù)據(jù)量較大的信息，靜態(tài)統(tǒng)計(jì)要消耗大量的時(shí)間； 必須保存統(tǒng)計(jì)出的結(jié)果以便解碼時(shí)構(gòu)造相同的編碼樹(shù)，或者直接保存編碼樹(shù)本身，而且，對(duì)于每次靜態(tài)統(tǒng)計(jì)，都有不同的結(jié)果，必須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）； 靜態(tài)統(tǒng)計(jì)模型統(tǒng)計(jì)出的頻率是字符在整個(gè)文件中的出現(xiàn)頻率，往往反映不出字符在文件中不同局部出現(xiàn)頻率的變化情況，使用這一頻率進(jìn)行壓縮，大多數(shù)情況下得不到太好壓縮效果，文

43、件有時(shí)甚至在壓縮后反而增大了。71一種有效的“靜態(tài)統(tǒng)計(jì)模型”的替代方案 如果要壓縮的所有信息在分布上存在著共同的特征，使用語(yǔ)言學(xué)家事先已經(jīng)建立好的字母頻率表來(lái)進(jìn)行壓縮和解壓縮，不但不用保存多份統(tǒng)計(jì)信息，而且一般說(shuō)來(lái)對(duì)該類文件有著較好的壓縮效果。比如我們要壓縮的是普通的英文文本，那么，字母 a 或者字母 e 的出現(xiàn)頻率應(yīng)當(dāng)是大致穩(wěn)定的。一種有效的“靜態(tài)統(tǒng)計(jì)模型”的替代方案 比如我們要壓縮的是普通的英文文本，那么，字母 a 或者字母 e 的出現(xiàn)頻率應(yīng)當(dāng)是大致穩(wěn)定的。72這種方案除了適應(yīng)性不太強(qiáng)以外，偶爾還會(huì)有一些尷尬的時(shí)候。缺點(diǎn)缺點(diǎn) If Youth，throughout all history，

44、 had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldnt constantly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 發(fā)現(xiàn)什么問(wèn)題了嗎？整段話中竟沒(méi)有出現(xiàn)一次英文中出現(xiàn)頻率最高的字母 e 。這種方案除了適應(yīng)性不太強(qiáng)以外，偶爾還會(huì)有一些尷尬的時(shí)候

45、。發(fā)現(xiàn)什么問(wèn)題了嗎？整段話中竟沒(méi)有出現(xiàn)一次英文中出現(xiàn)頻率最高的字母 e 。73對(duì)英文或中文文本，有一種比較實(shí)用的靜態(tài)模型：不是把字符而是把英文單詞或中文詞語(yǔ)作為統(tǒng)計(jì)頻率和編碼的單位進(jìn)行壓縮。這種壓縮方式可以達(dá)到相當(dāng)不錯(cuò)的壓縮效果，并被廣泛地用于全文檢索系統(tǒng)。74自適應(yīng)模型自適應(yīng)模型無(wú)需為解壓縮預(yù)先保存任何信息，整個(gè)編碼是在壓縮和解壓縮過(guò)程中動(dòng)態(tài)創(chuàng)建的，而且自適應(yīng)編碼由于其符號(hào)頻率是根據(jù)信息內(nèi)容的變化動(dòng)態(tài)得到的，更符合符號(hào)的局部分布規(guī)律，因此在壓縮效果上比靜態(tài)模型好許多。根據(jù)已經(jīng)編碼的符號(hào)頻率決定下一個(gè)符號(hào)的編碼。根據(jù)已經(jīng)編碼的符號(hào)頻率決定下一個(gè)符號(hào)的編碼。75算術(shù)編碼、字典編碼等更為適合采用自

46、適應(yīng)模型 但是，采用自適應(yīng)模型必須考慮編碼表的動(dòng)態(tài)特性，即編碼表必須可以隨時(shí)更新以適應(yīng)符號(hào)頻率的變化。對(duì)于 Huffman 編碼來(lái)說(shuō)，我們很難建立能夠隨時(shí)更新的二叉樹(shù)，76 霍夫曼碼的局限性霍夫曼碼的局限性霍夫曼編碼霍夫曼編碼文本文件壓縮文本文件壓縮二進(jìn)制文件壓縮二進(jìn)制文件壓縮適用于適用于經(jīng)過(guò)符號(hào)合并經(jīng)過(guò)符號(hào)合并77局限性局限性: : 輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的霍夫曼碼表尺寸輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的霍夫曼碼表尺寸 ; ; 譯碼復(fù)雜度譯碼復(fù)雜度; ; 需要知道輸入符號(hào)集的概率分布；需要知道輸入符號(hào)集的概率分布； 由于碼長(zhǎng)不等，還存在一個(gè)輸入與輸出的速率由于碼長(zhǎng)不等，還存在一個(gè)輸入與輸出的速率 匹配

47、問(wèn)題。匹配問(wèn)題。784.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計(jì)編碼方法統(tǒng)計(jì)編碼方法794.3 游程編碼游程編碼游程長(zhǎng)度游程長(zhǎng)度(RL: Run Length,簡(jiǎn)稱游程或游長(zhǎng)簡(jiǎn)稱游程或游長(zhǎng)) )： 由字符由字符( (或信號(hào)采樣值或信號(hào)采樣值) )構(gòu)成的數(shù)據(jù)流中各字符構(gòu)成的數(shù)據(jù)流中各字符重復(fù)出現(xiàn)而形成的字符串的長(zhǎng)度。重復(fù)出現(xiàn)而形成的字符串的長(zhǎng)度。用二進(jìn)制碼字給出形成串的字符、串的長(zhǎng)度用二進(jìn)制碼字給出形成串的字符、串的長(zhǎng)度及串的位置等信息，以此來(lái)恢復(fù)出原來(lái)的數(shù)及串的位置等信息，以此來(lái)恢復(fù)出原來(lái)的數(shù)據(jù)

48、流。據(jù)流。 游程長(zhǎng)度編碼游程長(zhǎng)度編碼(RLC) )：80游程編碼類型：游程編碼類型：變長(zhǎng)游程編碼變長(zhǎng)游程編碼使用位數(shù)是固定的，即使用位數(shù)是固定的，即RLRL位數(shù)是固定的，如果灰度位數(shù)是固定的，如果灰度連續(xù)相同的個(gè)數(shù)超過(guò)了固定位數(shù)所能表示的最大值，連續(xù)相同的個(gè)數(shù)超過(guò)了固定位數(shù)所能表示的最大值，則進(jìn)入下一輪游程編碼；則進(jìn)入下一輪游程編碼；定長(zhǎng)游程編碼定長(zhǎng)游程編碼對(duì)不同范圍的游程采用不同位數(shù)的編碼，即表示對(duì)不同范圍的游程采用不同位數(shù)的編碼，即表示RLRL位數(shù)不固定。位數(shù)不固定。81 基本的游程編碼基本的游程編碼基本的基本的RLC壓縮方法：壓縮方法：最初出現(xiàn)在最初出現(xiàn)在 IBM 3780 BYSYNC

49、 (Binary Synchronous Communication)通信協(xié)議中。通信協(xié)議中?；镜幕镜腞LC數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：XScRL數(shù)數(shù) 據(jù)據(jù) 流流圖圖4.9 基本的基本的RLC數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)82其中其中X ： 代表數(shù)據(jù)字符；代表數(shù)據(jù)字符； Sc： Sc X，表示有一個(gè)字符在此位置；，表示有一個(gè)字符在此位置； RL： 代表串（游程）的長(zhǎng)度，字符重復(fù)出現(xiàn)的次數(shù)；代表串（游程）的長(zhǎng)度，字符重復(fù)出現(xiàn)的次數(shù)；只有當(dāng)只有當(dāng)RL 3時(shí)時(shí), 才有數(shù)據(jù)壓縮效益。才有數(shù)據(jù)壓縮效益。編碼時(shí)：先判斷編碼時(shí)：先判斷RL值，再?zèng)Q定是否值，再?zèng)Q定是否RLC； 解碼時(shí)：根據(jù)每一解碼時(shí)：根據(jù)每一X后的碼字是否為后

50、的碼字是否為Sc，再，再 決定下一個(gè)字的含義。決定下一個(gè)字的含義。83RLC壓縮效能:取決于數(shù)據(jù)流中重復(fù)字符出現(xiàn)次數(shù)、平均游程長(zhǎng)度及所采用的編碼結(jié)構(gòu)。平均重復(fù)平均重復(fù)長(zhǎng)度長(zhǎng)度重復(fù)出現(xiàn)重復(fù)出現(xiàn)1010次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)2020次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)3030次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)4040次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)5050次的壓縮比次的壓縮比41.0101.0201.0311.0421.05351.0201.0421.0641.0731.11161.0311.0641.0991.1361.17671.0421.0871.1361.1901.25

51、081.0531.1111.1761.2501.33391.0641.1361.2201.3161.429101.0751.1631.2661.3841.538表4.2 基本的游程編碼壓縮比84 二值圖像的游程編碼二值圖像的游程編碼僅有黑(“1”代表)、白(“0”代表)兩個(gè)亮度值的圖像。 經(jīng)掃描儀得到的氣象圖、工程圖、地圖、線 路圖等； 文字組成的文件圖像； 灰度圖像經(jīng)過(guò)位平面分解或抖動(dòng)處理后 的圖像。最常用的傳輸方式：傳真二值圖像二值圖像編碼也往往指數(shù)字傳真編碼。85二值圖像的游程編碼二值圖像的游程編碼數(shù)據(jù)字符 X=白，黑對(duì)二值圖像每一掃描行： 白像素游程（白長(zhǎng)） 黑像素游程（黑長(zhǎng)）對(duì)不同長(zhǎng)

52、度的白長(zhǎng)和黑長(zhǎng)，按其出現(xiàn)概率的不同分別配以不同長(zhǎng)度的碼字。RLC利用多個(gè)像素之間的相關(guān)性，可得到較低的碼率下限。86二值圖像的二值圖像的RLC的兩種方式的兩種方式 不分白長(zhǎng)和黑長(zhǎng)，只根據(jù)長(zhǎng)度進(jìn)行編碼由于在實(shí)際圖像中, 白長(zhǎng)和黑長(zhǎng)的概率分布各異, 此方法不是很有效; 其最低比特率 滿足:WBnWBWBWBWBWBPPhnhll(4.3-1)其中：PW和PB分別是白像素和黑像素出現(xiàn)的概率; lW和lB分別是白長(zhǎng)和黑長(zhǎng)的平均像素?cái)?shù)(平均長(zhǎng)度 ); hWB為每個(gè)像素的熵值。 不分白長(zhǎng)和黑長(zhǎng)，只根據(jù)長(zhǎng)度進(jìn)行編碼 對(duì)白長(zhǎng)和黑長(zhǎng)分別編碼(前CCITT建議)87編碼過(guò)程：編碼過(guò)程： 先對(duì)圖像進(jìn)行統(tǒng)計(jì)分別得出白

53、長(zhǎng)為先對(duì)圖像進(jìn)行統(tǒng)計(jì)分別得出白長(zhǎng)為 i 的的 概率概率 PiW 和黑長(zhǎng)為和黑長(zhǎng)為 i 的概率的概率 PiB， 然后根據(jù)霍夫曼原則按然后根據(jù)霍夫曼原則按RL出現(xiàn)概率來(lái)分出現(xiàn)概率來(lái)分 配碼字。配碼字。二值圖像的二值圖像的RLC實(shí)為霍夫曼碼的具體應(yīng)用實(shí)為霍夫曼碼的具體應(yīng)用88由于各種由于各種 RL 的出現(xiàn)概率在行間、頁(yè)的出現(xiàn)概率在行間、頁(yè)間都不相同，且為求得概率，需要存間都不相同，且為求得概率，需要存儲(chǔ)數(shù)據(jù)并做統(tǒng)計(jì)計(jì)算，難以實(shí)時(shí)編碼儲(chǔ)數(shù)據(jù)并做統(tǒng)計(jì)計(jì)算，難以實(shí)時(shí)編碼CCITT的的T.4建議建議: 推薦推薦8幅標(biāo)準(zhǔn)傳真樣張為幅標(biāo)準(zhǔn)傳真樣張為統(tǒng)計(jì)依據(jù)統(tǒng)計(jì)依據(jù),根據(jù)各種根據(jù)各種RL的出現(xiàn)概率編出霍夫的出現(xiàn)概

54、率編出霍夫曼碼表，稱為改進(jìn)型霍夫曼編碼曼碼表，稱為改進(jìn)型霍夫曼編碼(MHC) 。89MH編碼規(guī)則: (見(jiàn)表4.7) RL=063， 用一個(gè)相應(yīng)的結(jié)尾碼表示用一個(gè)相應(yīng)的結(jié)尾碼表示 ; ; RL=641728，用一個(gè)組合基干碼加一個(gè)補(bǔ)充結(jié)尾碼；，用一個(gè)組合基干碼加一個(gè)補(bǔ)充結(jié)尾碼； RL(白白)=128, 補(bǔ)充結(jié)尾碼為補(bǔ)充結(jié)尾碼為0(白白)=00110101, 其編碼為其編碼為: 10010 | 00110101 RL(白白)=129, 補(bǔ)充結(jié)尾碼為補(bǔ)充結(jié)尾碼為1(白白)=000111, 其編碼為其編碼為: 10010 | 000111 規(guī)定每行都從白游程開(kāi)始，若實(shí)際掃描由黑開(kāi)始，則規(guī)定每行都從白游

55、程開(kāi)始，若實(shí)際掃描由黑開(kāi)始，則 需在行首加零長(zhǎng)度白游程；每行結(jié)束要加同步碼需在行首加零長(zhǎng)度白游程；每行結(jié)束要加同步碼EOL。90 游程編碼的局限性游程編碼的局限性 對(duì)二值圖像最為有效，但對(duì)數(shù)據(jù)文件就不那對(duì)二值圖像最為有效，但對(duì)數(shù)據(jù)文件就不那 么顯著，而對(duì)于課文實(shí)質(zhì)已無(wú)使用價(jià)值么顯著，而對(duì)于課文實(shí)質(zhì)已無(wú)使用價(jià)值; 壓縮字符與數(shù)值混合序列比較麻煩，要求區(qū)分壓縮字符與數(shù)值混合序列比較麻煩，要求區(qū)分 計(jì)數(shù)字段和常規(guī)字符；計(jì)數(shù)字段和常規(guī)字符； 需要較大容量的緩沖和較低誤碼的優(yōu)質(zhì)信道。需要較大容量的緩沖和較低誤碼的優(yōu)質(zhì)信道。914.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編

56、碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計(jì)編碼方法統(tǒng)計(jì)編碼方法92u 問(wèn)題的引入問(wèn)題的引入 Huffman碼等在實(shí)際應(yīng)用過(guò)程中，只有在信源符號(hào)概率分碼等在實(shí)際應(yīng)用過(guò)程中，只有在信源符號(hào)概率分布等于布等于2的負(fù)整次冪時(shí)，它們才能產(chǎn)生最佳效果，即產(chǎn)生最佳的負(fù)整次冪時(shí)，它們才能產(chǎn)生最佳效果，即產(chǎn)生最佳變長(zhǎng)碼。變長(zhǎng)碼。 假設(shè)某個(gè)字符的出現(xiàn)概率為假設(shè)某個(gè)字符的出現(xiàn)概率為 80%，那么該字符事實(shí)上只需，那么該字符事實(shí)上只需要要 -log2(0.8) = 0.322 位編碼，但位編碼，但Huffman 編碼一定會(huì)為其分編碼一定會(huì)為其分配一位配一位 0 或或1 的編碼。的編碼。 真的能

57、只輸出真的能只輸出 0.322 個(gè)個(gè) 0 或或 0.322 位信息嗎位信息嗎？4.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）934.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）u 算術(shù)編碼基本思路算術(shù)編碼基本思路 算術(shù)編碼一種非分組編碼算法。它是從全序列出發(fā)，算術(shù)編碼一種非分組編碼算法。它是從全序列出發(fā)，采用遞推形式的連續(xù)編碼。它不是將單個(gè)的信源符號(hào)映射采用遞推形式的連續(xù)編碼。它不是將單個(gè)的信源符號(hào)映射成一個(gè)碼字，而是將整個(gè)輸入序列的符號(hào)依據(jù)它們的概率成一個(gè)碼字，而是將整個(gè)輸入序列的符號(hào)依據(jù)它們的概率映射為實(shí)數(shù)軸上區(qū)間映射為實(shí)數(shù)軸上區(qū)間0 1)0 1)內(nèi)的一個(gè)

58、小區(qū)間，再在該小區(qū)間內(nèi)的一個(gè)小區(qū)間，再在該小區(qū)間內(nèi)選擇一個(gè)代表性的二進(jìn)制小數(shù)，作為實(shí)際的編碼輸出。內(nèi)選擇一個(gè)代表性的二進(jìn)制小數(shù)，作為實(shí)際的編碼輸出。 例如算術(shù)編碼對(duì)某條信息的輸出為例如算術(shù)編碼對(duì)某條信息的輸出為 10100011111010001111，那么它，那么它表示小數(shù)表示小數(shù) 0.10100011110.1010001111，也即十進(jìn)制數(shù)，也即十進(jìn)制數(shù) 0.640.64。941) 碼字刷新：碼字刷新：C(sai)=C(s)+P(ai)A(s)2) 區(qū)間刷新：區(qū)間刷新：A(sai)=p(ai)A(s) 設(shè)輸入符號(hào)串設(shè)輸入符號(hào)串s取自符號(hào)集取自符號(hào)集S=a1,a2,a3,am, p(ai)

59、=p1,p2,p3,pm, s后跟符號(hào)后跟符號(hào)ai擴(kuò)展成符號(hào)串?dāng)U展成符號(hào)串sai，算術(shù)編碼的迭代關(guān)系為，算術(shù)編碼的迭代關(guān)系為: 符號(hào)累積概率：符號(hào)累積概率：初始條件：初始條件： 11)()(ikkiapaP1)(, 0)(, 1)(, 0)(pPACu 算術(shù)編碼方法具體過(guò)程算術(shù)編碼方法具體過(guò)程4.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）95當(dāng)處理當(dāng)處理ai時(shí)，區(qū)間時(shí)，區(qū)間A(s)寬度根據(jù)寬度根據(jù)ai出現(xiàn)概率出現(xiàn)概率p(ai)而變窄，符號(hào)而變窄，符號(hào)序列越長(zhǎng)，相應(yīng)的子區(qū)間越窄，編碼的位數(shù)越多。符號(hào)串每序列越長(zhǎng)，相應(yīng)的子區(qū)間越窄，編碼的位數(shù)越多。符號(hào)串每一步新擴(kuò)展的碼字一步新擴(kuò)

60、展的碼字C(sai)都是由原符號(hào)串的碼字都是由原符號(hào)串的碼字C(s)與新區(qū)間與新區(qū)間寬度寬度A(sai)的算術(shù)相加，的算術(shù)相加，“算術(shù)碼算術(shù)碼”由此得名。由此得名。算術(shù)編碼在傳輸任何信號(hào)算術(shù)編碼在傳輸任何信號(hào)ai之前，信號(hào)的完整范圍是之前，信號(hào)的完整范圍是) 1 , 0)()(),(ACC4.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）u 算術(shù)編碼方法具體過(guò)程算術(shù)編碼方法具體過(guò)程964.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）u 例：算術(shù)編碼方法具體編碼過(guò)程例：算術(shù)編碼方法具體編碼過(guò)程 設(shè)某信源取自符號(hào)集設(shè)某信源取自符號(hào)集S=a,b,c,e,r,!，!表示編