哈夫曼編碼基本原理是什么 哈夫曼編碼計(jì)算公式

哈夫曼編碼的工作原理，性能，應(yīng)用，哈夫曼編碼的原理，Huffman編碼的基本原理是什么？哈夫曼編碼的原理，哈夫曼編碼是什么？什么赫夫曼編碼,我想知道下它的原理？

本文導(dǎo)航

• 哈夫曼編碼的簡單實(shí)例
• 哈夫曼編碼怎么求
• 軟件編碼原理學(xué)習(xí)
• 哈夫曼編碼計(jì)算公式
• 哈夫曼編碼的具體實(shí)例
• 怎樣判斷哪些是哈夫曼編碼

哈夫曼編碼的簡單實(shí)例

哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(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)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達(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的長度，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)路徑長度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）可以看出，兩者雖平均碼長相等，但同一符號(hào)可以有不同的碼長，即編碼方法并不唯一，其原因是兩支路概率合并后重新排隊(duì)時(shí)，可能出現(xiàn)幾個(gè)支路概率相等，造成排隊(duì)方法不唯一。一般，若將新合并后的支路排到等概率的最上支路，將有利于縮短碼長方差，且編出的碼更接近于等長碼。這里圖（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不同長度游程組成擴(kuò)大的符號(hào)集合信源。游程，指相同碼元的長度（如二進(jìn)碼中連續(xù)的一串0或一串1的長度或個(gè)數(shù)）。按照CCITT標(biāo)準(zhǔn)，需要統(tǒng)計(jì)2×1728種游程（長度），這樣，實(shí)現(xiàn)時(shí)的存儲(chǔ)量太大。事實(shí)上長游程的概率很小，故CCITT還規(guī)定：若l表示游程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時(shí)，不小于64的游程長度由主碼和基碼組成。而當(dāng)l為64的整數(shù)倍時(shí)，只用主碼的代碼，已不存在基碼的代碼。長游程的主碼和基碼均用赫夫曼規(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ì)編碼。屬于無損壓縮編碼。

霍夫曼編碼的碼長是變化的，對(duì)于出現(xiàn)頻率高的信息，編碼的長度較短；而對(duì)于出現(xiàn)頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實(shí)際信息的符號(hào)長度。

步驟進(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)造平均長度最短的異字頭碼字。

霍未曼編碼通常采用兩次掃描的辦法，第一次掃描得到統(tǒng)計(jì)結(jié)果，第二次掃描進(jìn)行編碼。

霍夫曼編碼具有一些明顯的特點(diǎn)：

1)

編出來的碼都是異字頭碼，保證了碼的唯一可譯性。

2)

由于編碼長度可變。因此譯碼時(shí)間較長，使得霍夫曼編碼的壓縮與還原相當(dāng)費(fèi)時(shí)。

3)

編碼長度不統(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"的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能

2、都差不多，個(gè)人感覺c++更好學(xué)