哈夫曼（Huffman）編碼是上個世紀五十年代由哈夫曼教授研制開發的，它借助了數據結構當中的樹型結構，在哈夫曼算法的支持下構造出一棵最優二叉樹，我們把這類樹命名為哈夫曼樹。因此，準确地說，哈夫曼編碼是在哈夫曼樹的基礎之上構造出來的一種編碼形式，主要用于數據編碼壓縮，在多媒體技術、編解碼技術、通信技術等領域有着非常廣泛的應用。
1 通信中的編碼問題通信中的信息傳輸，一般都需要進行編碼，接收方收到後，按照編碼的逆過程，再将信息還原為原來的形式。
最常用的傳播通道是二元通道，即可傳輸兩個基本符号的通道，常用0、表示。
例如，将傳送的文字轉換成二進制的字符串，用0，1碼的不同排列來表示字符。假設需傳送的報文為“AFTER DATA EAR ARE ART AREA”，這裡用到的字符集為“A，E，R，T，F，D”，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區别6個字母，最簡單的二進制編碼方式是等長編碼，固定采用3位二進制，可分别用000、001、010、011、100、101對“A，E，R，T，F，D”進行編碼發送，當對方接收報文時再按照三位一分進行譯碼。顯然編碼的長度取決報文中不同字符的個數。若報文中可能出現26個不同字符，則固定編碼長度為5。然而，傳送報文時總是希望總長度盡可能短。在實際應用中，各個字符的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高于X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。
1951年，哈夫曼和他在MIT信息論的同學需要選擇是完成學期報告還是期末考試。導師Robert M. Fano給他們的學期報告的題目是，尋找最有效的二進制編碼。由于無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基于有序頻率二叉樹編碼的想法，并很快證明了這個方法是最有效的。由于這個算法，學生終于青出于藍，超過了他那曾經和信息論創立者香農共同研究過類似編碼的導師。哈夫曼使用自底向上的方法構建二叉樹，避免了次優算法Shannon-Fano編碼的最大弊端──自頂向下構建樹。
如下面的二叉樹就是兩棵葉子結點賦了權值的二叉樹。
計算上面左圖的二叉樹的帶權路徑長度：
葉子結點權值W={2,8,6,3}
對應結點的路徑長度L={2,3,3,1}
WPL ＝ {2,8,6,3} * {2,3,3,1} =49
如果二權樹的圖形相同，隻是某些葉子結點相互調換權值，二叉樹的帶權路徑長度會相同通常也會不同：
上面右圖的二叉樹的帶權路徑長度：
葉子結點權值W={8,2,3,6}
對應結點的路徑長度L={2,3,3,1}
WPL ＝ {8,2,3,6} * {2,3,3,1} =37
當然，同樣的帶權值四個葉子節點{2,8,6,3}，可以構造不同的樹，對應的各葉子結點的路徑長度肯定也會不同，所以二叉樹的帶權路徑長度也會不同。
那現在的問題是，對于給定的一組權值，如何構造二叉樹，使得帶權路徑長度最小？
2.1 将給定的權值按照從小到大的順序排列(w1,w2,…,wn)，然後構造出森林F=(T1,T2,…Tn)，其中第棵樹都是左、右子樹均為空的二叉樹，Ti的權值為Wi。
2.2 把森林F中根結點權值最小的兩棵二叉樹T1,T2作為左、右葉子結點合并為一棵新的二叉樹T，令T的根結點的權值為T1,T2兩個結點的權值之和，然後将T按照其根結點權值大小加入到森林F中，同時從F中删除T1,T2這兩棵二叉樹；
2.3 重複上述2.2步驟，直到構造出一棵二叉樹為止。
權值四個葉子節點{2,8,6,3}構造的思路可圖示如下：
上圖的二叉樹的帶權路徑長度：
葉子結點權值W={8,6,2,3}
對應結點的路徑長度L={1,2,3,3}
WPL ＝ {8,6,2,3} * {1,2,3,3} =35
按上述思路構造的二叉樹就是哈夫曼樹，根據給定的一組權值，其帶權路徑長度最小。
給定n個帶權值的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
3 哈夫曼編碼利用哈夫曼樹對數據進行二進制編碼稱為哈夫曼編碼。
假設要對字符串"this is a test"進行編碼，(t, h, i, s, a, e, 空格)就組成了一個字符集D，各字符重複的頻率組成一組權值W(3, 1, 2, 3, 1, 1, 3)，以該組權值構造一棵哈夫曼樹。從根節點到葉節點di的路徑上，每經過一條左樹枝，取二進制值0，每經過一條右樹枝，取二進制1，于是從根結點到葉結點di的路徑上得到由二進制0和1構成的二進制序列即為字符di對應的哈夫曼編碼。
字符集的哈夫曼編碼為：
字符di t h i s a e 空格符 頻率wi 3 1 2 3 1 1 3 編碼 10 00000 001 11 00001 0001 01 可以看出，重複頻率越高的字符，其哈夫曼編碼越短。相反，出現次數越少的字符，其編碼越長。這樣就從整體上保證了報文的長度最短。
因為哈夫曼編碼是不等長編碼，即不同字符的編碼長度可能不同，所以必須保證任何一個字符的編碼都不是另一個字符編碼的前綴，這樣當編碼寫到一起時才能正确區分每個字符的編碼，這樣的編碼稱為前綴編碼。由于哈夫曼編碼是基于哈夫曼樹生成的，而代表每個字符的結點都是哈夫葉子結點，不可能出現在從根結點到另一個字符的路徑上，從而保證了哈夫曼編碼一定是前綴編碼。這樣也就避免了解碼過程中的二叉性問題。
哈夫曼編碼是可變字長編碼(VLC)的一種。 Huffman于1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。
哈夫曼碼的碼字（各符号的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符号，隻要傳送時不出錯，收端仍可分離各個碼字，不緻混淆。
4 哈夫曼編碼是如何來實現數據的壓縮和解壓縮的呢?衆所周知，在計算機當中，數據的存儲和加工都是以字節作為基本單位的，一個西文字符要通過一個字節來表達，而一個漢字就要用兩個字節，我們把這種每一個字符都通過相同的字節數來表達的編碼形式稱為定長編碼。以西文為例，例如我們要在計算機當中存儲這樣的一句話:I am a teacher。就需要15個字節，也就是120個二進制位的數據來實現。與這種定長編碼不同的是，哈夫曼編碼是一種變長編碼。它根據字符出現的概率來構造平均長度最短的編碼。換句話說如果一個字符在一段文檔當中出現的次數多，它的編碼就相應的短，如果一個字符在一段文檔當中出現的次數少，它的編碼就相應的長。當編碼中，各碼字的長度嚴格按照對應符号出現的概率大小進行逆序排列時，則編碼的平均長度是最小的。這就是哈夫曼編碼實現數據壓縮的基本原理。要想得到一段數據的哈夫曼編碼，需要用到三個步驟:第一步:掃描需編碼的數據，統計原數據中各字符出現的概率。第二步:利用得到的概率值創建哈夫曼樹。第三步:對哈夫曼樹進行編碼，并把編碼後得到的碼字存儲起來。
因為定長編碼已經用相同的位數這個條件保證了任一個字符的編碼都不會成為其它編碼的前綴，所以這種情況隻會出現在變長編碼當中，要想避免這種情況，我們就必須用一個條件來制約定長編碼，這個條件就是要想成為壓縮編碼，變長編碼就必須是前綴編碼。什麼是前綴編碼呢?所謂的前綴編碼就是任何一個字符的編碼都不能是另一個字符編碼的前綴。
那麼哈夫曼編碼是否是前綴編碼呢?觀察a、b、c、d構成的編碼樹，可以發現b之所以成為c的前綴，是因為在這棵樹上，b成為了c的父結點，從在哈夫曼樹當中，原文檔中的數據字符全都分布在這棵哈夫曼樹的葉子位置，從而保證了哈夫曼編碼當中的任何一個字符的編碼都不能是另一個字符編碼的前綴。也就是說哈夫曼編碼是一種前綴編碼，也就保證了解壓縮過程當中譯碼的準确性。哈夫曼編碼的解壓縮過程也相對簡單，就是将編碼嚴格按照哈夫曼樹進行翻譯就可以了，例如遇到000，就可以順着哈夫曼樹找到I，遇到101就可以順着哈夫曼樹找到空格，以此類推，我們就可以很順利的找到原來所有的字符。哈夫曼編碼是一種一緻性編碼，有着非常廣泛的應用，例如在JPEG文件中，就應用了哈夫曼編碼來實現最後一步的壓縮;在數字電視大力發展的今天，哈夫曼編碼成為了視頻信号的主要壓縮方式。應當說，哈夫曼編碼出現，結束了熵編碼不能實現最短編碼的曆史，也使哈夫曼編碼成為一種非常重要的無損編碼。
哈夫曼方法的最大缺點就是它需要對原始數據進行兩遍掃描:第一遍統計原始數據中各字符出現的頻率，利用得到的頻率值創建哈夫曼樹并将樹的有關信息保存起來，便于解壓時使用;第二遍則根據前面得到的哈夫曼樹對原始數據進行編碼，并将編碼信息存儲起來。這樣如果用于網絡通信中，将會引起較大的延時；對于文件壓縮這樣的應用場合，額外的磁盤訪間将會降低該算法的數據壓縮速度。
為使不等長編碼為前綴編碼(即要求一個字符的編碼不能是另一個字符編碼的前綴)，可用字符集中的每個字符作為葉子結點生成一棵編碼二叉樹。為了獲得傳送報文的最短長度，可将每個字符的出現頻率作為字符結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，于是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字符集中的所有字符作為葉子結點，由字符出現頻率作為其權值所産生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。
在圖像壓縮時，霍夫曼編碼的基本方法是先對圖像數據掃描一遍，計算出各種像素出現的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼表。編碼後的圖像數據記錄的是每個像素的碼字，而碼字與實際像素值的對應關系記錄在碼表中。
5 一個哈夫曼樹的實例
運行效果：
6 一個哈夫曼編碼的實例
運行效果：
附原碼1：
#include <iostream>
#include <iomanip>
using namespace std;
//哈夫曼樹的存儲表示
typedef struct
{
int weight; // 權值
int parent, lChild, rChild; // 雙親及左右孩子的下标
}HTNode, *HuffmanTree;
// 選擇權值最小的兩顆樹
void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
{
s1 = s2 = 0;
int i;
for(i = 1; i < n; i){
if(0 == hT[i].parent){
if(0 == s1){
s1 = i;
}
else{
s2 = i;
break;
}
}
}
if(hT[s1].weight > hT[s2].weight){
int t = s1;
s1 = s2;
s2 = t;
}
for(i = 1; i < n; i){
if(0 == hT[i].parent){
if(hT[i].weight < hT[s1].weight){
s2 = s1;
s1 = i;
}else if(hT[i].weight < hT[s2].weight){
s2 = i;
}
}
}
}
// 構造有n個權值（葉子節點）的哈夫曼樹
void CreateHufmanTree(HuffmanTree &hT)
{
int n, m;
cout << "輸入需要構造哈夫曼樹的葉子結點數量，如4："<<endl;
cin >> n;
m = 2*n - 1;
hT = new HTNode[m 1]; // 0号節點不使用
for(int i = 1; i <= m; i){
hT[i].parent = hT[i].lChild = hT[i].rChild = 0;
}
cout << "輸入權值，如8 6 2 3:" <<endl;
for(int j = 1; j <= n; j){
cin >> hT[j].weight; // 輸入權值
}
hT[0].weight = m; // 用0号節點保存節點數量
/****** 初始化完畢, 創建哈夫曼樹 ******/
for(int k = n 1; k <= m; k){
int s1, s2;
SelectMin(hT, k, s1, s2);
hT[s1].parent = hT[s2].parent = k;
hT[k].lChild = s1; hT[k].rChild = s2; // 作為新節點的孩子
hT[k].weight = hT[s1].weight hT[s2].weight; // 新節點為左右孩子節點權值之和
}
}
int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)
{
if(hT[i].lChild == 0 && hT[i].rChild == 0){
return hT[i].weight * deepth;
}
else{
return HuffmanTreeWPL_(hT, hT[i].lChild, deepth 1) HuffmanTreeWPL_(hT, hT[i].rChild, deepth 1);
}
}
// 計算WPL（帶權路徑長度）
int HuffmanTreeWPL(HuffmanTree hT)
{
return HuffmanTreeWPL_(hT, hT[0].weight, 0);
}
// 輸出哈夫曼樹各節點的狀态
void Print(HuffmanTree hT)
{
cout << "index weight parent lChild rChild" << endl;
cout << left; // 左對齊輸出
for(int i = 1, m = hT[0].weight; i <= m; i){
cout << setw(5) << i << " ";
cout << setw(6) << hT[i].weight << " ";
cout << setw(6) << hT[i].parent << " ";
cout << setw(6) << hT[i].lChild << " ";
cout << setw(6) << hT[i].rChild << endl;
}
}
// 銷毀哈夫曼樹
void DestoryHuffmanTree(HuffmanTree &hT)
{
delete[] hT;
hT = NULL;
}
int main()
{
HuffmanTree hT;
CreateHufmanTree(hT);
Print(hT);
cout << "WPL = " << HuffmanTreeWPL(hT) << endl;
DestoryHuffmanTree(hT);
system("pause");
return 0;
}
附原碼2：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
typedef struct node{
char ch; //存儲該節點表示的字符，隻有葉子節點用的到
int val; //記錄該節點的權值
struct node *self,*left,*right; //三個指針，分别用于記錄自己的地址，左孩子的地址和右孩子的地址
friend bool operator <(const node &a,const node &b) //運算符重載，定義優先隊列的比較結構
{
return a.val>b.val; //這裡是權值小的優先出隊列
}
}node;
priority_queue<node> p; //定義優先隊列
char res[30]; //用于記錄哈夫曼編碼
void dfs(node *root,int level) //打印字符和對應的哈夫曼編碼
{
if(root->left==root->right) //葉子節點的左孩子地址一定等于右孩子地址，且一定都為NULL;葉子節點記錄有字符
{
if(level==0) //“AAAAA”這種隻有一字符的情況
{
res[0]='0';
level ;
}
res[level]='\0'; //字符數組以'\0'結束
printf("%c=>%s\n",root->ch,res);
}
else
{
res[level]='0'; //左分支為0
dfs(root->left,level 1);
res[level]='1'; //右分支為1
dfs(root->right,level 1);
}
}
void huffman(int *hash) //構建哈夫曼樹
{
node *root,fir,sec;
for(int i=0;i<26;i ) //程序隻能處理全為大寫英文字符的信息串，故哈希也隻有26個
{
if(!hash[i]) //對應字母在text中未出現
continue;
root=(node *)malloc(sizeof(node)); //開辟節點
root->self=root; //記錄自己的地址，方便父節點連接自己
root->left=root->right=NULL; //該節點是葉子節點，左右孩子地址均為NULL
root->ch='A' i; //記錄該節點表示的字符
root->val=hash[i]; //記錄該字符的權值
p.push(*root); //将該節點壓入優先隊列
}
//下面循環模拟建樹過程，每次取出兩個最小的節點合并後重新壓入隊列
//當隊列中剩餘節點數量為1時，哈夫曼樹構建完成
while(p.size()>1)
{
fir=p.top();p.pop(); //取出最小的節點
sec=p.top();p.pop(); //取出次小的節點
root=(node *)malloc(sizeof(node)); //構建新節點，将其作為fir，sec的父節點
root->self=root; //記錄自己的地址，方便該節點的父節點連接
root->left=fir.self; //記錄左孩子節點地址
root->right=sec.self; //記錄右孩子節點地址
root->val=fir.val sec.val;//該節點權值為兩孩子權值之和
p.push(*root); //将新節點壓入隊列
}
fir=p.top();p.pop(); //彈出哈夫曼樹的根節點
dfs(fir.self,0); //輸出葉子節點記錄的字符和對應的哈夫曼編碼
}
int main()
{
char text[100];
int hash[30];
memset(hash,0,sizeof(hash)); //哈希數組初始化全為0
printf("輸入信息串text，全部要求是大字字母，不能有空格，如THISISATEST:\n");
scanf("%s",text); //讀入信息串text
for(int i=0;text[i]!='\0';i )//通過哈希求每個字符的出現次數
{
hash[text[i]-'A'] ; //程序假設運行的全為英文大寫字母
}
huffman(hash);
getchar();getchar();
system("pause");
return 0;
}
－End－
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
