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