哈夫曼编码的原理及C++实现
- 格式：docx
- 大小：46.67 KB
- 文档页数：4
哈夫曼编码的原理及C++实现
哈夫曼编码（Huffman Coding）是一种非常经典的编码方式，实现起来也很简单，在实际的笔试面试过程中有可能会遇到，这里介绍一下它的原理和一个使用优先队列的实现版本。
一 编码原理
哈夫曼编码是一种可变长的编码，它依据字符出现的概率来决定字符编码的长度，使得出现概率大的字符编码长度短，出现概率小的字符的编码长度长，于是可以减少整体的编码的长度。
哈弗曼编码时首先根据待编码的文本统计出每个字符出现的概率，组成初始的节点。然后每次取出概率最小的两个节点，新建一个节点，使得新建节点的左右儿子为选取的两个节点，并且其概率是两个节点概率之和，把新建的节点再放进所有节点中重新选择最小的两个节点。重复此过程直到只剩一个节点，这个就是哈夫曼树的根节点。
以下以字符串"aaaaaabbbbccddd"为例进行说明，为了方便，以字符出现的频数来代替频率（实际中通常使用的是频率，二者效果上是一样的），经过统计，可以知道每个字符出现的频数为
a b c d
6 4 2 3
具体建树过程如下：
（1）首先节点权值为6、4、2、3，选择最小的2和3，组成一个根节点为5的组合节点。
（2）当前节点权值为6、4、5，选择最小的4和5，组成一个根节点为9的组合节点。
（3）当前节点权值为6、9，选择最小的6和9，组成一个根节点为15的组合节点。
（4）当前节点权值为15，只有一个节点，哈夫曼树建立完成。
图示如下：
要从哈夫曼树得到每个字符的编码，只要在哈夫曼树中从根节点遍历到该字符节点，每次向左走时加一个0，向右走时加一个1，最终得到的字符串即为该字符的编码字符串。
如从上图可以看到，a的编码为0，b的编码为10，c的编码为110，d的编码为111。
当遇到一个新的字符串时，比如说"abcd"，要对其编码，只需要把其中的每个字符相应地替换成其编码字符串即可。
当已知一个编码后的字符串，比如说"010110111"，要对其解码时，只需从左到右依次扫描该编码串，当读到的串在哈弗曼编码表里有对应的字符时即解码为该字符，然后继续扫描。
在这个例子中，读到第一个0时即可解码为a，读到10时可以解码为b，以此类推，最终得到解码后的结果为abcd。
哈夫曼编码之所以可以这样解码，是因为它是一种前缀编码，任何一个字符的编码都不会是另一个字符编码的前缀。于是给定一个编码后的串，其解码的结果是唯一的。
二 代码实现
这里的哈夫曼树的节点主要包含两个成员：字符及其频率，另外还必须有其左右儿子指针，父亲节点指针可以看情况添加，这里暂时不考虑。
为了方便，还添加了一个构造函数，可以给成员赋默认值。
struct node //哈夫曼树节点
{
char ch; //字符
double freq; //出现频率
node *lchild, *rchild; //左右儿子
node(char c = 0, double f = 0, node *l = NULL, node *r = NULL) :
ch(c), freq(f), lchild(l), rchild(r){}
};
为了提高效率，程序中使用了STL中的优先队列来选择权值最小的节点。队列的成员是节点的指针，为了选择权值最小的节点，需要自己定义比较的规则，以下是定义比较规则的仿函数，实质就是一个重载了括号运算符的类。
注意实现最小的权值优先，仿函数里应该使用的是大于运算。
struct cmp //仿函数，实现最小优先队列
{
bool operator()(node*& a, node*& b)
{
return a->freq > b->freq;
}
};
然后是具体的建树过程。首先需要统计字符出现的次数，可以非常方便地使用STL的map实现。然后构造初始节点送入优先队列，再循环取出最小的两个节点，生成新的节点放入队列。直到队列只剩一个节点，即为树的根节点。
node* createTree(string str) //对一段文本构建哈夫曼树
{
//统计字符集及其出现频数
map charSet;
for (int i = 0; i < str.length(); i++)
charSet[str[i]]++;
//查看统计结果
//for(map::iterator p = charSet.begin(); p != charSet.end(); p++)
// cout << p->first << " " << p->second << endl;;
//初始节点进入优先队列
priority_queue, cmp> que;
for(map::iterator p = charSet.begin(); p != charSet.end(); p++) que.push(new node(p->first, (double)p->second / str.length()));
//每次取出频率最小的两个节点，生成一个新的节点并重新入队
while (que.size() > 1)
{
node *l = que.top(); que.pop();
node *r = que.top(); que.pop();
node *newnode = new node(0, l->freq + r->freq, l, r);
que.push(newnode);
}
return que.top();
}
得到哈夫曼树之后基本就完成了，接下来可以遍历哈夫曼树得到每个字符的编码串。注意每次向左走时加0，向右走时加1，到达叶子节点即为该字符的编码。
这里只是简单打印了编码表的信息，没有保存起来，如果需要可以再次使用STL的map进行保存。
void printInfo(const node *tree, string code) //递归打印编码信息
{
if (tree->lchild == NULL && tree->rchild == NULL)
{
cout << tree->ch << ": " << code << endl;
return;
}
if (tree->lchild != NULL) printInfo(tree->lchild, code + '0');
if (tree->rchild != NULL) printInfo(tree->rchild, code + '1');
}
解码时可以在遍历编码串的同时沿着哈夫曼树走，到达叶子节点时即得到一个解码字符，同时再次回到根节点继续遍历。最后得到解码的结果。
string decode(const node *tree, string str) //解码
{
string ret = "";
const node *p = tree;
for (int i = 0; i < str.length(); i++)
{
p = str[i] == '0' ? p->lchild : p->rchild;
if (p->lchild == NULL && p->rchild == NULL) //得到一个字符
ret += p->ch, p = tree;
}
return ret; }
因为这里的节点都是使用new运算符动态申请得到，不再使用时需要释放掉申请到的资源，以免造成内存泄露。
void deleteTree(node *tree) //释放哈夫曼树申请的节点
{
if (tree->lchild != NULL) deleteTree(tree->lchild);
if (tree->rchild != NULL) deleteTree(tree->rchild);
delete(tree);
}
下面是一个简单的测试例子，看程序是否正常运行。
int main ()
{
string encodeStr = "aaaaaabbbbccddd";
node *tree = createTree(encodeStr);
printInfo(tree, "");
string decodeStr = "010110111";
string str = decode(tree, decodeStr);
cout << decodeStr << ": " << str << endl;
/*运行结果
a: 0
b: 10
c: 110
d: 111
010110111: abcd
*/
}
