可視化計(jì)算第6章信息論哈夫曼編碼與二叉樹a-wenkub.com
2025-05-10 01:26 本頁面
【正文】 如何編碼，可以使編碼最短？ 池塘狀態(tài) 平靜 青蛙叫 蛤蟆叫 青蛙和蛤蟆叫 概率 24 利用熵求最優(yōu)編碼 ? 定長(zhǎng)編碼，需要 兩個(gè)二進(jìn)制位 ； ? 變長(zhǎng)編碼：給小概率消息較長(zhǎng)的編碼，給大小概率消息較短的編碼； ? 因?yàn)?，隨機(jī)變量 X服從概率分布 P時(shí)，如果消息x的分布密度為 p（ x） ,則給其分配一個(gè)長(zhǎng)度為[log2p(x)]個(gè)二進(jìn)制位的編碼 ? 則發(fā)送一個(gè)消息平均需要 ∑ p(x)log2p(x)個(gè)二進(jìn)制位 ? 所以，有變長(zhǎng)的編碼規(guī)則如下： 25 利用熵求最優(yōu)編碼 (3) 消息 編碼 平靜 0 青蛙叫 110 蛤蟆叫 111 青蛙和蛤蟆一起叫 10 編碼的平均長(zhǎng)度為： ∑p(x)log2p(x)=*1+*3+*3+*2 = 26 基亍有序頻率二叉樹編碼 ? 1951年哈夫曼和他在 MIT信息論課程的同學(xué)需要選擇是完成學(xué)期報(bào)告還是期末考試； ? 導(dǎo)師 Robert M. Fano給他們的學(xué)期報(bào)告的題目是，尋找最有效的二進(jìn)制編碼 ? 最終發(fā)現(xiàn)了基于有序頻率二叉樹（也稱為最優(yōu)二叉樹）編碼的想法 27 最優(yōu)二叉樹概念 ? 1．樹的路徑長(zhǎng)度 ? 從樹根到樹中每一節(jié)點(diǎn)的路徑長(zhǎng)度之和 ? 2．樹的帶權(quán)路徑長(zhǎng)度 (Weighted Path Length of Tree， WPL) ? 節(jié)點(diǎn)的權(quán)：在一些應(yīng)用中，賦予樹中節(jié)點(diǎn)的一個(gè)有某種意義的實(shí)數(shù) (例如編碼值 ) ? 節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：節(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與該節(jié)點(diǎn)上權(quán)的乘積 28 最優(yōu)二叉樹概念 ? 樹的帶權(quán)路徑長(zhǎng)度：定義為樹中所有葉節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為： iniilwW P L ???1 其中： n表示葉子節(jié)點(diǎn)的數(shù)目 wi和 li分別表示葉節(jié)點(diǎn) ki的權(quán)值和根到節(jié)點(diǎn) ki之間的路徑長(zhǎng)度 樹的帶權(quán)路徑長(zhǎng)度亦稱為樹的代價(jià) 29 最優(yōu)二叉樹或哈夫曼樹 ? 在權(quán)為 wl， w2， ? ， wn的 n個(gè)葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長(zhǎng)度最小 (即代價(jià)最小 )的二叉樹稱為 最優(yōu)二叉樹 (a)WPL=7*2+5*2+2*2+4*2=36
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1