哈夫曼編碼演算法的實現

⑴ 計算哈夫曼編碼

六個權值(頻率)是0.040.060.130.250.280.33

(1)從小到大排序0.040.060.130.250.280.33(這是有序序列)
(2)每次提取最小的兩個結點,取結點0.04和結點0.06,組成新結點N0.10,其權值=0.04+0.06=0.10,
取數值較小的結點作為左分支,結點0.04為左分支,結點0.06為右分支.
(3)將新結點N0.10放入有序序列,保持從小到大排序:
N0.100.130.250.280.33
(4)重復步驟(2),提取最小的兩個結點,N0.10與結點0.13組成新結點N0.23,其權值=0.10+0.13=0.23,
N0.10的數值較小,作為左分支,結點0.13就作為右分支.
(5)將新結點N0.23放入有序序列,保持從小到大排序:
N0.230.250.280.33
(6)重復步驟(2),提取最小的兩個結點,N0.23與結點0.25組成新結點N0.48,其權值=0.23+0.25=0.48,
N0.23的數值較小,作為左分支,結點0.25就作為右分支.
(7)將新結點N0.48放入有序序列,保持從小到大排序:
0.280.33N0.48
(8)重復步驟(2),提取最小的兩個結點,結點0.28與結點0.33組成新結點N0.61,其權值=0.28+0.33=0.61,
結點0.28的數值較小,作為左分支,結點0.33就作為右分支.
(9)將新結點N0.61放入有序序列,保持從小到大排序:
N0.48N0.61
(10)重復步驟(2),提取剩下的兩個結點,N0.48與N0.61組成新結點N1.09,其權值=0.48+0.61=1.09,
數值較小的N0.48作為左分支,N0.61就作為右分支.
有序序列已經沒有結點,得到"哈夫曼樹":

N1.09
/
N0.48N0.61
//
N0.230.250.280.33
/
N0.100.13
/
0.040.06

帶權路徑長度(WPL):
根結點N1.09到結點0.33的路徑長度是2,結點0.33的帶權路徑長度是0.33*2
根結點N1.09到結點0.28的路徑長度是2,結點0.28的帶權路徑長度是0.28*2
根結點N1.09到結點0.25的路徑長度是2,結點0.25的帶權路徑長度是0.25*2
根結點N1.09到結點0.13的路徑長度是3,結點0.13的帶權路徑長度是0.13*3
根結點N1.09到結點0.06的路徑長度是4,結點0.06的帶權路徑長度是0.06*4
根結點N1.09到結點0.04的路徑長度是4,結點0.04的帶權路徑長度是0.04*4
所以,哈夫曼樹的帶權路徑長度(WPL)等於
0.33*2+0.28*2+0.25*2+0.13*3+0.06*4+0.04*4=2.51

哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根結點N1.09到結點0.33,先後經歷兩次右分支,結點0.33的編碼就是11
從根結點N1.09到結點0.28,先經歷右分支,後經歷左分支,結點0.28的編碼就是10
從根結點N1.09到結點0.25,先經歷左分支,後經歷右分支,結點0.25的編碼就是01
從根結點N1.09到結點0.13,先經歷兩次左分支,後經歷右分支,結點0.13的編碼就是001
從根結點N1.09到結點0.06,先經歷三次左分支,後經歷右分支,結點0.06的編碼就是0001
從根結點N1.09到結點0.04,先後經歷四次左分支,結點0.04的編碼就是0000
得出所有結點的"哈夫曼編碼":
字元f(頻率0.33):11
字元e(頻率0.28):10
字元d(頻率0.25):01
字元c(頻率0.13):001
字元b(頻率0.06):0001
字元a(頻率0.04):0000


//C語言測試程序(來自其他網友)
//
//輸入構造哈夫曼樹中帶權葉子結點數(n)：6
//輸入6個整數作為權值：4613252833(將頻率的小數形式改為整數形式)
//可以得出哈夫曼樹的廣義表形式,帶權路徑長度,以及哈夫曼編碼.

