静态霍夫曼编码（Huffman Coding）

小咪咪 2022-05-09 07:44 250阅读 0赞

转载：[https://blog.csdn.net/xgf415/article/details/52628073/][https_blog.csdn.net_xgf415_article_details_52628073]

霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。

霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

**霍夫曼编码的具体步骤如下：**

> 1）将信源符号的概率按减小的顺序排队。
> 
> 2）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率１。
> 
> 3）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。   
> 
> 4）将每对组合的左边一个指定为0，右边一个指定为1（或相反）。

例：现有一个由5个不同符号组成的30个符号的字符串：

BABACAC ADADABB CBABEBE DDABEEEBB

1首先计算出每个字符出现的次数（概率）：

![Center][]

2把出现次数（概率）最小的两个相加，并作为左右子树，重复此过程，直到概率值为1

![Center 1][]

第一次：将概率最低值3和4相加，组合成7：

![Center 2][]

第二次：将最低值5和7相加，组合成12：

![Center 3][]

第三次：将8和10相加，组合成18：

![Center 4][]

第四次：将最低值12和18相加，结束组合：

![Center 5][]

3 将每个二叉树的左边指定为0，右边指定为1

![Center 6][]

4 沿二叉树顶部到每个字符路径，获得每个符号的编码

![Center 7][]

我们可以看到出现次数（概率）越多的会越在上层，编码也越短，出现频率越少的就越在下层，编码也越长。当我们编码的时候，我们是按“bit”来编码的，解码也是通过bit来完成，如果我们有这样的bitset “10111101100″ 那么其解码后就是 “ABBDE”。所以，我们需要通过这个二叉树建立我们Huffman编码和解码的字典表。

这里需要注意的是，Huffman编码使得每一个字符的编码都与另一个字符编码的前一部分不同，不会出现像’A’：00，  ’B’：001，这样的情况，解码也不会出现冲突。

**霍夫曼编码的局限性**

利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限；输入符号数受限于可实现的码表尺寸；译码复杂；需要实现知道输入符号集的概率分布；没有错误保护功能。

代码：

>     #include <stdio.h>
>     #include<stdlib.h>
>     #include<string>
>     #include <iostream>
>      
>     #define MAXBIT      100
>     #define MAXVALUE  10000
>     #define MAXLEAF     30
>     #define MAXNODE    MAXLEAF*2 -1
>      
>     typedef struct 
>     {
>         int bit[MAXBIT];
>         int start;
>     } HCodeType;        /* 编码结构体 */
>     typedef struct
>     {
>         int weight;
>         int parent;
>         int lchild;
>         int rchild;
>         char value;
>     } HNodeType;        /* 结点结构体 */
>      
>     /* 构造一颗哈夫曼树 */
>     void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
>     { 
>         /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
>         x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
>         int i, j, m1, m2, x1, x2;
>         /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
>         for (i=0; i<2*n-1; i++)
>         {
>             HuffNode[i].weight = 0;//权值 
>             HuffNode[i].parent =-1;
>             HuffNode[i].lchild =-1;
>             HuffNode[i].rchild =-1;
>             HuffNode[i].value=' '; //实际值，可根据情况替换为字母  
>         } /* end for */
>      
>         /* 输入 n 个叶子结点的权值 */
>         for (i=0; i<n; i++)
>         {
>             printf ("Please input char of leaf node: ", i);
>             scanf ("%c",&HuffNode[i].value);
>      
>             getchar();
>         } /* end for */
>         for (i=0; i<n; i++)
>         {
>             printf ("Please input  weight of leaf node: ", i);
>             scanf ("%d",&HuffNode[i].weight);
>      
>             getchar();
>         } /* end for */
>      
>         /* 循环构造 Huffman 树 */
>         for (i=0; i<n-1; i++)
>         {
>             m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
>             x1=x2=0;
>             /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
>             for (j=0; j<n+i; j++)
>             {
>                 if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
>                 {
>                     m2=m1; 
>                     x2=x1; 
>                     m1=HuffNode[j].weight;
>                     x1=j;
>                 }
>                 else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
>                 {
>                     m2=HuffNode[j].weight;
>                     x2=j;
>                 }
>             } /* end for */
>             /* 设置找到的两个子结点 x1、x2 的父结点信息 */
>             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;
>      
>             printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
>             printf ("\n");
>         } /* end for */
>      
>     } /* end HuffmanTree */
>      
>     //解码 
>     void decodeing(char string[],HNodeType Buf[],int Num)
>     {
>         int i,tmp=0,code[1024];
>         int m=2*Num-1;
>         char *nump;
>         char num[1024];
>         for(i=0;i<strlen(string);i++)
>         {
>             if(string[i]=='0')
>                 num[i]=0;        
>             else
>                 num[i]=1;                    
>         } 
>         i=0;
>         nump=&num[0];
>      
>         while(nump<(&num[strlen(string)]))
>         {tmp=m-1;
>         while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
>         {
>             if(*nump==0)
>             {
>                 tmp=Buf[tmp].lchild ;          
>             } 
>             else tmp=Buf[tmp].rchild;
>             nump++;
>      
>         } 
>         printf("%c",Buf[tmp].value);                                  
>         }
>     }
>      
>     int main(void)
>     {
>      
>         HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
>         HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
>         int i, j, c, p, n;
>         char pp[100];
>         printf ("Please input n:\n");
>         scanf ("%d", &n);
>         HuffmanTree (HuffNode, n);
>      
>         for (i=0; i < n; i++)
>         {
>             cd.start = n-1;
>             c = i;
>             p = HuffNode[c].parent;
>             while (p != -1)   /* 父结点存在 */
>             {
>                 if (HuffNode[p].lchild == c)
>                     cd.bit[cd.start] = 0;
>                 else
>                     cd.bit[cd.start] = 1;
>                 cd.start--;        /* 求编码的低一位 */
>                 c=p;                    
>                 p=HuffNode[c].parent;    /* 设置下一循环条件 */
>             } /* end while */
>      
>             /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
>             for (j=cd.start+1; j<n; j++)
>             { HuffCode[i].bit[j] = cd.bit[j];}
>             HuffCode[i].start = cd.start;
>         } /* end for */
>      
>         /* 输出已保存好的所有存在编码的哈夫曼编码 */
>         for (i=0; i<n; i++)
>         {
>             printf ("%d 's Huffman code is: ", i);
>             for (j=HuffCode[i].start+1; j < n; j++)
>             {
>                 printf ("%d", HuffCode[i].bit[j]);
>             }
>             printf(" start:%d",HuffCode[i].start);
>      
>             printf ("\n");
>      
>         }
>         printf("Decoding?Please Enter code:\n");
>         scanf("%s",&pp);
>         decodeing(pp,HuffNode,n);
>         getchar();
>         return 0;
>     }

上面是人家的文章，写的挺好，比较容易看懂。

字符和译码之间我用来map来写。同时，翻译的时候，也可以再反向建立一个map，这样会大大节省翻译实践。

（我尝试了下，如果map中没有此元素，输出为“空”）

#include<iostream> 
    #include<climits>//INT_MAX函数头文件 
    #include<map>
    #include<algorithm>//min函数的头文件 
    using namespace std;
    
    #define MAXLEAF 30//最多的叶子数 
    #define MAXNODE MAXLEAF*2-1 //最多的节点数 
    #define MAXBIT 30//编码长度不超过30 
    
    typedef struct//节点的结构体 
    {
    	char value;
    	int weight;
    	int parent;
    	int lchild;
    	int rchild;
    }HNodeType;
    
    void  HuffmanTree(HNodeType HuffNode[],int n)
    {
    	int i,j;//用来循环记数 
    	for(i=0;i<2*n-1;i++)//对节点进行初始化 
    	{
    		HuffNode[i].value=' ';
    		HuffNode[i].weight=0;
    		HuffNode[i].parent=-1;
    		HuffNode[i].lchild=-1;
    		HuffNode[i].rchild=-1;
    	}
    	
    	printf("enter the value and weight\n");
    	for(i=0;i<n;i++)//输入叶子节点 
    	{	
    		 scanf("%c",&HuffNode[i].value);
    		 scanf("%d",&HuffNode[i].weight);
    		 getchar();//接收回车 
    	}
    	
    	//建立huffman树 
    	int x1,x2,w1,w2;//分别用来记录权值最小两片叶子在数组中的位置和权值
    	for(i=0;i<n-1;i++)//n-1为最后只有一棵树 
    	{   
    		x1=x2=0;
    		w1=w2=INT_MAX;                  
    		for(j=0;j<n+i;j++)//n+i因为会增加新的节点 
    		{                 //找寻最小权值的两片叶子 
    			if(HuffNode[j].weight<w1&&HuffNode[j].parent==-1)
    			{
    				x2=x1;
    				w2=w1;
    				x1=j;
    				w1=HuffNode[j].weight; 
    			}
    			else if(HuffNode[j].weight<w2&&HuffNode[j].parent==-1) 
    			{
    				x2=j;
    				w2=HuffNode[j].weight; 
    			}
    		}
    		HuffNode[x1].parent=n+i;
    		HuffNode[x2].parent=n+i;
    		HuffNode[n+i].lchild=x1;//建立的时候左孩子小于右孩子 
    		HuffNode[n+i].rchild=x2;
    		HuffNode[n+i].weight=w1+w2; 
    		
    		/* 用于测试 */
    		printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  
            printf ("\n");
    	}
    } 
    
    void HuffCode(map<char,string>&Huffcode,HNodeType HuffNode[],int n)
    {
    	char ch;//存储当前的叶子字符 
    	string s;//存储当前叶子字符对应的编码 
    	int i,p,j,child;
    	char tmp[MAXBIT]; 
    	for(i=0;i<n;i++)
    	{	
    		j=0;
    		child=i;//当前的孩子 
    		p=HuffNode[i].parent;
    		ch=HuffNode[i].value;
    		s.clear();
    		while(p!=-1)
    		{
    			if(HuffNode[p].lchild==child)
    				tmp[j++]='0';
    			else 
    				tmp[j++]='1'; 
    			child=p;
    			p=HuffNode[child].parent;
    		}
    		for(j--;j>=0;j--)
    			s.push_back(tmp[j]);
    		Huffcode[ch]=s;	
    	}
    	
    	for(map<char,string>::iterator it=Huffcode.begin();it!=Huffcode.end();it++)
    		cout<<it->first<<"的编码："<<it->second<<endl; 
    } 
    
    void HuffDiscode(string &code,HNodeType HuffNode[],int n,string &ans)
    {
    	int i;
    	int p;
    	for(i=0;code[i];)//字符串的结束符为'/0'，ASSIC值为0 
    	{
    		p=2*n-1-1;//根节点 
    		while(HuffNode[p].lchild!=-1&&HuffNode[p].rchild!=-1)
    		{
    			if(code[i]=='0')//左孩子 
    				p=HuffNode[p].lchild; 
    			else
    				p=HuffNode[p].rchild;
    			i++; 
    		}
    		//cout<<HuffNode[p].value;
    		ans.push_back(HuffNode[p].value);
    	}
    }
    
    //实验数据A:20;B:6;C:6;E:15;G:13;
    //编码为A:11    B:000    C:001    E:10    G:01 
    int main()
    {
    	HNodeType HuffNode[MAXLEAF];
    	map<char,string>Huffcode;//用映射来存储字符和编码 
    	int n;
    	printf("enter the leaf nums:");
    	scanf("%d",&n);
    	getchar();
    	HuffmanTree(HuffNode,n);//构造huffman树 
    	HuffCode(Huffcode,HuffNode,n);//生成huffman编码 
    	
    	
    	//加密过程
    	int i;
    	string prev="ABCEG";
    	cout<<"原文为："<<prev<<endl<<"译文为："; 
    	for(i=0;prev[i];i++)
    		cout<<Huffcode[prev[i]];
    	cout<<endl;
    	
    	
    	//解密过程 
    	string code="110000011001";//ABCEG
    	cout<<"加密过的文件为：110000011001\n";//测试使用
    	string ans;
    	HuffDiscode(code,HuffNode,n,ans);
    	cout<<"译文为："<<ans<<endl;
    	
    	return 0;	
    }

结果：

![70][]

阅读文章：[哈夫曼编码——百度百科][Link 1]

[https_blog.csdn.net_xgf415_article_details_52628073]: https://blog.csdn.net/xgf415/article/details/52628073/
[Center]: /images/20220509/629468cce7fb443f8c77b1afd5357ad7.png
[Center 1]: /images/20220509/61e3fc5b369246d082c2a8eab5c38718.png
[Center 2]: /images/20220509/ec741a3a9e6247fdbd0dbc61aec54448.png
[Center 3]: /images/20220509/6f016eabf2394a2fb0a5fbe722ebe25f.png
[Center 4]: /images/20220509/734b6540f8674a639dd60b2e78e1e67e.png
[Center 5]: /images/20220509/15aa19e401864edeb6bb67ff06ea1d0e.png
[Center 6]: /images/20220509/dfd389fd838d4378aa2682ee3a149769.png
[Center 7]: /images/20220509/8c1f0dbd178c445882b32687019e6e88.png
[70]: /images/20220509/492123e348b349a183cf78fbd052bfc9.png
[Link 1]: https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81/1719730?fromtitle=HUFFMAN%E7%BC%96%E7%A0%81&fromid=364674&fr=aladdin