（信息論編碼）Huffman編碼

ID:105323 · 發(fā)表于 2016-2-23 01:13

#include <stdio.h>
#include <math.h>
/*huffman tree 結(jié)構(gòu)定義*/
typedef struct
{
float weight;
int flag;
int parent;
int lchild;
int rchild;
}huffnode;
void main(void)
{
huffnode huff_node[50]; /*為huffman tree 定義了50個(gè)結(jié)點(diǎn)*/
int huff_code[50][10],cd,d[10],a[50];
int i,j,x1,x2,n,c,p;
float m1,m2,temp,hx=0,L=0,sum=0;/*hx為信源熵，L為平均碼長(zhǎng)*/
printf("the number of input information source:\nN= "); /*輸入信源符號(hào)的個(gè)數(shù)*/
scanf("%d",&n);
for(i=0;i<=2*n-1;i++) /*初始化huffman樹各個(gè)結(jié)點(diǎn)的值*/
{
huff_node[i].weight=0;
huff_node[i].parent=0;
huff_node[i].flag=0;
huff_node[i].lchild=-1;
huff_node[i].rchild=-1;
}
printf("Please input probability distribution :\n");
for(i=0;i<n;i++) /*輸入信源輸入分布*/
{
printf("p[%d]= ",i+1);
scanf("%f",&temp);
sum+=temp;
huff_node[i].weight=temp;
hx=hx-temp*3.332*log10(temp); /*求信源的熵H(X)*/
}
if(fabs((sum-1))>0.00001) /*判斷信源輸入分布是否正確*/
{
printf("Error!");
exit(-1);
}
/*構(gòu)建霍夫曼樹（參考數(shù)據(jù)結(jié)構(gòu)書）*/
for(i=0;i<n-1;i++)
{
m1=m2=1.1;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(huff_node[j].weight<m1&&huff_node[j].flag==0)
{
m2=m1;
x2=x1;
m1=huff_node[j].weight;
x1=j;
}
else
if(huff_node[j].weight<m2&&huff_node[j].flag==0)
{
m2=huff_node[j].weight;
x2=j;
}
}
huff_node[x1].parent=n+i;
huff_node[x2].parent=n+i; /*將找出的兩棵子樹合并為一棵子樹*/
huff_node[x1].flag=1;
huff_node[x2].flag=1;
huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
if(huff_node[x1].weight==huff_node[x2].weight) /*如果值相等，則將其置于最上面*/
{
huff_node[n+i].lchild=x1;
huff_node[n+i].rchild=x2;
}
else
{
huff_node[n+i].lchild=x2;
huff_node[n+i].rchild=x1;
}
}
/*求信源符號(hào)的huffman編碼*/
for(i=0;i<n;i++)
{
cd=n;
c=i;
p=huff_node[c].parent;
while(p!=0) /*為信源si編碼*/
{
if(huff_node[p].lchild==c) /*左孩子編碼為0*/
d[cd]=0;
else
d[cd]=1; /*左孩子編碼為1*/
cd=cd-1;
c=p;
p=huff_node[p].parent;
}
cd++;
for(j=cd;j<=n;j++) /*存儲(chǔ)信源si的huffman編碼*/
huff_code[i][j]=d[j];
a[i]=cd;
}
/*輸出信源符號(hào)的huffman編碼、信源熵和平均碼長(zhǎng)*/
printf("\ninformaition source\thuffmancode\n");
for(i=0;i<n;i++)
{
printf("p[%d]=%2.3f\t\t",i+1,huff_node[i].weight);/*輸出信源分布*/
for(j=a[i];j<=n;j++)
printf("%d",huff_code[i][j]); /*輸出huffman編碼*/
/*求平均碼長(zhǎng)*/
L=L+(n+1-a[i])*huff_node[i].weight; /*(n-cd+1)表示的是信源符號(hào)si的碼長(zhǎng)*/
printf("\n");
}
printf("\nH(X)=%.2f bit/Symbol\n",hx);/*輸出信源熵*/
printf("The average length of code is:\tL=%.2f\n",L);/*輸出平均碼長(zhǎng)*/
printf("The rate is:\tR=%.3f",hx/L); /*輸出編碼效率*/
}

復(fù)制代碼

帳號(hào)		自動(dòng)登錄	找回密碼
密碼			立即注冊(cè)

（信息論編碼）Huffman編碼

相關(guān)帖子