哈夫曼編碼怎么算，哈夫曼編碼算法

來(lái)源：整理時(shí)間：2023-08-26 02:15:39 編輯：智能門(mén)戶(hù) 手機(jī)版

本文目錄一覽

1，哈夫曼編碼算法
2，赫夫曼編碼后將結(jié)果以二進(jìn)制形式存入文件即0 1 的信息用比特
3，什么是哈夫曼編碼和譯碼
4，哈夫曼樹(shù)的構(gòu)建過(guò)程
5，什么是霍夫曼編碼
6，霍夫曼樹(shù)和霍夫曼編碼trcpy怎么定義

1，哈夫曼編碼算法

因?yàn)槠渲幸粋€(gè)不能是另一個(gè)的前綴所以只能是1111、1110、1101、1100

哈夫曼編碼算法

2，赫夫曼編碼后將結(jié)果以二進(jìn)制形式存入文件即0 1 的信息用比特

首先赫夫曼編碼你要會(huì)寫(xiě). 假如寫(xiě)出來(lái)后 a 0b 10c 110d 111那么用比特表示 (寫(xiě)入二進(jìn)制)a 寫(xiě)入 0 b 寫(xiě)入 2 c寫(xiě)入 6d 寫(xiě)入 7

赫夫曼編碼后將結(jié)果以二進(jìn)制形式存入文件即0 1 的信息用比特

3，什么是哈夫曼編碼和譯碼

哈夫曼編碼http://baike.baidu.com/view/95311.htm譯碼http://baike.baidu.com/view/189742.htm

什么是哈夫曼編碼和譯碼

4，哈夫曼樹(shù)的構(gòu)建過(guò)程

哈夫曼樹(shù):給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman tree)。哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近。哈夫曼樹(shù)的構(gòu)造：假設(shè)給定的權(quán)值如下：3,5,7,8,10,15；首先取集合中最小的兩個(gè)數(shù)：3+5=8，再刪除集合中3和5的值，把8放入原集合,原集合變成:7,8,8,10,15； 8 / \ 3 5再?gòu)?,8,8,10,15中再取2個(gè)最小的數(shù)構(gòu)成一個(gè)樹(shù) 15 / \ 8 7 / \ 3 5再?gòu)?,10,15,15中再取2個(gè)最小的數(shù)構(gòu)成一個(gè)樹(shù): 18 / \ 8 10再?gòu)?5,15,18中取兩個(gè)最小數(shù):15,15,構(gòu)成樹(shù): 30 / \ 15 15 / \ 8 7 / \ 3 5最后把18,30構(gòu)成樹(shù)(此時(shí)集合中已經(jīng)沒(méi)元素了，就形成了哈夫曼樹(shù)): 48 / \ 30 18 / \ / \ 15 15 8 10 / \ 8 7 / \ 3 5希望你能看懂??！

5，什么是霍夫曼編碼

霍夫曼（Huffman）編碼原理霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統(tǒng)計(jì)編碼。屬于無(wú)損壓縮編碼。霍夫曼編碼的碼長(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)的概率來(lái)構(gòu)造平均長(zhǎng)度最短的異字頭碼字?；粑绰幋a通常采用兩次掃描的辦法，第一次掃描得到統(tǒng)計(jì)結(jié)果，第二次掃描進(jìn)行編碼?；舴蚵幋a具有一些明顯的特點(diǎn)：1) 編出來(lái)的碼都是異字頭碼，保證了碼的唯一可譯性。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"的指定是任意的，故由上述過(guò)程編出的最佳碼不是唯一的，但其平均碼長(zhǎng)是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能。

6，霍夫曼樹(shù)和霍夫曼編碼trcpy怎么定義

