可視化計(jì)算第6章信息論哈夫曼編碼與二叉樹(shù)a-wenkub
2023-05-28 01:26:14 本頁(yè)面
【正文】 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4*3=35 30 構(gòu)造 Huffman樹(shù) ? l）將信號(hào)源的符號(hào)按照出現(xiàn)概率遞減的順序排列2）將最下面的兩個(gè)最小出現(xiàn)概率進(jìn)行合并相加，得到的結(jié)果作為新符號(hào)的出現(xiàn)概率 ? 3）重復(fù)進(jìn)行步驟 1和 2直到概率相加的結(jié)果等于 1為止 ? 4）在合并運(yùn)算時(shí)，概率大的符號(hào)用編碼 0表示，概率小的符號(hào)用編碼 1表示 ? 5）記錄下概率為 1處到當(dāng)前信號(hào)源符號(hào)之間的 0，l序列，從而得到每個(gè)符號(hào)的編碼 31 例 65：請(qǐng)編制哈夫曼編碼 ? 一串信號(hào)源 S＝ {Z， K， F， C， U， D， L， E}對(duì)應(yīng)頻率為 p＝ {2， 7， 24， 32， 37， 42， 42， 120} 32 例 65：請(qǐng)編制哈夫曼編碼 ? E=0 ? U=100 ? D=101 ? L=110 ? C=1110 ? Z=111100 ? K=111101 ? F=11111 每一碼不會(huì)是另一碼的前綴， 譯碼時(shí)可惟一復(fù)原 33 使用 RAPTOR產(chǎn)生哈夫曼編碼 ? 編碼的數(shù)據(jù)的準(zhǔn)備： 基本數(shù)據(jù)，通過(guò)文件 ()輸入給算法，并按以下字母、頻率對(duì)的形式排列： “ Z， 2， K， 7， F， 24， C， 32， U， 37， D， 42， L， 42， E， 120” 34 使用 RAPTOR產(chǎn)生哈夫曼編碼 ? 主要數(shù)據(jù)結(jié)構(gòu)： ? 使用 binlist數(shù)組保存帶權(quán)二叉樹(shù) 元素序號(hào) 1 2 3 4 5 6 作用 節(jié)點(diǎn)名 左子 右子 代碼 頻率 父節(jié)點(diǎn) ?作為葉子的 8個(gè)節(jié)點(diǎn)在代碼字段，具有原始代碼的值，其他節(jié)點(diǎn)則沒(méi)有； ?所有葉子節(jié)點(diǎn)的左子，右子字段為空，用“ 0”表示 35 哈夫曼編碼 main子圖 36 主要子圖和子程序 ? Init子圖： binlist、 asslist數(shù)組初始化，從文件讀入編碼需要的基本數(shù)據(jù)； ? Build_huffman_tree子圖： 使用哈夫曼編碼的原理，進(jìn)行建立帶權(quán)二叉樹(shù)； ? Twochild子圖：找出當(dāng)前新建節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn) ? Findmin子圖：用于尋找
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1