哈夫曼編碼用什麼數據

㈠ 哈夫曼編碼碼長怎麼算

設某信源產生有五種符號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。

㈡ 哈夫曼編碼 數據結構演算法

#include <stdio.h>
#include <string.h>
#define N 50 /*葉子結點數*/
#define M 2*N-1 /*樹中結點總數*/
typedef struct
{
char data[5]; /*結點值*/
int weight; /*權重*/
int parent; /*雙親結點*/
int lchild; /*左孩子結點*/
int rchild; /*右孩子結點*/
} HTNode;
typedef struct
{
char cd[N]; /*存放哈夫曼碼*/
int start;
} HCode;
void CreateHT(HTNode ht[],int n)
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++) /*所有結點的相關域置初值-1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*構造哈夫曼樹*/
{
min1=min2=32767; /*lnode和rnode為最小權重的兩個結點位置*/
lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1) /*只在尚未構造二叉樹的結點中查找*/
{
if (ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++) /*根據哈夫曼樹求哈夫曼編碼*/
{
hc.start=n;c=i;
f=ht[i].parent;
while (f!=-1) /*循序直到樹根結點*/
{
if (ht[f].lchild==c) /*處理左孩子結點*/
hc.cd[hc.start--]='0';
else /*處理右孩子結點*/
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++; /*start指向哈夫曼編碼最開始字元*/
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k;
int sum=0,m=0,j;
printf(" 輸出哈夫曼編碼:\n"); /*輸出哈夫曼編碼*/
for (i=0;i<n;i++)
{
j=0;
printf(" %s:\t",ht[i].data);
for (k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n 平均長度=%g\n",1.0*sum/m);
}
void main()
{
int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
HTNode ht[M];
HCode hcd[N];
for (i=0;i<n;i++)
{
strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
}
網上找了一個，運行了一下，應沒問題，你可根據自已情況做適當修改。

㈢ 哈夫曼樹和哈夫曼編碼

給定n個權值作為n的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
哈夫曼樹（霍夫曼樹）又稱為最優樹.
1、路徑和路徑長度
在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長

哈夫曼樹 (3張)
度為L-1。

2、結點的權及帶權路徑長度
若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。
3、樹的帶權路徑長度
樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。
構造
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。
哈夫曼編碼
在數據通信中，需要將傳送的文字轉換成二進制的字元串，用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，自然會想到設計編碼時，讓

哈夫曼樹 (4張)
使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。

為使不等長編碼為前綴編碼(即要求一個字元的編碼不能是另一個字元編碼的前綴)，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，於是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。
哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
哈夫曼動態編碼：動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。
2、哈夫曼解碼
在通信中，若將字元用哈夫曼編碼形式發送出去，對方接收到編碼後，將編碼還原成字元的過程，稱為哈夫曼解碼。

㈣ 哈夫曼編碼和二進制編碼優缺點比較

比較如下：

1、碼字不同。

哈夫曼所構造的碼字不是唯一的，對於同一個信息源，無論上述的前後順序如何排列，它的平均碼長是不會改變的，所以他的優點是編碼效率唯一性。而二進制編碼所構造的碼字是唯一。

2、長度不同

哈夫曼編碼是依據字元出現概率來構造異字頭的平均長度最短的碼字，比較精準，二進制編碼是用預先規定的方法將文字、數字或其他對象編成二進制的數碼，或將信息、數據轉換成規定的二進制電脈沖信號。二進制是最基礎的編碼。

3、穩定性不同

哈夫曼編碼的穩定性比較差。如果改變其中一位數據就會產生改變。二進制編碼具有抗干擾能力強，可靠性高等優點。

㈤ 數據傳輸中使用二進制編碼,要傳送的6個數據為:AA,AB,ADC,CFE,DF,BCDA.試給出其中CFE的赫夫曼編碼.

對每一個字母單獨編碼 分別計算每一個字母的頻率即為權重 如A出現了5次 總共出現了16個字母 A的權重就是5/16 依次得出其他字母權重 構造赫夫曼樹 這就不用說了 當然 會有多種編碼 因為有兩組相同的權重

㈥ 哈夫曼編碼演算法設計

在哈夫曼編碼中，若編碼長度只允許小於等於4，則除了兩個字元已編碼為0和10因為其中一個不能是另一個的前綴 所以只能是1111、1110、1101、1100

㈦ 利用 數據結構 實現 哈夫曼編碼/解碼實現

//D:\2010 代碼\haffman\haffman\Node_statement.h
#define MAXVALUE 1000//定義最大權值
#define MAXBIT 100//定義哈夫曼樹中葉子結點個數
typedef struct
{
char data;//字元值
int num;//某個值的字元出現的次數
}TotalNode;
//統計結點，包括字元種類和出現次數
typedef struct
{
TotalNode tot[300];//統計結點數組
int num;//統計數組中含有的字元個數
}Total;
//統計結構體，包括統計數組和字元種類數
typedef struct
{
char mes[300];//字元數組
int num;//總字元數
}Message;
//信息結構體，包括字元數組和總字元數
typedef struct{
int locked[500];//密碼數組
int num;//密碼總數
}Locking;
//哈夫曼編碼後的密文信息
typedef struct
{
char data;//字元
int weight;//權值
int parent;//雙親結點在數組HuffNode[]中的序號
int lchild;//左孩子結點在數組HuffNode[]中的序號
int rchild;//右孩子結點在數組HuffNode[]中的序號
}HNodetype;
//哈夫曼樹結點類型，包括左右孩子，權值和信息
typedef struct
{
int bit[MAXBIT];
int start;
}HCodetype;
//哈夫曼編碼結構體，包括編碼數組和起始位

void reading_file(Message *message);//從文件中讀取信息
int writing_file(Message *message);//將信息寫進文件
void total_message(Message *message,Total *total);//統計信息中各字元的次數
void HaffmanTree(Total *total,HNodetype HuffNode[]);//構建哈夫曼樹
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼編碼
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//將編碼規則寫進文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//給文件信息加密編碼
void writing_lock(Locking *locking);//將已編碼信息寫進文件
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);
void display(Total *total,HNodetype HuffNode[]);
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//將已編碼信息翻譯過來並寫進文

//D:\2010 代碼\haffman\haffman\function_mian.cpp
#include"Node_statement.h"
#include<iostream>
#include<fstream>
#include "cstdlib"
using namespace std;
int main()
{
int i,j,choice,mark=0;//mark標記文件信息是否讀入到內存中
HNodetype HuffNode[500];//保存哈夫曼樹中各結點信息
HCodetype HuffCode[300];
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking->num=0;
total=new Total;
total->num=0;
message=new Message;
message->num=0;
//初始化變數
printf("┏ ┓\n");
printf("┣ haffman_code system ┫ \n");
printf("┗ ┛\n");
printf("\n\n");
choice=0;
while(choice!=7 )
{

printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" 0:go \n");
printf("※********** 1：從文件讀取信息**********************※\n");
printf(" *********** 2：顯示編碼規則 ********************* \n");
printf(" ********** 3：將原文件信息寫進文件 ************ \n");
printf(" ********* 4：將編碼規則寫進文件 ************ \n");
printf(" ********** 5：將編碼後的信息寫進文件 ********** \n");
printf(" *********** 6：將解碼後的信息寫進文件 *********\n");
printf("※***********7：退出 *****************************※\n");
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" please input the choice ");
cin>>choice;
switch(choice)
{
case 1:
reading_file(message);//從文件中讀取信息
mark=1;
break;
case 2://顯示編碼規則
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
cout<<"編碼規則為"<<endl;
for(i=0;i<total->num;i++)//顯示編碼規則
{
cout<<total->tot[i].data<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
break;
case 3://將原文件信息寫進文件a_test1.txt
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else

writing_file(message);//將信息寫進文件
break;
case 4://將編碼規則寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_HCode(HuffNode,HuffCode,total);//將編碼規則寫進文件
}
break;
case 5://將編碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_lock(locking);//將已編碼信息寫進文件
}
break;
case 6://將解碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_translate(locking,HuffCode,HuffNode,total);//將已編碼信息翻譯過來並寫進文件
}
break;
}
}

/**
列印haffman樹
**/
display(total,HuffNode);
system("PAUSE");
return 0;
}

