奇妙的二叉樹(編輯修改稿)
2024-10-24 19:17 本頁面
【文章內(nèi)容簡介】 的編碼表： a 00 b 01 c 10 d 110 e – 111 ?可以將例子中的信息編碼為：cabcedeacacdeddaaabaababaaabbacdebaceada 10 00 01 10 111 110 111 00 10 00 10 ...... ?碼長共 91 位?？紤]用 ASCII 碼表示上述信息需要 8 * 40 = 320 位，我們確實(shí)實(shí)現(xiàn)了數(shù)據(jù)壓縮。 Huffman 編碼 ?Huffman 編碼構(gòu)造二叉樹的方法和 ShannonFano 正好相反，不是自上而下，而是從樹葉到樹根生成二叉樹?，F(xiàn)在，我們?nèi)匀皇褂蒙厦娴睦觼韺W(xué)習(xí) Huffman 編碼方法。 ? 1) 將各個(gè)符號(hào)及其出現(xiàn)頻率分別作為不同的小二叉樹 （ 目前每棵樹只有根節(jié)點(diǎn) ） 。 a(16) b(7) c(6) d(6) e(5) ? 2) 在 1) 中得到的樹林里找出頻率值最小的兩棵樹 ， 將他們分別作為左 、 右子樹連成一棵大一些的二叉樹 ， 該二叉樹的頻率值為兩棵子樹頻率值之和 。 對(duì)上面的例子 ， 我們得到一個(gè)新的樹林： d e ?3) 對(duì)上面得到的樹林重復(fù) 2 的做法，直到所有符號(hào)都連入樹中為止。這一步完成后，我們有這樣的二叉樹： 根（ root） 0 0 0 a(16) 1 1 1 c(6) 1 b(7) e(5) d(6) 0 (11) (13) (24) (40) ?由此，我們可以建立和 ShannonFano 編碼略微不同的編碼表： a 0 b
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1