離散數(shù)學(xué)第8章圖論8樹(shù)(編輯修改稿)
2025-02-12 20:15 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 +5*2+2*2+4*2=36 (b) W(T)= =7*3+5*3+2*1+4*2=46 (c) W(T)= =7*1+5*2+2*3+4*3=35 其中 (c)樹(shù)的 W最小，它就是 最優(yōu)二叉樹(shù) (哈夫曼樹(shù) ) 。 18 返回 結(jié)束 幾類常用樹(shù) ? Huffman樹(shù) [Huffman 算法 ] 給定 t個(gè)非負(fù)實(shí)數(shù)，構(gòu)造以它們?yōu)槿~子帶權(quán)且具有最小M(T) 的最優(yōu)二叉樹(shù)。 (1) i ? t； (2) 若 i =1 結(jié)束； (3) 將 i 個(gè)非負(fù)實(shí)數(shù)權(quán)由小到大排列成序，以最小的兩個(gè)數(shù)作為左右兒子，構(gòu)造其父親結(jié)點(diǎn)，并以此左右兒子的權(quán)值之和作為新構(gòu)造的父親結(jié)點(diǎn)的權(quán)值。在權(quán)序列中刪去此左右兒子對(duì)應(yīng)的權(quán)值，增加新構(gòu)造的父親結(jié)點(diǎn)的權(quán)值。 (4) i ? i1 ， 轉(zhuǎn) (2)。 19 返回 結(jié)束 幾類常用樹(shù) ? 例：有 4個(gè)權(quán)值 {7,5,2,4}，試構(gòu)造一棵有 4個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)。 20 返回 結(jié)束 幾類常用樹(shù) [Huffman樹(shù) ] 由 Huffman算法構(gòu)造的二叉樹(shù)稱為相對(duì)于非負(fù)實(shí)數(shù)權(quán) wi (i=1,2,…, t) 的Huffman樹(shù)。 [定理 ] Huffman樹(shù)是一棵相對(duì)于非負(fù)實(shí)數(shù)權(quán) wi (i=1,2,…, t) 的最優(yōu)二叉樹(shù)。 21 返回 結(jié)束 幾類常用樹(shù) 定義 ： 有一個(gè)序列的集合，如果在這個(gè)集合中。任何序列都不是另一個(gè)序列的前綴，則稱這個(gè)集合為 前綴碼 。 ? 例如， 001是 001011的前綴，集合{000,001,01,10,11}是前綴碼，而{1,00,01,000,0001}不是前綴碼。 [二元前綴碼 ]前綴碼 A={?1, ?2, … , ?m }中的 ?i 只由兩種符號(hào)（如 0、 1）組成時(shí)，稱 A為一個(gè)二元 前綴碼。 22 返回 結(jié)束 幾類常用樹(shù) ? 對(duì)有序二叉樹(shù)的頂點(diǎn)編碼如下： ?(1)根不標(biāo)碼； ?(2)兄弟有序，左為兄，標(biāo) 0，右為弟，標(biāo) 1； ?(3)從根始到葉上的道路依次抄出各點(diǎn)之碼，寫在葉下方，稱 該葉的前綴 ； ?(4)全樹(shù)的葉從左到有把它們的前綴依次抄出，叫做 該樹(shù)的前綴碼 ，每個(gè)葉子的前綴后加逗號(hào)，最后一個(gè)葉子前綴后加句號(hào)。 ?顯然有序二叉樹(shù)與前綴碼一一對(duì)應(yīng)。 23 返回 結(jié)束 幾類常用樹(shù) ? 例如， 0000， 0001， 001， 010， 011， 100，101， 11這一前綴碼對(duì)應(yīng)的有序二叉樹(shù)如下圖所示： v0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0000 0001 001 010 011 100 101 11 24 返回 結(jié)束 幾類常用樹(shù) [Huffman編碼 ] 以各個(gè)源碼符號(hào)在源碼電文中出現(xiàn)的頻率為權(quán)值，構(gòu)造以源碼符號(hào)為葉子的 Huffman樹(shù)，得到關(guān)于源碼符號(hào)集的一個(gè)二叉前綴碼，稱為其 Huffman編碼。 [定理 ] Huffman編碼是關(guān)于該源碼符號(hào)集的最短二叉前綴碼。 [證明 ] 略 25 返回 結(jié)束 幾類常用樹(shù) ? 實(shí)現(xiàn)譯文長(zhǎng)度最短的二叉前綴碼設(shè)計(jì)過(guò)程： 1. 字頻統(tǒng)計(jì) 2. 等概率假設(shè) 3. Huffman樹(shù)構(gòu)造 4. Huffman編碼方案確定 [例 ] 設(shè)一段電文含有 x1,x2,x3,x4,x5,x6,x7共 7個(gè)符號(hào)，它們出現(xiàn)的頻率分別是： x1: 35% x2: 20% x3: 15% x4:10 x5: 10% x6:5% x7:5%。試為這 7個(gè)符號(hào)設(shè)計(jì)一套最短二叉前綴編碼方案。 26 返回 結(jié)束 幾類常用樹(shù)
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1