一、哈夫曼樹(shù)的概念和定義什么是哈夫曼樹(shù)？讓我們先舉一個(gè)例子。判定樹(shù)：在很多問(wèn)題的處理過(guò)程中，需要進(jìn)行大量的條件判斷，這些判斷結(jié)構(gòu)的設(shè)計(jì)直接影響著程序的執(zhí)行效率。例如，編制一個(gè)程序，將百分制轉(zhuǎn)換成五個(gè)等級(jí)輸出。大家可能認(rèn)為這個(gè)程序很簡(jiǎn)單，并且很快就可以用下列形式編寫(xiě)出來(lái)：[cpp] view plain copyif(score<60) cout<<"Bad"<<endl; else if(score<70) cout<<"Pass"<<endl else if(score<80) cout<<"General"<<endl; else if(score<90) cout<<"Good"<<endl; else cout<<"Very good!"<<endl; [cpp] view plain copyif(score<60) cout<<"Bad"<<endl; else if(score<70) cout<<"Pass"<<endl else if(score<80) cout<<"General"<<endl; else if(score<90) cout<<"Good"<<endl; else cout<<"Very good!"<<endl; 若考慮上述程序所耗費(fèi)的時(shí)間，就會(huì)發(fā)現(xiàn)該程序的缺陷。在實(shí)際中，學(xué)生成績(jī)?cè)谖鍌€(gè)等級(jí)上的分布是不均勻的。當(dāng)學(xué)生百分制成績(jī)的錄入量很大時(shí)，上述判定過(guò)程需要反復(fù)調(diào)用，此時(shí)程序的執(zhí)行效率將成為一個(gè)嚴(yán)重問(wèn)題。但在實(shí)際應(yīng)用中，往往各個(gè)分?jǐn)?shù)段的分布并不是均勻的。下面就是在一次考試中某門(mén)課程的各分?jǐn)?shù)段的分布情況：下面我們就利用哈夫曼樹(shù)尋找一棵最佳判定樹(shù)，即總的比較次數(shù)最少的判定樹(shù)。第一種構(gòu)造方式：第二種構(gòu)造方式：這兩種方式，顯然后者的判定過(guò)程的效率要比前者高。在也沒(méi)有別地判定過(guò)程比第二種方式的效率更高。我們稱(chēng)判定過(guò)程最優(yōu)的二叉樹(shù)為哈夫曼樹(shù)，又稱(chēng)最優(yōu)二叉樹(shù)===================================================================================================定義哈夫曼樹(shù)之前先說(shuō)明幾個(gè)與哈夫曼樹(shù)有關(guān)的概念：路徑：樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。路徑長(zhǎng)度：路徑上的分枝數(shù)目稱(chēng)作路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：在一棵樹(shù)中，如果其結(jié)點(diǎn)上附帶有一個(gè)權(quán)值，通常把該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)上的權(quán)值之積稱(chēng)為該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度（weighted path length）什么是權(quán)值?( From 百度百科 ) 　計(jì)算機(jī)領(lǐng)域中（數(shù)據(jù)結(jié)構(gòu)）　　權(quán)值就是定義的路徑上面的值。可以這樣理解為節(jié)點(diǎn)間的距離。通常指字符對(duì)應(yīng)的二進(jìn)制編碼出現(xiàn)的概率?！　≈劣诨舴蚵鼧?shù)中的權(quán)值可以理解為：權(quán)值大表明出現(xiàn)概率大！　　一個(gè)結(jié)點(diǎn)的權(quán)值實(shí)際上就是這個(gè)結(jié)點(diǎn)子樹(shù)在整個(gè)樹(shù)中所占的比例.　　abcd四個(gè)葉子結(jié)點(diǎn)的權(quán)值為7,5,2,4. 這個(gè)7,5,2,4是根據(jù)實(shí)際情況得到的,比如說(shuō)從一段文本中統(tǒng)計(jì)出abcd四個(gè)字母出現(xiàn)的次數(shù)分別為7,5,2,4. 說(shuō)a結(jié)點(diǎn)的權(quán)值為7,意思是說(shuō)a結(jié)點(diǎn)在系統(tǒng)中占有7這個(gè)份量.實(shí)際上也可以化為百分比來(lái)表示,但反而麻煩,實(shí)際上是一樣的.樹(shù)的帶權(quán)路徑長(zhǎng)度：如果樹(shù)中每個(gè)葉子上都帶有一個(gè)權(quán)值，則把樹(shù)中所有葉子的帶權(quán)路徑長(zhǎng)度之和稱(chēng)為樹(shù)的帶權(quán)路徑長(zhǎng)度。設(shè)某二叉樹(shù)有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，則該二叉樹(shù)的帶權(quán)路徑長(zhǎng)度記為：公式中，Wk為第k個(gè)葉子結(jié)點(diǎn)的權(quán)值；Lk為該結(jié)點(diǎn)的路徑長(zhǎng)度。示例：======================================================================================================一般來(lái)說(shuō)，用n（n>0）個(gè)帶權(quán)值的葉子來(lái)構(gòu)造二叉樹(shù)，限定二叉樹(shù)中除了這n個(gè)葉子外只能出現(xiàn)度為2的結(jié)點(diǎn)。那么符合這樣條件的二叉樹(shù)往往可構(gòu)造出許多顆，其中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就稱(chēng)為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)===============================================================================二、哈夫曼樹(shù)的構(gòu)造根據(jù)哈弗曼樹(shù)的定義，一棵二叉樹(shù)要使其WPL值最小，必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。哈弗曼依據(jù)這一特點(diǎn)提出了一種構(gòu)造最優(yōu)二叉樹(shù)的方法，其基本思想如下：下面演示了用Huffman算法構(gòu)造一棵Huffman樹(shù)的過(guò)程：三、哈夫曼樹(shù)的在編碼中的應(yīng)用在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則：（1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有唯一性，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣；（2）發(fā)送的二進(jìn)制編碼盡可能地短。下面我們介紹兩種編碼的方式。1. 等長(zhǎng)編碼這種編碼方式的特點(diǎn)是每個(gè)字符的編碼長(zhǎng)度相同（編碼長(zhǎng)度就是每個(gè)編碼所含的二進(jìn)制位數(shù)）。假設(shè)字符集只含有4個(gè)字符A，B，C，D，用二進(jìn)制兩位表示的編碼分別為00，01，10，11。若現(xiàn)在有一段電文為：ABACCDA，則應(yīng)發(fā)送二進(jìn)制序列：00010010101100，總長(zhǎng)度為14位。當(dāng)接收方接收到這段電文后，將按兩位一段進(jìn)行譯碼。這種編碼的特點(diǎn)是譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。2. 不等長(zhǎng)編碼在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡可能地少，可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng)的，使用頻度較高的字符分配一個(gè)相對(duì)比較短的編碼，使用頻度較低的字符分配一個(gè)比較長(zhǎng)的編碼。例如，可以為A，B，C，D四個(gè)字符分別分配0，00，1，01，并可將上述電文用二進(jìn)制序列：000011010發(fā)送，其長(zhǎng)度只有9個(gè)二進(jìn)制位，但隨之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后無(wú)法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面4個(gè)0是4個(gè)A，1個(gè)B、2個(gè)A，還是2個(gè)B，即譯碼不唯一，因此這種編碼方法不可使用。因此，為了設(shè)計(jì)長(zhǎng)短不等的編碼，以便減少電文的總長(zhǎng)，還必須考慮編碼的唯一性，即在建立不等長(zhǎng)編碼時(shí)必須使任何一個(gè)字符的編碼都不是另一個(gè)字符的前綴，這宗編碼稱(chēng)為前綴編碼（prefix code）（1）利用字符集中每個(gè)字符的使用頻率作為權(quán)值構(gòu)造一個(gè)哈夫曼樹(shù)；（2）從根結(jié)點(diǎn)開(kāi)始，為到每個(gè)葉子結(jié)點(diǎn)路徑上的左分支賦予0，右分支賦予1，并從根到葉子方向形成該葉子結(jié)點(diǎn)的編碼例題：假設(shè)一個(gè)文本文件TFile中只包含7個(gè)字符利用哈夫曼樹(shù)可以為文件TFile構(gòu)造出符合前綴編碼要求的不等長(zhǎng)編碼具體做法：1. 將TFile中7個(gè)字符都作為葉子結(jié)點(diǎn)，每個(gè)字符出現(xiàn)次數(shù)作為該葉子結(jié)點(diǎn)的權(quán)值2. 規(guī)定哈夫曼樹(shù)中所有左分支表示字符0，所有右分支表示字符1,將依次從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的分支的二進(jìn)制位的序列作為該結(jié)點(diǎn)對(duì)應(yīng)的字符編碼3. 由于從根結(jié)點(diǎn)到任何一個(gè)葉子結(jié)點(diǎn)都不可能經(jīng)過(guò)其他葉子，這種編碼一定是前綴編碼，哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度正好是文件TFile編碼的總長(zhǎng)度通過(guò)哈夫曼樹(shù)來(lái)構(gòu)造的編碼稱(chēng)為哈弗曼編碼（huffman code）http://blog.csdn.net/sddxqlrjxr/article/details/51114809