huffman无损压缩编码实验报告

（huffman编码）实验报告

  本文介绍了无损压缩编码中的霍夫曼（huffman）编码。Huffman编码是可变字长编码的一种，该方法完全依据字符出现概率来构造最优二叉树（huffman树），故有时又称为最佳编码。在文中，我们使用C++语言进行编码，从下到上进行了熵编码。

关键词：huffman、最优二叉树、熵编码、C++

Abstract

  The huffman (Huffman) coding of Lossless coding were introduced in this paper . Huffman coding is a kind of variable-word- length coding.The method is completely based on the characters appear probability to construct the optimal binary tree (Huffman tree), so it is sometimes referred to as the optimal coding. In this paper, we use c + + language to code, from bottom to top in the entropy coding.

Key words: huffman、optimal binary tree、entropy coding、C++

1、实验目的

1、理解无损压缩编码的优点和意义。

2、理解树、二叉树、huffman树的概念。

3、学会二叉树的C++编程，进行熵编码。

2、实验步骤

步骤①：按照符号出现概率大小的顺序对符号进行排序。

步骤②：把概率最小的两个符号组成一个节点P1。

步骤③：重复步骤②，得到节点P2，P3，P4，……，PN，形成一棵树，其中的PN称为根节点。

步骤④：从根节点PN开始到每个符号的树叶，从上到下标上0(上枝)和1(下枝)，至于哪个为1哪个为0则无关紧要，但通常把概率大的标成1，概率小的标成0。

步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出每个符号的代码。

3、实验程序设计

1、输入字符，定义三个字符串，输入字符串到words数组，并且求得其长度length。

char words[500],wds[500],wd[500];              //定义三个字符串，长度都不超过500

cin>>words;                                 //输入字符串

int length,len,m;   

length=strlen(words);                          //计算words字符串长度

2、对words字符串进行从小到大冒泡排序，并且将words中的元素全部赋给wds字符串。

void maopao(char wd[],int len)                    //函数冒泡排序