#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};

//1、輸出二叉樹，可在前序遍歷的基礎上修改。
//採用廣義表格式，元素類型為int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//輸出根結點的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//輸出左子樹
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//輸出右子樹
printf(")");
}
}
}

//2、根據數組a中n個權值建立一棵哈夫曼樹，返回樹根指針
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//進行n-1次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
intk1=-1,k2;
//讓k1初始指向森林中第一棵樹，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//從當前森林中求出最小權值樹和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];

b[k1]=q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2]=NULL;//k2位置為空
}
free(b);//刪除動態建立的數組b
returnq;//返回整個哈夫曼樹的樹根指針
}

//3、求哈夫曼樹的帶權路徑長度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始為0
{
if(FBT==NULL)//空樹返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//訪問到葉子結點
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//訪問到非葉子結點，進行遞歸調用，
{//返回左右子樹的帶權路徑長度之和，len遞增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}

//4、哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的演算法基礎上進行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值為0
{
//定義靜態數組a，保存每個葉子的編碼，數組長度至少是樹深度減一
staticinta[10];
inti;
//訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("權值為%d的編碼：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf("
");
}
else//訪問到非葉子結點時分別向左右子樹遞歸調用，
{//並把分支上的0、1編碼保存到數組a的對應元素中，
//向下深入一層時len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}

intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("輸入構造哈夫曼樹中帶權葉子結點數(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重輸n值：");
}
a=malloc(n*sizeof(ElemType));
printf("輸入%d個整數作為權值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf("
");
printf("哈夫曼樹的帶權路徑長度：
");
printf("=");
printf("
=%d
",WeightPathLength(fbt,0));
printf("樹中每個葉子結點的哈夫曼編碼：
");
HuffManCoding(fbt,0);

return0;
}

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

參考： 哈夫曼編碼

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

下面看一個例子：
假如我們有一個包含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』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的

⑶ 哈夫曼樹及哈夫曼編碼的C程序實現(數據結構題)

去年做的課程設計，有什麼不合要求的自己改改

#include<string.h>
#include<stdlib.h>
#include<stdio.h>

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 演算法6.13
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼樹的構造過程如下所示：");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2。
Select(HT, i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
}

//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父結點，編碼長度減1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("輸入結點數:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各結點的哈夫曼編碼:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

⑷ 哈夫曼編碼原理

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

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

(4)哈夫曼編碼演算法的實現擴展閱讀

赫夫曼編碼的具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率
和剩餘的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最後變成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，二者已經是很接近了。

⑸ 求高手寫個關於哈夫曼編碼的演算法

恩，樓主這個題目相當復雜啊
首先讀文件，按字元讀。一個一個讀，統計所有出現字元的頻數。
記錄到一個鏈表裡吧
第二步，建樹。霍夫曼樹……復雜程度可想而知。
Huffman 演算法
思想： 權大的外結點靠近根， 權小的遠離根。
演算法： 從m個權值中找出兩個最小值W1，W2構成
w
w1 w2 W=W1+W2表通過該結點的頻度。
依次往上找……
估計你的100個字元的短文，出現的字元數量估計平均有20個左右，建的樹的高度就12就算低的。
3 按結點到跟的距離編碼，從左到右編碼為0 1 0 1依次進行……
生成霍夫曼編碼
把每個字幕的二進制編碼記錄，打出，這就是密碼表
然後對原來的文件進行列印，碰到相應的字母列印出相應的密碼（二進制啊，汗……）
估計只有拿到密碼才能看明白那一串的01！！
如果某一電文出現的字元為D={M，S，T，A，Q， K} ， 每個字元出現的頻率為W={10，29，4，8，15，7}，
則用改演算法生成的密碼為：
S：0 A：100 M：101 Q：111
T：1100 K：1101
100 1100 101 0 111 0 1101 0 0 密文的含義是：
A T M S Q S K S S