huffman霍夫曼編碼x

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

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

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

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

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

5、熵(entropy)，記為：單位:以2為底的對數(shù)時是比特/符號(bit/symbol);以e為底的對數(shù)時是奈特/符號(nat/symbol);以10為底的對數(shù)時是哈特/符號(hart/symbol)其中表示某個事件xi的信息量。I(xi)=－logp(xi)平均碼長編碼效率例：現(xiàn)有一個由5個不同符號組成的30個符號的字符串：BABACACADADABBCBABEBEDDABEEEBB計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長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)例：平均碼長：＝(2×8＋2×10＋3×3＋3×4＋2×5)/30＝2.233位/符號類似書中例4-600001111霍夫曼編碼的主要特點：1.霍夫曼編碼構(gòu)造的碼字不唯一；2.霍夫曼編碼是變長編碼，硬件實現(xiàn)比較困難；3.采用霍夫曼編碼，要傳送編碼表，占用傳送時間；4.霍夫曼編碼是變長編

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

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