如何建立哈夫曼樹(shù)?假設(shè)n個(gè)權(quán)重,構(gòu)造的哈夫曼樹(shù)有n個(gè)葉節(jié)點(diǎn)。將N個(gè)權(quán)值設(shè)為K1,K2,則哈夫曼樹(shù)的構(gòu)造規(guī)則為:(1)將K1,k2kn看作一個(gè)有N棵樹(shù)的森林(每棵樹(shù)只有一個(gè)節(jié)點(diǎn));(2)在森林中,選擇兩棵根節(jié)點(diǎn)權(quán)值最小的樹(shù)并合并為一棵新樹(shù)的左、右子樹(shù),新樹(shù)的根節(jié)點(diǎn)的權(quán)重是左右子樹(shù)的權(quán)重之和;(3)從林中刪除選中的兩棵樹(shù),并將新樹(shù)添加到林中;(4)重復(fù)步驟(2)和(3),直到林中只剩下一棵樹(shù),該樹(shù)就是得到的哈夫曼樹(shù)。哈夫曼靜態(tài)編碼:對(duì)要編碼的數(shù)據(jù)進(jìn)行兩次掃描:第一次對(duì)原始數(shù)據(jù)中每個(gè)字符的頻率進(jìn)行計(jì)數(shù),用頻率值創(chuàng)建一棵哈夫曼樹(shù),并且必須保存樹(shù)的信息,即按2-4字節(jié)的長(zhǎng)度順序存儲(chǔ)字符0-255(2^8=256)的頻率值,(存儲(chǔ)長(zhǎng)度為4字節(jié)的頻率值,頻率值的表示)為了創(chuàng)建用于解壓縮的相同哈夫曼樹(shù),第二遍對(duì)從第一遍掃描獲得的哈夫曼樹(shù)進(jìn)行編碼并存儲(chǔ)編碼的碼字。哈夫曼動(dòng)態(tài)編碼:動(dòng)態(tài)哈夫曼編碼使用一個(gè)動(dòng)態(tài)哈夫曼樹(shù)對(duì)一個(gè)字符進(jìn)行編碼是基于哈夫曼樹(shù)從原始數(shù)據(jù)的前t個(gè)字符中獲得。編碼和解碼使用相同的初始哈夫曼樹(shù)。每個(gè)字符經(jīng)過(guò)處理后,編碼和解碼采用相同的方法修改哈夫曼樹(shù),因此不需要保存哈夫曼樹(shù)信息進(jìn)行解碼。編碼和解碼字符所需的時(shí)間與字符的長(zhǎng)度成正比,因此可以實(shí)時(shí)地進(jìn)行動(dòng)態(tài)哈夫曼編碼。

如何實(shí)現(xiàn)哈夫曼樹(shù)?
分享標(biāo)題:哈夫曼樹(shù)怎么建立如何建立哈夫曼樹(shù)?-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明:http://www.chinadenli.net/article8/gchop.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供虛擬主機(jī)、App開(kāi)發(fā)、網(wǎng)站導(dǎo)航、關(guān)鍵詞優(yōu)化、品牌網(wǎng)站制作、手機(jī)網(wǎng)站建設(shè)
廣告
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源:
創(chuàng)新互聯(lián)