《可視化計(jì)算》第6章信息論哈夫曼編碼與二叉樹(shù)A課件

第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