數(shù)據(jù)無(wú)損壓縮ppt課件-文庫(kù)吧資料
2024-11-09 22:17本頁(yè)面
【正文】 標(biāo)成 0 步驟⑤：從根節(jié)點(diǎn) PN開(kāi)始順著樹(shù)枝到每個(gè)葉子分別寫(xiě)出 每個(gè)符號(hào)的代碼 2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 22 of 42 霍夫曼編碼 — Case Study 1 (續(xù) 3) 符號(hào) B (10) A (8) E (5) D (4) C (3) P1 (7) P2 (12) P3 (18) P4 (30) 0 1 1 0 1 0 1 0 代碼 B(11) A(10) E(00) D(011) C(010) 2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 23 of 42 霍夫曼編碼 — Case Study 1 (續(xù) 4) 符號(hào) 出現(xiàn)的次數(shù) log2(1/pi） 分配的代碼 需要的位數(shù) B 10 11 20 A 8 10 16 C 3 010 9 D 4 011 12 E 5 00 10 合計(jì) 30 67 30個(gè)字符組成的字符串需要 67位 5個(gè)符號(hào)的代碼 2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 24 of 42 霍夫曼編碼 — Case Study 1 (續(xù) 5) (2) 計(jì)算該字符串的熵 其中， 是事件 的集合， 并滿(mǎn)足 ? 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 ＋ 5 lg5)] / (30 log22) = ( － )/ ＝ (Sh) 1{ , , }nX x x?1( ) 1n iipx???( 1 , 2 , , )ix i n?211( ) ( ) ( ) ( ) l o g ( )nni i i iiiH X p x I x p x p x??? ? ???2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 25 of 42 霍夫曼編碼 — Case Study 1 (續(xù) 6) (3) 計(jì)算該字符串的平均碼長(zhǎng) ? 平均碼長(zhǎng)： ＝ (2 8＋ 2 10＋ 3 3＋ 3 4＋ 2 5)/30 ＝ 位 /符號(hào) 壓縮比 : 90/67=:1 1()N iiil l p l?? ? 平均碼長(zhǎng)： 67/30= (4) 計(jì)算編碼前后的壓縮比 ? 編碼前： 5個(gè)符號(hào)需 3位， 30個(gè)字符，需要 90位 ? 編碼后：共 67位 2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 26 of 42 霍夫曼編碼 — Case Study 2 ? 霍夫曼編碼舉例 2 ? 編碼前 ? N = 8 symbols: {a,b,c,d,e,f,g,h}, ? 3 bits per symbol (N =23=8) ? P(a) = , P(b)=, P(c)=, P(d)=, P(e)=, P(f)=, P(g)=, P(h)= ? 計(jì)算 (1) 該字符串的霍夫曼碼 (2) 該字符串的熵 (3) 該字符串的平均碼長(zhǎng) (4) 編碼效率 2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 27 of 42 霍夫曼編碼 — Case Study 2 (續(xù) 1) 2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 28 of 42 霍夫曼編碼 — Case Study 2 (續(xù) 2) Average length per symbol (before coding): 81 3 3 bi ts /s y m bol???? ()iL P i821 2 5 8 2 1 b i t s / s y m b o l?? ? ?? ( ) l o g ( ) .iH P i P i2 6 3 b i t s / s y m b o l? .H u fL98?/%H u fHL(2) Entropy: (3) Average length per symbol (with Huffman coding): (4) Efficiency of the code: 2021年 12月 1日 第 2章 數(shù)據(jù)無(wú)損壓縮 29 of 42 統(tǒng)計(jì)編碼 ——算術(shù)編碼 ? 算術(shù)編碼 (arithmetic co
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1