哈夫曼編碼基本原理是什么 哈夫曼編碼計算公式
哈夫曼編碼的工作原理,性能,應用,哈夫曼編碼的原理,Huffman編碼的基本原理是什么?哈夫曼編碼的原理,哈夫曼編碼是什么?什么赫夫曼編碼,我想知道下它的原理?
本文導航
哈夫曼編碼的簡單實例
哈夫曼編碼(Huffman Coding)是一種編碼方式,以哈夫曼樹—即最優(yōu)二叉樹,帶權(quán)路徑長度最小的二叉樹,經(jīng)常應用于數(shù)據(jù)壓縮。在計算機信息處理中,“哈夫曼編碼”是一種一致性編碼法(又稱"熵編碼法"),用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)厥獾木幋a表將源字符(例如某文件中的一個符號)進行編碼。這張編碼表的特殊之處在于,它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的(出現(xiàn)概率高的字符使用較短的編碼,反之出現(xiàn)概率低的則使用較長的編碼,這便使編碼之后的字符串的平均期望長度降低,從而達到無損壓縮數(shù)據(jù)的目的)。這種方法是由David.A.Huffman發(fā)展起來的。例如,在英文中,e的出現(xiàn)概率很高,而z的出現(xiàn)概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時,e極有可能用一個位(bit)來表示,而z則可能花去 25個位(不是26)。用普通的表示方法時,每個英文字母均占用一個字節(jié)(byte),即8個位。二者相比,e使用了一般編碼的1/8的長度,z則使用了 3倍多。倘若我們能實現(xiàn)對于英文中各個字母出現(xiàn)概率的較準確的估算,就可以大幅度提高無損壓縮的比例。
參考資料:http://baike.baidu.com/lemma-php/dispose/view.php/95311.htm
哈夫曼編碼怎么求
霍夫曼編碼的基本思想:輸入一個待編碼的串,首先統(tǒng)計串中各字符出現(xiàn)的次數(shù),稱之為頻次,假設統(tǒng)計頻次的數(shù)組為count[ ],則霍夫曼編碼每次找出count數(shù)組中的值最小的兩個分別作為左右孩子,建立他們的父節(jié)點,循環(huán)這個操作2*n-1-n(n是不同的字符數(shù))次,這樣就把霍夫曼樹建好了。建樹的過程需要注意,首先把count數(shù)組里面的n個值初始化為霍夫曼樹的n個葉子節(jié)點,他們的孩子節(jié)點的標號初始化為-1,父節(jié)點初始化為他本身的標號。接下來是編碼,每次從霍夫曼樹的葉子節(jié)點出發(fā),依次向上找,假設當前的節(jié)點標號是i,那么他的父節(jié)點必然是myHuffmantree[i].parent,如果i是myHuffmantree[i].parent的左節(jié)點,則該節(jié)點的路徑為0,如果是右節(jié)點,則該節(jié)點的路徑為1。當向上找到一個節(jié)點,他的父節(jié)點標號就是他本身,就停止(說明該節(jié)點已經(jīng)是根節(jié)點)。還有一個需要注意的地方:在查找當前權(quán)值最小的兩個節(jié)點時,那些父節(jié)點不是他本身的節(jié)點不能考慮進去,因為這些節(jié)點已經(jīng)被處理過了
軟件編碼原理學習
構(gòu)造最優(yōu)二叉樹就是其原理。最優(yōu)二叉樹:假設有n個權(quán)值{w1,w2,...,wn},試構(gòu)造一顆又n個葉子結(jié)點的二叉樹,每個葉子結(jié)點帶權(quán)為wi,則其中帶權(quán)路徑長度WPL最小的二叉樹稱作最優(yōu)二叉樹,也叫赫夫曼樹。具體請看數(shù)據(jù)結(jié)構(gòu)相關(guān)書籍。希望這個解釋對你有用,祝你學習進步~!
哈夫曼編碼計算公式
設某信源產(chǎn)生有五種符號u1、u2、u3、u4和u5,對應概率P1=0.4,P2=0.1,P3=P4=0.2,P5=0.1。首先,將符號按照概率由大到小排隊,如圖所示。編碼時,從最小概率的兩個符號開始,可選其中一個支 路為0,另一支路為1。這里,我們選上支路為0,下支路為1。再將已編碼的兩支路的概率合并,并重新排隊。多次重復使用上述方法直至合并概率歸一時為止。從圖(a)和(b)可以看出,兩者雖平均碼長相等,但同一符號可以有不同的碼長,即編碼方法并不唯一,其原因是兩支路概率合并后重新排隊時,可能出現(xiàn)幾個支路概率相等,造成排隊方法不唯一。一般,若將新合并后的支路排到等概率的最上支路,將有利于縮短碼長方差,且編出的碼更接近于等長碼。這里圖(a)的編碼比(b)好。赫夫曼碼的碼字(各符號的代碼是異前置碼字,即任一碼字不會是另一碼宇的前面部分,這使各碼字可以連在一起傳送,中間不需另加隔離符號,只要傳送時不出錯,收端仍可分離各個碼字,不致混淆。實際應用中,除采用定時清洗以消除誤差擴散和采用緩沖存儲以解決速率匹配以外,主要問題是解決小符號集合的統(tǒng)計匹配,例如黑(1)、白(0)傳真信源的統(tǒng)計匹配,采用0和1不同長度游程組成擴大的符號集合信源。游程,指相同碼元的長度(如二進碼中連續(xù)的一串0或一串1的長度或個數(shù))。按照CCITT標準,需要統(tǒng)計2×1728種游程(長度),這樣,實現(xiàn)時的存儲量太大。事實上長游程的概率很小,故CCITT還規(guī)定:若l表示游程長度,則l=64q+r。其中q稱主碼,r為基碼。編碼時,不小于64的游程長度由主碼和基碼組成。而當l為64的整數(shù)倍時,只用主碼的代碼,已不存在基碼的代碼。長游程的主碼和基碼均用赫夫曼規(guī)則進行編碼,這稱為修正赫夫曼碼,其結(jié)果有表可查。該方法已廣泛應用于文件傳真機中。
哈夫曼編碼的具體實例
哈夫曼編碼是在哈夫曼樹的基礎上進行的,其編碼步驟為:
(1)利用字符集中每個字符的使用頻率作為權(quán)值構(gòu)造一個哈夫曼樹,并在葉子結(jié)點上注明對應的字符。
(2)在樹中從根結(jié)點到葉子結(jié)點都有一條路徑,對路徑上的各分支約定指向左子樹根的分支表示“0”碼,指向右子樹的分支表示“1”碼。
(2)取從根到每個葉子上的“0”或“1”的序列作為各個葉子結(jié)點(字符)的編碼。
怎樣判斷哪些是哈夫曼編碼
1、是一種利用二叉樹實現(xiàn)的編碼原理
霍夫曼(Huffman)編碼原理
霍夫曼(Huffman)編碼是1952年為文本文件而建立,是一種統(tǒng)計編碼。屬于無損壓縮編碼。
霍夫曼編碼的碼長是變化的,對于出現(xiàn)頻率高的信息,編碼的長度較短;而對于出現(xiàn)頻率低的信息,編碼長度較長。這樣,處理全部信息的總碼長一定小于實際信息的符號長度。
步驟進行:
l)將信號源的符號按照出現(xiàn)概率遞減的順序排列。
2)將兩個最小出現(xiàn)概率進行合并相加,得到的結(jié)果作為新符號的出現(xiàn)概率。
3)重復進行步驟1和2直到概率相加的結(jié)果等于1為止。
4)在合并運算時,概率大的符號用編碼0表示,概率小的符號用編碼1表示。
5)記錄下概率為1處到當前信號源符號之間的0,l序列,從而得到每個符號的編碼。
例:
設信號源為
s={s1,
s2,
s3,
s4,
s5}
對應的概率為p={0.25,0.22,0.20,
0.18,0.15}。
根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的異字頭碼字。
霍未曼編碼通常采用兩次掃描的辦法,第一次掃描得到統(tǒng)計結(jié)果,第二次掃描進行編碼。
霍夫曼編碼具有一些明顯的特點:
1)
編出來的碼都是異字頭碼,保證了碼的唯一可譯性。
2)
由于編碼長度可變。因此譯碼時間較長,使得霍夫曼編碼的壓縮與還原相當費時。
3)
編碼長度不統(tǒng)一,硬件實現(xiàn)有難度。
4)
對不同信號源的編碼效率不同,當信號源的符號概率為2的負冪次方時,達到100%的編碼效率;若信號源符號的概率相等,則編碼效率最低。
5)
由于"0"與"1"的指定是任意的,故由上述過程編出的最佳碼不是唯一的,但其平均碼長是一樣的,故不影響編碼效率與數(shù)據(jù)壓縮性能
2、都差不多,個人感覺c++更好學
掃描二維碼推送至手機訪問。
版權(quán)聲明:本文由尚恩教育網(wǎng)發(fā)布,如需轉(zhuǎn)載請注明出處。