哈夫曼編譯問題演算法分析

A. 哈夫曼解碼演算法

C++的
#include<stdlib.h>
#include<fstream.h>
#include<iomanip.h>
#include<windows.h>
ofstream outstuf;
#define MAXBIT 50 // 哈夫曼編碼的最大長度
#define MAXVALUE 50 // 最大權值
#define MAXLEAF 50 // 哈夫曼樹中葉子結點個數
#define MAXNODE MAXLEAF*2-1 //樹中結點總數
//哈夫曼樹結點結構
typedef struct
{
char data ; //結點值
int weight; //權值
int parent; //雙親結點
int lchild; //左孩子結點
int rchild; //右孩子結點
}HNodeType;
HNodeType HuffNode[MAXNODE];
//存放哈夫曼編碼的數據元素結構
typedef struct
{
int bit [MAXBIT]; //存放哈夫曼碼
int start; //編碼的起始下標
}HCodeType;
void Haffmanfile(int n); //保存文件
HNodeType *HaffmanTree(int n) ; //構造哈夫曼樹
void Haffmancode(int n); //構造哈夫曼編碼
HNodeType *HaffmanTree(int n) //構造哈夫曼樹
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) //所有結點的初始化
{
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
cout<<"\t________________________________________"<<endl;
cout<<"\t輸入葉子結點的值和權值"<<endl;
cout<<"\t________________________________________"<<endl;
for(i=0;i<n;i++)
{
cout<<"\t______________________"<<endl;
cout<<"\t輸入第"<<i+1<<"個葉子節點的值: ";
cin>>HuffNode[i].data;
cout<<"\t輸入第"<<i+1<<"個葉子節點的權值: ";
cin>>HuffNode[i].weight;
}
for(i=0;i<n-1;i++) //構造哈夫曼樹
{ m1=m2=MAXVALUE; x1=x2=0;
for(j=0;j<n+i;j++)
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) //只在尚未構造二叉樹的結點中查找
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//將找出的兩棵權值最小的子樹合並為一棵子樹
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
return HuffNode;
}
//構造哈夫曼編碼
void Haffmancode(int n)
{
int i,j,c,p;
HNodeType *HuffNode=new HNodeType[MAXNODE];
HCodeType *HuffCode=new HCodeType[MAXLEAF];
HCodeType *cd=new HCodeType;
HuffNode=HaffmanTree(n); //建立哈夫曼樹
for(i=0;i<n;i++)
{
cd->start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1) //循環直到樹根結點
{
if(HuffNode[p].lchild==c)
cd->bit[cd->start]=0; //處理左孩子結點
else
cd->bit[cd->start]=1; //處理右孩子結點
cd->start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd->start+1;j<n;j++)
HuffCode[i].bit[j]=cd->bit[j];
HuffCode[i].start=cd->start; //指向哈夫曼編碼最開始字元
}
cout<<"\n\t每個葉子結點的值及對應的哈夫曼編碼"<<endl;
for(i=0;i<n;i++)
{ cout<<"\t****************************************"<<endl;
cout<<"\t第"<<i+1<<"個葉子結點的值和哈夫曼編碼為:";
cout<<HuffNode[i].data<<" ";
for(j=HuffCode[i].start+1;j<n;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
outstuf.open("bianma.txt",ios::out);
outstuf<<"____________\n哈夫曼編碼:\n____________ "<<endl;
for(i=0;i<n;i++)
{
for(j=HuffCode[i].start+1;j<n;j++)
outstuf<<HuffCode[i].bit[j]<<" ";
outstuf<<endl;
}
cout<<"\t\t*******************"<<endl;
cout<<"\t\t哈夫曼編碼保存成功!"<<endl;
cout<<"\t\t*******************"<<endl;
outstuf.close();
Haffmanfile(n);
}
void Haffmanfile(int n)
{
char s[80];
int a[20],i=0,r;
ifstream instuf("bianma.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打開!"<<endl;
abort();
}
instuf.getline(s,80);
while(instuf>>a[i])
i++;
for(r=0;r<i;r++) cout<<a[r]<<" ";
if(a[0]!=0&&a[0]!=1)
{
cout<<"此文件無內容!"<<endl;
abort();
}
instuf.close();
int p=0,j=0,k=0; char zu[10],ch;
system("pause");system("cls");
cout<<"\n\t\t*************************************"<<endl;
cout<<"\t\t是否要對原編碼進行解碼操作 (Y or N)?:\t";
cin>>ch;
if(ch=='N'||ch=='n') return;
for(r=0;r<n;r++)
{
p=2*n-2;
while(HuffNode[p].lchild!=-1&&HuffNode[p].rchild!=-1)
{
if(a[j]==0) p=HuffNode[p].lchild;
if(a[j]==1) p=HuffNode[p].rchild;
j++;
}
zu[k]=HuffNode[p].data;
k++;
}
outstuf.open("yima.txt",ios::out);
outstuf<<"解碼為: "<<endl;
for(j=0;j<n;j++) outstuf<<HuffNode[j].data<<" ";
outstuf<<endl;
cout<<"\t\t**************\n\t\t解碼保存成功!\n\t\t**************"<<endl;
outstuf.close();
instuf.open("yima.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打開!"<<endl;
abort();
}
instuf.getline(s,80);
i=0;
cout<<"\n\t\t哈夫曼編碼的解碼為: ";
while(instuf>>zu[i])
{cout<<zu[i]<<" ";
i++;
}
cout<<endl;
instuf.close();
}
void main()
{
int n,i;char choice;system("cls");system("color 80");
cout<<"\t _______________________________________________________"<<endl;
cout<<"\t 本演示系統可以良好的演示哈夫曼編碼和解碼的產生,"<<endl;
cout<<"\t 但本程序有一定的不完善，用戶可以隨時到CSDN社區關注更新!"<<endl;
cout<<"\t _______________________________________________________"<<endl;
loop:
cout<<"\t\t _________________________________\n\n";
cout<<"\t\t 1.哈夫曼演示系統 0.退出演示系統\n";
cout<<"\t\t _________________________________\n\n\t請選擇\t";
cin>>choice;
switch(choice)
{case '1': system("cls");
cout<<"\t\t _____________________________\n\n";
cout<<"\t\t\t請輸入葉子結點個數:\t";
cin>>n;
Haffmancode(n);
cout<<"\n\t*********輸出哈夫曼樹!**********"<<endl;
cout<<"\t字元 "<<"權值 "<<"左孩子指針 "<<"右孩子指針"<<endl;
for( i=0;i<2*n-1;i++)
{cout<<"\t";
cout<<setw(5)<<HuffNode[i].data<<setw(5)<<HuffNode[i].weight<<setw(5)<<
HuffNode[i].lchild<<setw(5)<<HuffNode[i].rchild<<setw(5)<<
HuffNode[i].parent<<endl;
}
system("pause");system("cls");goto loop;break;
case '0':break;
}
}

B. 哈夫曼編碼原理

赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。

哈夫曼編碼，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼。

(2)哈夫曼編譯問題演算法分析擴展閱讀

赫夫曼編碼的具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率
和剩餘的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最後變成1。

每次相
加時都將「0」和「1」賦與相加的兩個概率，讀出時由該符號開始一直走到最後的「1」，
將路線上所遇到的「0」和「1」按最低位到最高位的順序排好，就是該符號的赫夫曼編碼。

例如a7從左至右，由U至U″″，其碼字為1000；

a6按路線將所遇到的「0」和「1」按最低位到最高位的順序排好，其碼字為1001…

用赫夫曼編碼所得的平均比特率為：Σ碼長×出現概率

上例為：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵為2.61bit，二者已經是很接近了。

C. 敘述哈夫曼演算法的思想

運行過了沒有任何問題,有什麼問題可以交流下.
#include
#include
#define N 6
typedef struct
{

int W,P,R,L;
}HTNode;
typedef struct
{
char ch;
char code[10];
}HTCode;
HTCode HC[27];
void select(HTNode HT[],int *min1,int *min2,int *a,int *b)
{

int i;int mina=100,minb=100;
int m,n;

for(i=1;i

D. 請描述哈夫曼演算法，並用圖描述構造哈夫曼樹的過程。

這個講的相當清楚。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。）
然而怎樣構造一棵哈夫曼樹呢？最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述：
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現演算法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法，可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構： struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合，以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例：若字母A，B，Z，C出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，101，11，對於編碼串：1010就可翻譯為bb或ca，因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規定。
這種編碼方法是靜態的哈夫曼編碼，它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。 靜態哈夫曼編碼方法有一些缺點：一、對於過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；二、進行哈夫曼編碼，存儲編碼信息時，若用與通訊網路，就會引起較大的延時；三、對較大的文件進行編碼時，頻繁的磁碟讀寫訪問會降低數據編碼的速度。
因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。

E. 哈夫曼編碼碼長怎麼算

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼編碼是變長編碼，思路：對概率大的編的碼字短，概率小的編的碼字長，這樣一來所編的總碼長就小，這樣編碼效率就高。上面那樣求是不對的，除非你這6個碼字是等概率的，各佔1/6。應該用對應的概率*其對應得碼長，再求和。

實際應用中

除採用定時清洗以消除誤差擴散和採用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。

按照CCITT標准，需要統計2×1728種遊程（長度），這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。

F. 哈夫曼編碼（貪心演算法）

參考： 哈夫曼編碼

哈夫曼編碼是一種十分有效的編碼方法，廣泛應用於 數據壓縮 中
通過採用 不等長 的編碼方式，根據 字元頻率的不同 ，選擇 不同長度的編碼 ，對頻率 越高 的字元採用 越短 的編碼實現數據的高度壓縮。
這種對頻率越高的字元採用越短的編碼來編碼的方式應用的就是貪心演算法的思想。

下面看一個例子：
假如我們有一個包含1000個字元的文件，每個字元佔1個byte(1byte=8bits)，則存儲這100個字元一共需要8000bits。這還是有一些大的
那我們統計一下這1000個字元中總共有多少種字元，原來需要8bit來表示一個字元，如果使用更少的位數來表示這些字元，則可以減少存儲空間。
假設這1000個字元中總共有a、b、c、d、e、f共6種字元，使用使用3個二進制位來表示的話，存儲這1000個字元就只需要3000bits，比原來更節省存儲空間。

或許還可以再壓縮一下：
根據字元出現的 頻率 給與字元 不等長 的編碼，頻率越高的字元編碼越短，頻率越低的字元編碼越長。
它不能像等長編碼一樣直接按固定長度去讀取二進制位，翻譯成字元，為了能夠准確讀取翻譯字元，它要求一個字元的編碼不能是另外一個字元的前綴。

假設a、b、c、d、e、f這6個字元出現的頻率依次降低，則我們可以給與他們這樣的編碼

假如字元的出現頻率如圖所示，按照這樣的編碼表示的話，總位數如圖，一共2100bits，更加節省空間了

貪心策略：頻率小的字元，優先入隊。

步驟：
1.將每一個字元作為節點，以出現頻率大小作為權重，將其都放入 優先隊列 中（一個最小堆）；
2.每次出隊兩個節點並創建一個父節點，使其權值為剛剛出隊的節點的權值和，並且為兩個節點的父節點（合並）。然後將這個樹入隊。
3.重復操作2，直到隊列中只有一個元素（此時這個元素表示形式應該為一個樹）時，完成創建。

創建好了樹，該怎麼編碼呢？
我們對一個哈夫曼樹，從父節點開始的所有節點，往左邊標0，右邊標1。那麼到達葉子節點的順次編碼就可以找到了。

C：字元集合
Q：優先隊列
EXTRACT-MIN：傳入一個隊列，出隊最小的元素
INSERT：將z插入到Q中

當for循環結束之後，此時隊列中只有一個元素，就是我們需要的哈夫曼樹，最後返回此樹即可。

假設T樹已經是一個最優的樹，假設x、y的頻率小於等於最低處的a、b，然後交換x、a，y、b。

計算代價是否發生變化。
比如這里比較 T 變成 T 』 後代價是否變化，發現代價變小或不變。

同理T』到T』』，又因為T本來假設就是最優的，所以只能相等
所以T』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的

G. 演算法解析：哈夫曼（huffman）壓縮演算法

本篇將介紹 哈夫曼壓縮演算法（Huffman compression）

眾所周知，計算機存儲數據時，實際上存儲的是一堆0和1（二進制）。

如果我們存儲一段字元：ABRACADABRA!

那麼計算機會把它們逐一翻譯成二進制，如A：01000001；B: 01000010; !: 00001010.

每個字元佔8個bits, 這一整段字元則至少佔12*8=96 bits。

但如果我們用一些特殊的值來代表這些字元，如：

圖中，0代表A; 1111代表B；等等。此時，存儲這段字元只需30bits，比96bits小多了，達到了壓縮的目的。

我們需要這么一個表格來把原數據翻譯成特別的、占空間較少的數據。同時，我們也可以用這個表格，把特別的數據還原成原數據。

首先，為了避免翻譯歧義，這個表格需滿足一個條件： 任何一個字元用的值都不能是其它字元的前綴 。

我們舉個反例：A: 0; B: 01;這里，A的值是B的值的前綴。如果壓縮後的數據為01xxxxxx,x為0或者1，那麼這個數據應該翻譯成A1xxxxxx, 還是Bxxxxxxx?這樣就會造成歧義。

然後，不同的表格會有不同的壓縮效果，如：

這個表格的壓縮效果更好。

那麼我們如何找到 最好的表格 呢？這個我們稍後再講。

為了方便閱讀，這個表格是可以寫成一棵樹的：

這棵樹的節點左邊是0，右邊是1。任何含有字元的節點都沒有非空子節點。（即上文提及的前綴問題。）

這棵樹是在壓縮的過程中建成的，這個表格是在樹形成後建成的。用這個表格，我們可以很簡單地把一段字元變成壓縮後的數據，如：

原數據：ABRACADABRA!

表格如上圖。

令壓縮後的數據為S；

第一個字元是A，根據表格，A：11，故S=11;

第二個字元是B，根據表格，B：00，故S=1100;

第三個字元是R，根據表格，R：011，故S=1100011;

如此類推，讀完所有字元為止。

壓縮搞定了，那解壓呢？很簡單，跟著這棵樹讀就行了：

壓縮後的數據S=11000111101011100110001111101

記住，讀到1時，往右走，讀到0時，往左走。

令解壓後的字元串為D；

從根節點出發，第一個數是1，往右走：

第二個數是1，往右走：

讀到有字元的節點，返回此字元，加到字元串D里。D:A;

返回根節點，繼續讀。

第三個數是0，往左走：

第四個數是0，往左走：

讀到有字元的節點，返回此字元，加到字元串D里。D:AB;

返回根節點，繼續讀。

第五個數是0，往左走：

第六個數是1，往右走：

第七個數是1，往右走：

讀到有字元的節點，返回此字元，加到字元串D里。D:ABR;

返回根節點，繼續讀。

如此類推，直到讀完所有壓縮後的數據S為止。

壓縮與解壓都搞定了之後 我們需要先把原數據讀一遍，並把每個字元出現的次數記錄下來。如：

ABRACADABRA!中，A出現了5次;B出現了2次;C出現了1次;D出現了1次;R出現了2次;!出現了1次。

理論上，出現頻率越高的字元，我們給它一個佔用空間越小的值，這樣，我們就可以有最佳的壓縮率

由於哈夫曼壓縮演算法這塊涉及內容較多 ，文章篇幅很長；全文全方面講解了Compose布局的各方面知識。更多Android前言技術進階，我自薦一套《 完整的Android的資料，以及一些視頻課講解 》 現在私信發送「進階」或者「筆記」即可免費獲取

最後我想說：

對於程序員來說，要學習的知識內容、技術有太多太多，要想不被環境淘汰就只有不斷提升自己，從來都是我們去適應環境，而不是環境來適應我們

技術是無止境的，你需要對自己提交的每一行代碼、使用的每一個工具負責，不斷挖掘其底層原理，才能使自己的技術升華到更高的層面

Android 架構師之路還很漫長，與君共勉