{  int i,j;   

   char t;

for(j=0;j<=len-1-1;j++)

for(i=0;i{ if(wd[i]>wd[i+1]) {

             t=wd[i];

             wd[i]=wd[i+1];

             wd[i+1]=t;      }

       } 

}

主函数：

maopao(words,length);                          //定义冒泡函数

cout<for(int i=0;i<=length;i++)                     //将words中的内容赋给wds

{  wds[i]=words[i];  }

3、将已经排序好的字符串中同种字符删除，使该字符在字符串中只剩下一个。得到wds的字符串长度len。

void typedelete(char *a1,int len)             //删除字符串中的同类字符使该字符只剩一个

{  while(*a1)  {

    if(*a1==*(a1+1))

    {  strcpy(a1,a1+1);

       continue;

    }

    a1++;      } 

} 

主函数：

typedelete(wds,length);                         //定义同类删除函数

cout<len=strlen(wds);                               //字符串wds的长度

4、定义两个数组entr1、entr2，分别用于存放输入字符串words中出现每个字符的频率与频数。定义log2函数用于计算熵。

double log2(double x)                             //定义log2函数计算熵值

{  double y;

   y=log10(x)/log10(2);

   return y;

}

主函数：

double entr1[500]={0,0,0};         //定义一个数组，存放每个字母出现的频率

int entr2[500]={0,0,0};          //定义一个数组，存放每个字母出现的频数，即为权值

double entropy=0;              //定义熵，即平均码长

int j;

for(i=0;ifor(j=0;j {if(wds[i]==words[j])  

{ entr2[i]++;}            //将每个字母出现地频数存放在entr2[]中

 }

for(i=0;i {  entr1[i]=(double)entr2[i]/length;}          //计算频率

i=0;

while(i{  entropy+=entr1[i]*(log2(1/entr1[i]));       //利用定义的log2函数计算熵

      i++;

}

for(i=0;i{ cout<cout<<'\\n';

for(i=0;i{ cout<cout<<'\\n';

cout<<"平均码长,即熵为entropy="<//到此主要是为了计算熵的值，也为霍夫曼编码做铺垫。

5、定义一个二叉树（huffman）结构体，包含了权值、父节点、左右子节点、状态值、编码。

struct huffmantree

{ int wei;                                        //权值 

  int prt;                                        //父节点

  int lch;                                        //左子节点 

  int rch;                                        //右子节点 

  int tmp;                                        

//中间变量，tmp=0 还未进行遍历 tmp=1 已近进行过向左遍历  tmp=2 已经进行过左右遍历 向上找到节点 char code[N];

  char code[N];

};

6、定义2*len个huffman树，调用huffman函数，利用结构体中的父节点、左右节点，将整个huffman树构造出来。其次进行huffman编码，通过判断tmp这个状态值，二叉树形成最优二叉树。最后进行编码的输出。

void select(huffmantree *HT,int n,int &i,int &j)  //该函数用于找最小值和次小值的位置 

{ int k;

  i=1; 

  while(HT[i].prt!=0) 

  {   i++;  }

for(k=i+1;k<=n;k++)

{ if((HT[k].prt==0)&&(HT[k].wei       i=k;  

  }

  j=1; 

  while((j==i)||(HT[j].prt!=0)) 

  {   j++;  }

for(k=j+1;k<=n;k++)

{ if((HT[k].prt=0)&&k!=i&&HT[k].wei      j=k; 

  }

}

void huffman(int w[],huffmantree *HT,int n)      //w存放n个字符的权值

{  int m=2*n-1;

   int i,k,j;

   huffmantree *p=0; 

for(p=HT+1,i=1;i<=m;i++,p++)

   {  HT[i].prt=0;  

      HT[i].lch=0;  

      HT[i].rch=0; 

   }

for(p=HT+1,i=1;i<=n;i++,p++)

   {  HT[i].wei=w[i-1]; } 

for(p=HT+n+1,i=n+1;i<=m;i++,p++)

   {  HT[i].wei=0;}

for(k=n+1;k<=m;k++)

   {  select(HT,k-1,i,j);                         // 找最小值和次小值的位置 

      HT[i].prt=k,HT[j].prt=k;                    // 找到i j 的父节点付给k 

      HT[k].lch=i,HT[k].rch=j;                    // 父节点的左右指针分别指向i, j  

      HT[k].wei=HT[i].wei+HT[j].wei; 

   }

}

void huffmancoding(huffmantree *HT,int n)         //n个叶子结点的huffman编码 从根节点开始编码

{  int BT=2*n-1; 

   int m=BT; 

   int l,r,p;

   char s1[100]="0",s2[100]="1";

   for(int i=0;i<=m;i++)                           //中间变量赋初值

   {   HT[i].tmp=0;  }

   strcpy(HT[m].code," "); 

   while(1)

   { l=HT[BT].lch;  r=HT[BT].rch;  p=HT[BT].prt;

        if(p==0&&HT[BT].tmp==2)   

            break;  

        if(l==0||r==0)

        {   HT[BT].tmp=2;  }                        //如果是叶子结点则给中间变量赋值2向上返回一节结点    

        if(HT[BT].tmp==0)                           //未进行过遍历，开始向左遍历 

        {   HT[BT].tmp=1;                           //已经进行过向左遍历   

            l=HT[BT].lch;  

            strcpy(HT[l].code,HT[BT].code);  

            strcat(HT[l].code,s1);   

            BT=l; 

        }

        else if(HT[BT].tmp==1)   

        {    HT[BT].tmp=2;    

             r=HT[BT].rch;    

             strcpy(HT[r].code,HT[BT].code);    

             strcat(HT[r].code,s2);   

             BT=r;  

        }

         else if(HT[BT].tmp==2)   

        {    p=HT[BT].prt;    BT=p;   } 

   }

}

void print(huffmantree HT[],int n)                //总共n个叶子节点

{  int i; 

   cout<<"源码："<for(i=1;i<=n;i++)

cout<   cout<<"Huffman编码："<for(i=1;i<=n;i++)

{ cout<}

主函数：

m=2*len-1;

huffmantree *HT;

HT=new huffmantree[m+1];

huffman(entr2,HT,len);

huffmancoding(HT,len);

print(HT,len);

delete HT;

4、实验结果

如图，输入字符串“ccaaZZAD.,”,之后的结果依次为words的长度、冒泡后的words、wds、删除同类字符的wds、频率、频数、熵、编码。

5、实验感想

  重新复习了C++编程，并且更加熟练地运用之。学习了树、二叉树、最优二叉树的构成、排序、遍历等，生动地反映了霍夫曼编码，巩固了所学知识。

6、参考书籍

●林福宗. 多媒体技术基础（第X版）[M].北京：清华大学出版社，200X.

●Ralf Steinmetz and Klara Nahrstedt. Multimedia: Computing, Communication & Application[M]. Prentice Hall, 1995. (清华大学出版社影印版)

●钟玉琢，蔡莲红，等. 多媒体计算机技术基础及应用[M]. 北京：高等教育出版社，2000.