《算法导论》实验四：哈夫曼（Huffman）编码问题（C++实现）

一、题目描述

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示：

有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。

二、算法设计与分析

1、前缀码：

对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。
译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。

图-1a 与固定长度编码对应的树; 图-1b 对应于最优前缀编码的树
从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。
给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)。dT(c)也是字符c的前缀码长。则平均码长定义为：

使平均码长达到最小的前缀码编码方案称为C的最优前缀码。

2、构造哈夫曼编码：

哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下：
(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
(2)算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。
(3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。

构造过程如图-2所示：

图-2 哈夫曼树构造过程

三、结果与分析

本实验以算法导论书中的例题为测试用例，来验证算法的正确性。即

实验结果截图如下图-7，结果与题目描述中给出的变长代码字一样：

图-7 实验结果截图

四、实验总结

1、实验结果与给出的变长代码字一样，算法正确，且哈夫曼编码问题是一个贪心算法问题。采用哈夫曼编码技术可以最小化总的编码长度，从而实现数据文件的压缩存储。
2、构造好哈夫曼树后，可用排列树回溯法来打印哈夫曼编码，即遇到左子树向左走，vector添加记录0；遇到右子树向右走，vector添加记录1；走到叶子节点并打印出叶节点的编码后回溯，同时往上退一层，则vector弹出一个值。如此不断回溯下去，即可打印所有字符编码。

五、源代码（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//Huffman树的节点类
typedef struct Node
{ char value; //结点的字符值    int weight; //结点字符出现的频度 Node *lchild,*rchild; //结点的左右孩子
}Node;

//自定义排序规则，即以vector中node结点weight值升序排序
bool ComNode(Node *p,Node *q)
{ return p->weight<q->weight;
}

//构造Huffman树，返回根结点指针
Node* BuildHuffmanTree(vector<Node*> vctNode)
{ while(vctNode.size()>1) //vctNode森林中树个数大于1时循环进行合并 { sort(vctNode.begin(),vctNode.end(),ComNode);   //依频度高低对森林中的树进行升序排序 Node *first=vctNode[0]; //取排完序后vctNode森林中频度最小的树根 Node *second=vctNode[1];   //取排完序后vctNode森林中频度第二小的树根 Node *merge=new Node; //合并上面两个树 merge->weight=first->weight+second->weight; merge->lchild=first; merge->rchild=second; vector<Node*>::iterator iter; iter=vctNode.erase(vctNode.begin(),vctNode.begin()+2); //从vctNode森林中删除上诉频度最小的两个节点first和second vctNode.push_back(merge); //向vctNode森林中添加合并后的merge树 } return vctNode[0]; //返回构造好的根节点
}

//用回溯法来打印编码
void PrintHuffman(Node *node,vector<int> vctchar)
{ if(node->lchild==NULL && node->rchild==NULL) {//若走到叶子节点，则迭代打印vctchar中存的编码 cout<<node->value<<": "; for(vector<int>::iterator iter=vctchar.begin();iter!=vctchar.end();iter++) cout<<*iter; cout<<endl; return; } else { vctchar.push_back(1); //遇到左子树时给vctchar中加一个1 PrintHuffman(node->lchild,vctchar); vctchar.pop_back(); //回溯，删除刚刚加进去的1 vctchar.push_back(0); //遇到左子树时给vctchar中加一个0 PrintHuffman(node->rchild,vctchar); vctchar.pop_back(); //回溯，删除刚刚加进去的0 }
}

int main()
{ cout<<"************ Huffman编码问题 ***************"<<endl; cout<<"请输入要编码的字符,并以空格隔开（个数任意）："<<endl; vector<Node*> vctNode; //存放Node结点的vector容器vctNode char ch; //临时存放控制台输入的字符 while((ch=getchar())!='\n') { if(ch==' ')continue; //遇到空格时跳过，即没输入一个字符空一格空格 Node *temp=new Node; temp->value=ch; temp->lchild=temp->rchild = NULL; vctNode.push_back(temp);  //将新的节点插入到容器vctNode中 } cout<<endl<<"请输入每个字符对应的频度，并以空格隔开："<<endl; for(int i=0;i<vctNode.size();i++) cin>>vctNode[i]->weight; Node *root = BuildHuffmanTree(vctNode);   //构造Huffman树，将返回的树根赋给root vector<int> vctchar; cout<<endl<<"对应的Huffman编码如下："<<endl; PrintHuffman(root,vctchar); system("pause");
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
 

文章来源: blog.csdn.net，作者：allinallinallin，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/to_Baidu/article/details/50302071