详解哈夫曼编码
概述
通常的编码方法有固定长度和不等长度编码两种。
最优编码方案的目的是使总码长度最短。利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。如果采用等长的编码方案，假设所有字符的编码都等长，则表示n个不同的字符需要位。例如三个不同的字符a,b,c，至少需要2位二进制数表示：a:00，b:01，c:10。如果每个字符的使用频率相等的话，固定长度编码是空间效率最高的方法。在这里我们讨论的是不等长度编码.
1.设计哈夫曼树
不等长编码方法需要解决两个关键问题：
（1）编码尽可能的短
使用频率高的字符编码较短，使用频率低的编码较长，可提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。(在哈夫曼树中,频率越高,距根节点也就越近,编码长度也就越短.)
（2）不能有二义性
解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。(在哈夫曼树中编码的字符是树的叶子,这样的话,字符的编码就不可能是另外一个字符的前缀)
1952年，数学家D.A.Huffman提出了用字符在文件中出现的频率来建议一个用0，1串表示各字符的最佳编码方式，称为Huffman编码。哈夫曼编码很好的解决了上述两个关键问题，广泛地应用于数据压缩，尤其是远距离通信和大容量数据存储，常用的JPEG图片就是采用哈夫曼编码压缩的。
哈夫曼编码的基本思想是以字符的使用频率作为权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。
程序设计思路:
构造一棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用频率作为叶子结点的权值，以自底向上的方式，通过n-1次的“合并”运算后构造出的树。核心思想是让权值大的叶子离根最近。
哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中。
注意
确定合适的数据结构(包括哈夫曼节点的结构体和编码的结构体)。
哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点(n-1次的“合并”产生n-1个节点,加上之前的n个节点共2n-1个节点.)。
构成哈夫曼树后，为求编码需从叶子结点出发走一条从叶子到根的路径。(因为如果从根开始编码,由于叶子不唯一,那么走的时候向左走或者向右走也就无法不确定,处理起来不容易;而如果是从叶子到根,那么每次如果是左孩子就编码为0,右孩子就编码为1,最后逆序输出即可.)
译码需要从根出发走一条从根到叶子的路径。那么对于每个结点而言，需要知道每个结点的权值(这个是必须知道的,因为在建造哈夫曼树时总是选取两个权值小的)、双亲(在编码时需要根据双亲来判断是左孩子还是右孩子)、左孩子、右孩子(左右孩子也是必须的,不然咋构成一棵树,而且还得用于判断左右孩子…)和结点的信息(也是必须的)。
参考代码1(使用静态数组)
#include<iostream> #include<string> using namespace std; const int MAXBIT = 100;//编码数组的长度 const int MAXVALUE = 10000; const int MAXLEAF = 30;//叶子节点数 const int MAXNODE = 2*MAXLEAF-1;//树中所有的节点数 typedef struct{//节点结构体 double weight; int parent; int lchild; int rchild; char value; } HNodeType; typedef struct{ int bit[MAXBIT];//存储编码的数组 int start;//编码开始下标 }HCodeType; // 编码结构体 HNodeType HuffNode[MAXNODE];//存放哈夫曼树的节点 HCodeType HuffCode[MAXLEAF]; //编码结构体数组 int n; int x1,x2;//最小和次小权重节点的索引 double m1,m2;//最小和次小的权重 void HuffmanTree(){//构建哈夫曼树 for(int 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 = '#'; } for(int i = 0; i < n; i++){ cin>>HuffNode[i].value>>HuffNode[i].weight;//叶子节点进行初始化 } for(int i = 0; i < n-1; i++){//构造树 n-1次合并,n-1个新生成节点 m1 = m2 = MAXVALUE;//x1,x2,m1m2,进行初始化. x1 = x2 = MAXVALUE; for(int j = 0; j < n+i; j++){//从0--j中寻找两个最小的. 此处用到了贪心思想. if(HuffNode[j].weight < m1 && HuffNode[j].parent == -1){//如果比最小的还要小,则m1,x1进行更新,次小的m2,x2更新为以前最小的. m2 = m1; x2 = x1; m1 = HuffNode[j].weight; x1 = j; }else if(HuffNode[j].weight < m2 && HuffNode[j].parent == -1){//如果比 m1大,比m2小.则只更新m2 m2 = HuffNode[j].weight; x2 = j; } } //更新找到的最小节点和新生成的节点信息 HuffNode[x1].parent = n+i; HuffNode[x2].parent = n+i; HuffNode[n+i].lchild = x1; HuffNode[n+i].rchild = x2; HuffNode[n+i].weight = m1+m2; cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl; } } void HuffmanCode(){//哈夫曼编码 HCodeType cd; int c,p; for(int i = 0; i <n ;i++){//n个编码 cd.start = n-1;//cd可以每次不更新,因为每次都要生成会进行覆盖. c = i; p = HuffNode[i].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[p].parent; } for(int j = cd.start+1; j < n; j++){ HuffCode[i].bit[j] = cd.bit[j]; } HuffCode[i].start = cd.start+1; } } int main() { cout<<"Please input n:"<<endl; cin>>n; HuffmanTree(); cout<<"------------"<<endl; HuffmanCode(); for(int i = 0;i < n; i++){ cout<<HuffNode[i].value<<": Huffman Code is:"; for(int j = HuffCode[i].start; j < n; j++){ cout<<HuffCode[i].bit[j]; } cout<<endl; } return 0; } // 6 //a 0.05 //b 0.32 //c 0.18 //d 0.07 //e 0.25 //f 0.13
运行结果:
参考代码2(使用动态数组)
#include<iostream> #include<string> using namespace std; const int MAXBIT = 100;//编码数组的长度 const int MAXVALUE = 10000; const int MAXLEAF = 30;//叶子节点数 const int MAXNODE = 2*MAXLEAF-1;//树中所有的节点数 typedef struct{//节点结构体 double weight; int parent; int lchild; int rchild; char value; } HNodeType; typedef struct{ int *bit;//存储编码的数组 int len;//编码长度 }HCodeType; // 编码结构体 HNodeType HuffNode[MAXNODE];//存放哈夫曼树的节点 HCodeType HuffCode[MAXLEAF]; //编码结构体数组 int n; int x1,x2;//最小和次小权重节点的索引 double m1,m2;//最小和次小的权重 void HuffmanTree(){//构建哈夫曼树 for(int 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 = '#'; } for(int i = 0; i < n; i++){ cin>>HuffNode[i].value>>HuffNode[i].weight;//叶子节点进行初始化 } for(int i = 0; i < n-1; i++){//构造树 n-1次合并,n-1个新生成节点 m1 = m2 = MAXVALUE;//x1,x2,m1m2,进行初始化. x1 = x2 = MAXVALUE; for(int j = 0; j < n+i; j++){//从0--j中寻找两个最小的. 此处用到了贪心思想. if(HuffNode[j].weight < m1 && HuffNode[j].parent == -1){//如果比最小的还要小,则m1,x1进行更新,次小的m2,x2更新为以前最小的. m2 = m1; x2 = x1; m1 = HuffNode[j].weight; x1 = j; }else if(HuffNode[j].weight < m2 && HuffNode[j].parent == -1){//如果比 m1大,比m2小.则只更新m2 m2 = HuffNode[j].weight; x2 = j; } } //更新找到的最小节点和新生成的节点信息 HuffNode[x1].parent = n+i; HuffNode[x2].parent = n+i; HuffNode[n+i].lchild = x1; HuffNode[n+i].rchild = x2; HuffNode[n+i].weight = m1+m2; cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl; } } void HuffmanCode(){//哈夫曼编码 HCodeType cd; int c,p,len2;//len2:数组的长度 cd.bit = new int[MAXBIT];//分配空间. for(int i = 0; i <n ;i++){//n个编码 cd.len = n-1;//cd可以每次不更新,因为每次都要生成会进行覆盖. c = i; p = HuffNode[i].parent; while(p!=-1){ if(HuffNode[p].lchild == c){//如果是左孩子 cd.bit[cd.len] = 0; }else{ cd.bit[cd.len] = 1; } cd.len--; c = p; p = HuffNode[p].parent; } cd.len++; len2 =n-cd.len; // n-1 -(cd.len) + 1 n - cd.len HuffCode[i].bit = new int[len2]; for(int j = 0; j < len2; j++){ HuffCode[i].bit[j] = cd.bit[cd.len+j]; } HuffCode[i].len = len2; } delete(cd.bit);//释放内存; } int main() { cout<<"Please input n:"<<endl; cin>>n; HuffmanTree(); cout<<"------------"<<endl; HuffmanCode(); for(int i = 0;i < n; i++){ cout<<HuffNode[i].value<<": Huffman Code is:"; for(int j = 0; j < HuffCode[i].len; j++){ cout<<HuffCode[i].bit[j]; } cout<<endl; } return 0; }
由于编码长度并不是等长的,所以使用动态数组可以明显的节约内存空间.
2.带权路径长度(WPL)
WPL=每个叶子的权值×该叶子到根的路径长度 之和
哈夫曼树带权路径长度之和等于各新生成结点的权值之和。
因为对于一个节点.路径长度与新生成节点权值之和中所包含的该节点出现的次数正好相同.如2好节点,该节点 wpl = 18 * 2 ,而新节点43和100也包含了该节点.所以计算时结果是一样的.
10^6个这样的字符，其哈夫曼编码的长度是多少？如果采用等长编码，其编码长度是多少？
本哈夫曼树中WPL= (100+43+57+25+12=237)/100 = 2.37 由于频率扩大了2倍,所以总编码长度为10^6 * 2.37
如果使用登长, 2^2 < 6 < 2^3 所以每个字符编码的长度为3,总编码长度为10^6*3
