huffman霍夫曼編碼x

《huffman霍夫曼編碼x》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、4.2霍夫曼編碼霍夫曼編碼(HuffmanCoding)是一種編碼方法，霍夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。1952年，DavidA.Huffman在麻省理工攻讀博士時(shí)所提出一種編碼方法，并發(fā)表于《一種構(gòu)建極小多余編碼的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文?；舴蚵幋a介紹DavidA.Huffman該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱(chēng)之為最佳編碼，一般就叫作Huffman編碼。在計(jì)算機(jī)數(shù)據(jù)

2、處理中，霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的一個(gè)字母）進(jìn)行編碼，其中變長(zhǎng)編碼表是通過(guò)一種評(píng)估來(lái)源符號(hào)出現(xiàn)機(jī)率的方法得到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均長(zhǎng)度、期望值降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的。1951年，霍夫曼和他在MIT信息論的同學(xué)需要選擇是完成學(xué)期報(bào)告還是期末考試。導(dǎo)師Robert?M.?Fano給他們的學(xué)期報(bào)告的題目是，查找最有效的二進(jìn)制編碼。由于無(wú)法證明哪個(gè)已有編碼是最有效的，霍夫曼放棄對(duì)已有編碼的研究，轉(zhuǎn)向新的探索

3、，最終發(fā)現(xiàn)了基于有序頻率二叉樹(shù)編碼的想法，并很快證明了這個(gè)方法是最有效的。由于這個(gè)算法，學(xué)生終于青出于藍(lán)，超過(guò)了他那曾經(jīng)和信息論創(chuàng)立者克勞德·香農(nóng)共同研究過(guò)類(lèi)似編碼的導(dǎo)師。霍夫曼使用自底向上的方法構(gòu)建二叉樹(shù)，避免了次優(yōu)算法Shannon-Fano編碼的最大弊端──自頂向下構(gòu)建樹(shù)。霍夫曼（Huffman）編碼是一種統(tǒng)計(jì)編碼。屬于無(wú)損（lossless）壓縮編碼。以霍夫曼樹(shù)─即最優(yōu)二叉樹(shù)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來(lái)壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。這些

4、元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少。廣泛用在JPEG,MPEG,H.2X等各種信息編碼標(biāo)準(zhǔn)中?；舴蚵幋a的步驟霍夫曼編碼的具體步驟如下：１）將信源符號(hào)的概率按減小的順序排隊(duì)。２）把兩個(gè)最小的概率相加，并繼續(xù)這一步驟，始終將較高的概率分支放在上部，直到最后變成概率１。3）將每對(duì)組合的上邊一個(gè)指定為1，下邊一個(gè)指定為0（或相反）。４）畫(huà)出由概率１處到每個(gè)信源符號(hào)的路徑，順序記下沿路徑的０和１，所得就是該符號(hào)的霍夫曼碼字。信源熵的定義：概率空間中每個(gè)事件所含有的自信息量的數(shù)學(xué)期望稱(chēng)信源熵或簡(jiǎn)稱(chēng)

5、熵(entropy)，記為：?jiǎn)挝?以2為底的對(duì)數(shù)時(shí)是比特/符號(hào)(bit/symbol);以e為底的對(duì)數(shù)時(shí)是奈特/符號(hào)(nat/symbol);以10為底的對(duì)數(shù)時(shí)是哈特/符號(hào)(hart/symbol)其中表示某個(gè)事件xi的信息量。I(xi)=－logp(xi)平均碼長(zhǎng)編碼效率例：現(xiàn)有一個(gè)由5個(gè)不同符號(hào)組成的30個(gè)符號(hào)的字符串：BABACACADADABBCBABEBEDDABEEEBB計(jì)算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(zhǎng)H(S)=(8/30)×log2(30/8)+(1

6、0/30)×log2(30/10)+(3/30)×log2(30/3)+(4/30)×log2(30/4)+(5/30)×log2(30/5)=(44.3136－24.5592)/9.0308＝2.1874(Sh)例：平均碼長(zhǎng)：＝(2×8＋2×10＋3×3＋3×4＋2×5)/30＝2.233位/符號(hào)類(lèi)似書(shū)中例4-600001111霍夫曼編碼的主要特點(diǎn)：1.霍夫曼編碼構(gòu)造的碼字不唯一；2.霍夫曼編碼是變長(zhǎng)編碼，硬件實(shí)現(xiàn)比較困難；3.采用霍夫曼編碼，要傳送編碼表，占用傳送時(shí)間；4.霍夫曼編碼是變長(zhǎng)編

7、碼，出錯(cuò)時(shí)難以識(shí)別；霍夫曼編碼方法不唯一，因?yàn)榫幋a時(shí)的0和1是任意給的，另外在兩個(gè)符號(hào)有相同概率時(shí)的編碼過(guò)程不唯一，造成編碼結(jié)果不同，但平均碼長(zhǎng)相同。其次對(duì)信源進(jìn)行縮減時(shí)兩個(gè)概率最小的符號(hào)合并后的概率與其他信源符號(hào)的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會(huì)得到不同的霍夫曼碼此時(shí)將影響碼字的長(zhǎng)度，一般將合并的概率放在上面，這樣可以獲得較小的碼方差。霍夫曼樹(shù)1、有關(guān)霍夫曼樹(shù)的相關(guān)概念霍夫曼樹(shù)：指所有葉子結(jié)點(diǎn)的二叉樹(shù)中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從樹(shù)的根

8、節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長(zhǎng)度與該節(jié)點(diǎn)權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。2、霍夫曼算法（1）根據(jù)給定的n個(gè)權(quán)值{w1,w2,...,wn}構(gòu)造n棵二叉樹(shù)的集合F={T1,T2,...,Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均空。（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。（3）在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)