《可視化計(jì)算》第6章信息論哈夫曼編碼與二叉樹(shù)A課件_第1頁(yè)
《可視化計(jì)算》第6章信息論哈夫曼編碼與二叉樹(shù)A課件_第2頁(yè)
《可視化計(jì)算》第6章信息論哈夫曼編碼與二叉樹(shù)A課件_第3頁(yè)
《可視化計(jì)算》第6章信息論哈夫曼編碼與二叉樹(shù)A課件_第4頁(yè)
《可視化計(jì)算》第6章信息論哈夫曼編碼與二叉樹(shù)A課件_第5頁(yè)
已閱讀5頁(yè),還剩40頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第6章信息論、哈夫曼編碼與二叉樹(shù)

PARTA《可視化計(jì)算》1學(xué)習(xí)目標(biāo)什么是信息論中的信息?如何使用二進(jìn)制編碼進(jìn)行表達(dá)信息?如何計(jì)算編碼的信息量?為什么哈夫曼編碼是最優(yōu)編碼?如何使用二叉樹(shù)進(jìn)行編碼設(shè)計(jì)?常見(jiàn)的樹(shù)結(jié)構(gòu)的算法有哪些?2信息與信息論信息的應(yīng)用非常廣泛,定義在不同的領(lǐng)域,也有不同,例如,在管理信息系統(tǒng)中:Byinformationwemeandatathathavebeenshapedintoaformthatismeaningfulandusefultohumanbeings但是在計(jì)算機(jī)和通信領(lǐng)域:1948年,美國(guó)數(shù)學(xué)家、信息論的創(chuàng)始人仙農(nóng)在題為“通訊的數(shù)學(xué)理論”的論文中指出:“信息是用來(lái)消除隨機(jī)不定性的東西”

3一個(gè)燈籠的故事5改進(jìn)的報(bào)警方案62的冪次和可表達(dá)的信息單元7反向思維如果知道要傳送的消息個(gè)數(shù),怎樣知道需要的最少比特?cái)?shù)?如果需要報(bào)信的內(nèi)容是一年內(nèi)可能發(fā)生進(jìn)攻的月份,需要多少燈籠?9數(shù)字表達(dá)如果民兵希望發(fā)送英軍中先頭部隊(duì)數(shù)量的消息時(shí)怎么辦?假設(shè)教堂中的報(bào)信人知道英軍先頭部隊(duì)有50個(gè)連,我們知道可以用不到50個(gè)燈籠來(lái)表達(dá)這種消息信息論告訴我們,民兵只要使用六個(gè)燈籠就可以表達(dá)英軍50個(gè)連進(jìn)攻的消息但要傳送這個(gè)消息,哪些燈籠要打開(kāi),哪些要關(guān)閉呢?10用燈籠來(lái)表示5011ASCII碼表13熵與信息量著名的美國(guó)數(shù)學(xué)家ClaudeShannon在1948年定義“熵”來(lái)表達(dá)消息的信息量消息的信息量是一個(gè)非常有意思的概念,取決于我們對(duì)此消息已知的內(nèi)容有時(shí),我們只要問(wèn)一個(gè)問(wèn)題,就消除了再問(wèn)的必要性,這種情況下,消息所含的信息量就很低14猜、猜、猜如果你的朋友問(wèn)你:“猜猜我今天是怎么到學(xué)校的?”,你一定可以很容易的一下猜到,騎車而如果他是坐直升飛機(jī)來(lái)的?而如果他是坐宇宙飛船來(lái)的?猜測(cè)次數(shù)的多少,意味著“信息不確定性”的程度,越是難猜的信息,包含的信息值越大15哪支球隊(duì)是冠軍可以把球隊(duì)編上號(hào),從1到32,猜/答一次,付錢一元然后提問(wèn):“冠軍的球隊(duì)在1-16號(hào)中嗎?”假如他告訴我猜對(duì)了我會(huì)接著問(wèn):“冠軍在1-8號(hào)中嗎?”假如他告訴我猜錯(cuò)了,我自然知道冠軍隊(duì)在9-16中這樣只需要五次,我就能知道哪支球隊(duì)是冠軍。所以,誰(shuí)是世界杯冠軍這條消息的信息量只值五塊錢17如何少猜幾次信息量使用比特?cái)?shù)計(jì)量并和所有可能情況的對(duì)數(shù)函數(shù)log有關(guān)log232=5log264=6(64支參賽隊(duì))實(shí)際上象巴西、德國(guó)、意大利這樣的球隊(duì)得冠軍的可能性比日本、美國(guó)、韓國(guó)等隊(duì)大的多因此,當(dāng)每個(gè)球隊(duì)奪冠的可能性(概率)不等時(shí),“誰(shuí)世界杯冠軍”的信息量實(shí)際比五比特少18實(shí)際上的信息量香農(nóng)指出,它的準(zhǔn)確信息量應(yīng)該是:

