標(biāo)題: （信息論編碼）Huffman編碼 [打印本頁(yè)]
作者: 51黑黑黑    時(shí)間: 2016-2-23 01:13
標(biāo)題: （信息論編碼）Huffman編碼
  1. #include <stdio.h>
  2. #include <math.h>

  4. /*huffman tree 結(jié)構(gòu)定義*/
  5. typedef struct
  6. {
  7. float weight;
  8.     int   flag;
  9.   int   parent;
  10.   int   lchild;
  11.   int   rchild;
  12. }huffnode;



  16. void main(void)
  17. {
  18.   huffnode huff_node[50];         /*為huffman tree 定義了50個(gè)結(jié)點(diǎn)*/
  19.   int huff_code[50][10],cd,d[10],a[50];  
  20.   int i,j,x1,x2,n,c,p;
  21.   float m1,m2,temp,hx=0,L=0,sum=0;/*hx為信源熵，L為平均碼長(zhǎng)*/
  22.   printf("the number of input information source:\nN=  ");      /*輸入信源符號(hào)的個(gè)數(shù)*/
  23.   scanf("%d",&n);
  24.   for(i=0;i<=2*n-1;i++)   /*初始化huffman樹各個(gè)結(jié)點(diǎn)的值*/
  25.   {
  26.    huff_node[i].weight=0;
  27.     huff_node[i].parent=0;
  28.     huff_node[i].flag=0;
  29.     huff_node[i].lchild=-1;
  30.     huff_node[i].rchild=-1;
  31.    }
  32.    printf("Please input probability distribution :\n");
  33.    for(i=0;i<n;i++)    /*輸入信源輸入分布*/
  34.    {
  35.     printf("p[%d]=  ",i+1);
  36.     scanf("%f",&temp);
  37.     sum+=temp;
  38.     huff_node[i].weight=temp;
  39.     hx=hx-temp*3.332*log10(temp);  /*求信源的熵H(X)*/
  40.    }

  42.    if(fabs((sum-1))>0.00001) /*判斷信源輸入分布是否正確*/
  43.    {
  44.     printf("Error!");
  45.     exit(-1);
  46.    }

  48. /*構(gòu)建霍夫曼樹（參考數(shù)據(jù)結(jié)構(gòu)書）*/
  49.   for(i=0;i<n-1;i++)
  50.   {
  51.     m1=m2=1.1;
  52.     x1=x2=0;
  53.     for(j=0;j<n+i;j++)
  54.      {
  55.       if(huff_node[j].weight<m1&&huff_node[j].flag==0)
  56.       {
  57.        m2=m1;
  58.        x2=x1;
  59.        m1=huff_node[j].weight;
  60.        x1=j;
  61.       }
  62.       else
  63.       if(huff_node[j].weight<m2&&huff_node[j].flag==0)
  64.       {
  65.        m2=huff_node[j].weight;
  66.        x2=j;
  67.       }
  68.    
  69.     }
  70.          huff_node[x1].parent=n+i;
  71.   huff_node[x2].parent=n+i;         /*將找出的兩棵子樹合并為一棵子樹*/
  72.   huff_node[x1].flag=1;
  73.   huff_node[x2].flag=1;
  74.   huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
  75.   
  76.   if(huff_node[x1].weight==huff_node[x2].weight)       /*如果值相等，則將其置于最上面*/
  77.    {   
  78.     huff_node[n+i].lchild=x1;
  79.     huff_node[n+i].rchild=x2;
  80.    }
  81.    else
  82.    {
  83.     huff_node[n+i].lchild=x2;
  84.     huff_node[n+i].rchild=x1;
  85.    }
  86. }


  89. /*求信源符號(hào)的huffman編碼*/
  90.   for(i=0;i<n;i++)
  91.   {
  92.    cd=n;      
  93.    c=i;
  94.    p=huff_node[c].parent;
  95.    while(p!=0)      /*為信源si編碼*/
  96.      {
  97.          if(huff_node[p].lchild==c)    /*左孩子編碼為0*/
  98.      d[cd]=0;
  99.         else  
  100.      d[cd]=1;    /*左孩子編碼為1*/
  101.      cd=cd-1;
  102.      c=p;
  103.      p=huff_node[p].parent;
  104.      }
  105.     cd++;     
  106.   for(j=cd;j<=n;j++)   /*存儲(chǔ)信源si的huffman編碼*/
  107.   huff_code[i][j]=d[j];  
  108.   a[i]=cd;   
  109.   }
  110.   
  111. /*輸出信源符號(hào)的huffman編碼、信源熵和平均碼長(zhǎng)*/
  112.   printf("\ninformaition source\thuffmancode\n");
  113.   for(i=0;i<n;i++)
  114.   {
  115.     printf("p[%d]=%2.3f\t\t",i+1,huff_node[i].weight);/*輸出信源分布*/
  116.     for(j=a[i];j<=n;j++)
  117.     printf("%d",huff_code[i][j]);              /*輸出huffman編碼*/
  118.     /*求平均碼長(zhǎng)*/
  119.     L=L+(n+1-a[i])*huff_node[i].weight;                /*(n-cd+1)表示的是信源符號(hào)si的碼長(zhǎng)*/            
  120.     printf("\n");
  121.   }
  122.   printf("\nH(X)=%.2f bit/Symbol\n",hx);/*輸出信源熵*/
  123.   printf("The average length of code is:\tL=%.2f\n",L);/*輸出平均碼長(zhǎng)*/
  124.   printf("The rate is:\tR=%.3f",hx/L);           /*輸出編碼效率*/
  125. }
  126.   
復(fù)制代碼






歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1