void display(Total *total,HNodetype HuffNode[])
{
int i,j;
for(i=0;i<2*total->num-1;i++)
{
printf("data weight lchild rchild parent \n");
printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent);
}

}

void reading_file(Message *message)
/**
絕對路徑下讀取a_test.txt file
message 中的num記錄suoyou字元總數 ，放在nes【】中
equal to the buffer
**/
{
int i=0;
char ch;
ifstream infile("a_test.txt",ios::in | ios::out);
if(!infile)//打開失敗則結束
{
cout<<"打開a_test.txt文件失敗"<<endl;
exit(1);
}
else
cout<<"讀取文件成功"<<endl;
while(infile.get(ch) && ch!='#')//讀取字元直到遇到#
{
message->mes[i]=ch;
i++;
}
message->num=i;//記錄總字元數
infile.close();//關閉文件
}

int writing_file(Message *message)
/**
把從數組message 的信息write to disk，a_test1.txt to save
**/
{ /*
int i;
ifstream outfile("a_test1.txt",ios::in ); //打開文件
if( !outfile )//打開失敗則結束
{
cout<<"打開a_test1.txt文件失敗"<<endl;
return -1;
}
for(i=0;i<message->num;i++)//寫文件
outfile.put(message->mes[i]);
cout<<"信息寫進文件成功"<<endl;
outfile.close();//關閉文件
return 0;*/
int i;
FILE *fp1=NULL;

if((fp1 = fopen("a_test1.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<message->num;i++)
fprintf(fp1,"%d ",message->mes[i]);
printf("文件寫入成功!\n");
i=fclose(fp1);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");
}

void total_message(Message *message,Total *total)
/**
統計message中不同字元 的個數，和相同字元重復的次數，重復字元用mark標記，
total.tot[] 放不同字元，TotalNode 類型（char，num）
total.num 統計不同字元個數
使total這塊內存空間有數據，
**/
{
int i,j,mark;
for(i=0;i<message->num;i++)//遍歷message中的所有字元信息
{
if(message->mes[i]!=' ')//字元不為空格時
{
mark=0;
for(j=0;j<total->num;j++)//在total中搜索當前字元
if(total->tot[j].data==message->mes[i])//搜索到，則此字元次數加1，mark標志為1
{
total->tot[j].num++;
mark=1;
break;
}
if(mark==0)//未搜索到，新建字元種類，保存進total中，字元類加1
{
total->tot[total->num].data=message->mes[i];
total->tot[total->num].num=1;
total->num++;
}
}
}
}

void HaffmanTree(Total *total,HNodetype HuffNode[])
/**create the haffman tree
不同字元個數為葉子節點個數對應書上的n，
相同字元的個數為其權值weight；
get HuffNode to store the tree
**/
{
int i,j,min1,min2,x1,x2;
for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼樹並存入葉子結點權值和信息
{
if(i<=total->num-1)
HuffNode[i].data=total->tot[i].data;
HuffNode[i].weight=total->tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<total->num-1;i++)
{
min1=min2=MAXVALUE;
x1=x2=0;
for(j=0;j<total->num+i;j++)//選取最小x1和次小x2的兩權值
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)
{
min2=min1;
x2=x1;
min1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)
{
min2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=total->num+i;//修改親人結點位置
HuffNode[x2].parent=total->num+i;
HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[total->num+i].lchild=x1;//左孩子比右孩子權值小
HuffNode[total->num+i].rchild=x2;
}
}

void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/***
haffman to code (0,10,110,)
得到每個不同字元（葉子）的編碼，
存貯在數組HuffCode【】中,bit[] store the char,start store the loction
**/
{

int i,j,c,p;
HCodetype cd;
for(i=0;i<total->num;i++)//建立葉子結點個數的編碼
{
cd.start=total->num-1;//起始位初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//從葉結點向上爬直到到達根結點
{
if(HuffNode[p].lchild==c)//左分支則為0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;//右分支則為1
cd.start--;//起始位向前移動
c=p;
p=HuffNode[p].parent;
}
for(j=cd.start+1;j<total->num;j++)//保存求出的每個葉結點編碼和起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;

}
}

void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/**
HuffNode[]to input the leaf
HuffCode[]to input the code
all is to the a_test2.txt ,save the code
**/
{
/*打開HCode文件，失敗則結束。將信息寫進文件*/
int i,j;
FILE *fp2=NULL;

if((fp2 = fopen("a_test2.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)
{fprintf(fp2,"%d ",HuffNode[i].data);
printf(" ");
for(j=HuffCode[i].start+1;j<total->num;j++)
fprintf(fp2,"%d ",HuffCode[i].bit[j]);
}
printf("編碼規則寫進文件成功!\n");
i=fclose(fp2);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");
}

void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)
/***
對messag操作，對所有字元加密，
結果存貯在數組locked[]中，locking 記錄已經加密後的密文
**/

{
int i,j,m;
for(i=0;i<message->num;i++)//把相同的不同的字元全部 遍歷
{
if(message->mes[i]==' ')//碰到空格則以-1形式保存進locked數組中
{
locking->locked[locking->num]=-1;
locking->num++;
}
else
for(j=0;j<total->num;j++)//從total中找到對應的字元
{
if(HuffNode[j].data==message->mes[i])
//找到在HuffNode 中對應字元，找到下標j
// 在HuffCode

for(m=HuffCode[j].start+1;m<total->num;m++)///////// !
{
locking->locked[locking->num]=HuffCode[j].bit[m];//加密
locking->num++;
}
}
}
}

void writing_lock(Locking *locking)
/*
將密文寫到a_test3.txt
*/
{
int i;
FILE *fp3=NULL;

if((fp3= fopen("a_test3.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<locking->num;i++)
{
if(locking->locked[i]==-1)
printf(" ");
else
fprintf(fp3,"%d ",locking->locked[i]);
}
printf("已編碼信息寫進文件成功!\n");
i=fclose(fp3);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");

}

void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
/**
密文翻譯成明文，然後存到文件 a_test4.txt
**/
{
int i,j,mark[100],start[100],min,max;
FILE *fp4=NULL;

if((fp4 = fopen("a_test4.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}

for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;//。。。。
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
min=0;

for(max=0;max<locking->num;max++)//寫文件
{
if(locking->locked[max]==-1)//碰到空格信息則直接輸出空格
{
printf(" ");//把空格寫到文件
min++;
}
else
{
for(i=min;i<=max;i++)//查找從min開始到max的編碼對應的信息
{
for(j=0;j<total->num;j++)
{
if(start[j] == total->num+1)
mark[j]=0; //對應編碼比所給編碼短則不在比較
if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
else
mark[j]=0;
}
}
for(i=0;i<total->num;i++)//找到對應信息，則寫進文件
{
if(mark[i]==1&&start[i]==total->num)
{
fprintf(fp4,"%d ",HuffNode[i].data);//寫到文件outfile
break;
}
}
if(i!=total->num)
min=max+1;
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
}
}
printf("文件寫入成功!\n");
i=fclose(fp4);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");
}
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message)
{
total_message(message,total);//統計信息中各字元的出現次數
HaffmanTree(total,HuffNode);//構建哈夫曼樹
HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼

}

㈧ 哈夫曼編碼原理

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

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

(8)哈夫曼編碼用什麼數據擴展閱讀

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

㈨ 哈夫曼的編碼

哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。） 而且哈夫曼編碼是按照子樹到父親，而其讀碼則是完全相反的。 因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。
哈夫曼樹的構造演算法。
const maxvalue= 10000; {定義最大權值}
maxleat=30; {定義哈夫曼樹中葉子結點個數}
maxnode=maxleaf*2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0..maxnode] of HnodeType;
var ……
procere CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構造演算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {輸入葉子結點個數}
for i:=0 to 2*n-1 do {數組HuffNode[ ]初始化}
begin
HuffNode.weight=0;
HuffNode.parent=-1;
HuffNode.lchild=-1;
HuffNode.rchild=-1;
end;
for i:=0 to n-1 do read(HuffNode.weight); {輸入n個葉子結點的權值}
for i:=0 to n-1 do {構造哈夫曼樹}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n+i-1 do
if (HuffNode[j].weight<m1) and (HuffNode[j].parent=-1) then
begin m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
end
else if (HuffNode[j].weight<m2) and (HuffNode[j].parent=-1) then
begin m2:=HuffNode[j].weight; x2:=j; end;
{將找出的兩棵子樹合並為一棵子樹}
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;
end;
end;