-(p1×logp1+p2×logp2+...+p32×logp32)其中,p1,p2,...,p32分別是這32個(gè)球隊(duì)奪冠的概率香農(nóng)把它稱為“信息熵”(Entropy),一般用符號(hào)H表示,單位是比特19熵的定義設(shè)隨機(jī)變量X,取值空間Ω,Ω為有限集合;X的分布密度為p(x),p(x)=P(X=x),x∈X,則該隨機(jī)變量的取值不確定程度,即其熵為:當(dāng)使用log2時(shí),熵的單位為比特反映一個(gè)信源發(fā)出不同信號(hào),具有的平均信息量21利用信息論進(jìn)行編碼分析(1)計(jì)算英文字符(26字母加空格)為信息源的熵:設(shè)所有字符等概率出現(xiàn):

H(X)=-∑p(x)log2p(x){x∈X}

=27*{-1/27log21/27}

=log227

=4.75(bits/Letter)22利用信息論進(jìn)行編碼分析(2)假設(shè)英文字符的概率分布如下表:解:H(X)=-∑p(xi)log2p(xi){i=1~27}

≈4.02(bits/Letter)說(shuō)明:考慮英文字符和空格實(shí)際出現(xiàn)的概率后,英文信源的平均不確定性,比把字符和空格看作等概率的情況要小23利用熵求最優(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)=0.5*1+0.125*3+0.125*3+0.25*2=1.75比特26最優(yōu)二叉樹(shù)概念樹(shù)的帶權(quán)路徑長(zhǎng)度:定義為樹(shù)中所有葉節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和,通常記為:

其中:

n表示葉子節(jié)點(diǎn)的數(shù)目

wi和li分別表示葉節(jié)點(diǎn)ki的權(quán)值和根到節(jié)點(diǎn)ki之間的路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度亦稱為樹(shù)的代價(jià)29最優(yōu)二叉樹(shù)或哈夫曼樹(shù)在權(quán)為wl,w2,…,wn的n個(gè)葉子所構(gòu)成的所有二叉樹(shù)中,帶權(quán)路徑長(zhǎng)度最小(即代價(jià)最小)的二叉樹(shù)稱為最優(yōu)二叉樹(shù)(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4*3=3530構(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例6-5:請(qǐng)編制哈夫曼編碼一串信號(hào)源S={Z,K,F(xiàn),C,U,D,L,E}對(duì)應(yīng)頻率為p={2,7,24,32,37,42,42,120}32例6-5:請(qǐng)編制哈夫曼編碼E=0U=100D=101L=110C=1110Z=111100K=111101F=11111每一碼不會(huì)是另一碼的前綴,譯碼時(shí)可惟一復(fù)原

33使用RAPTOR產(chǎn)生哈夫曼編碼1、編碼的數(shù)據(jù)的準(zhǔn)備:基本數(shù)據(jù),通過(guò)文件(code_frequence.csv)輸入給算法,并按以下字母、頻率對(duì)的形式排列:“Z,2,K,7,F(xiàn),24,C,32,U,37,D,42,L,42,E,120”34使用RAPTOR產(chǎn)生哈夫曼編碼2、主要數(shù)據(jù)結(jié)構(gòu):使用binlist數(shù)組保存帶權(quán)二叉樹(shù)元素序號(hào)123456作用節(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子圖:用于尋找當(dāng)前asslist中保存的最小權(quán)重的節(jié)點(diǎn);Incode子程序:用于帶權(quán)二叉樹(shù)建立完成后,進(jìn)行各個(gè)原始碼的二進(jìn)制編碼的編制;Ou

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論