2014.07.06 16:47
简介：
给定一段有固定符号集合S构成的文本T，集合S中总共有n种符号。如果对于每种符号，使用一种不同的由‘0’和‘1’构成的位字符串来代替，比如：
‘a’->‘01’
‘c’->'101'
'd'->‘11’
...
例如，文本“acd”经过这种编码就变成了“0110111”。
这样，就可以把文本T中的符号全部替换为‘0’‘1’构成的二进制串，这样就能以二进制文件的形式保存信息了。并且，一个ASCII字符默认占用一个字节，也就是8位。但使用这种不定长的编码方式一个字符占用的位数可能小于8位，于是可能达到压缩数据的效果。Huffman编码的规则，就是通过选定合适的编码，使得这段文本经过编码转换后的二进制串的长度最短。
图示：
用算法描述Huffman编码的过程还是比较简单的：
1. 定义键值对<字符, 出现频率>，比如<a, 12>表示a字符出现了12次。
2. 每次选出出现频率最低的两个字符，组合成一个字符（字符当然不能组合，但频率是可以相加的），重新放入候选集中。
3. 这个组合的过程，其实就是构建二叉树的过程
新结点的频率等于两个子节点的频率之和，而新节点上对应的字符没有实际意义，所以我们姑且标记为‘?’。
每经过一轮这样的操作，我们取出两个结点，放回一个结点，所以要经过n-1轮才能得到一棵完整的树，比如这样：
上图中给出了这棵树对应的字符编码方式，其实每个字符的编码对应于从根结点到叶结点的路径，‘0’向左，‘1’向右。
由于组合两个结点时，左右次序可以调换，因此同一套文本与字符可以构建出2^(n-1)种的Huffman树。任何一种的效果都是相同的，目的只有一个：压缩数据。
如何每次选出最小的两个呢？最小堆。
问题是：为什么每次选出最小的，结果就是最好的呢？贪婪。
实现：
// A simple illustration for
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std; // The character statistics type
typedef unordered_map<char, int> StatType;
// The character encoding type
typedef unordered_map<char, string> EncodeType; struct TreeNode {
char ch;
int weight;
TreeNode *left;
TreeNode *right; TreeNode(char _ch, int _weight): ch(_ch), weight(_weight),
left(nullptr), right(nullptr) {}
}; struct GreaterFunctor {
bool operator () (const TreeNode *x, const TreeNode *y) {
return x->weight > y->weight;
}
}; void deleteTree(TreeNode *&root)
{
if (root == nullptr) {
return;
} else {
deleteTree(root->left);
deleteTree(root->right);
delete root;
root = nullptr;
}
} void calculateEncoding(const TreeNode *root, EncodeType &encoding, string &path)
{
if (root == nullptr) {
return;
} if (root->ch != '\0') {
encoding[root->ch] = path;
return;
} path.push_back('');
calculateEncoding(root->left, encoding, path);
path.pop_back(); path.push_back('');
calculateEncoding(root->right, encoding, path);
path.pop_back();
} void huffmanEncoding(const StatType &statistics, EncodeType &encoding)
{
priority_queue<TreeNode *, vector<TreeNode *>, GreaterFunctor> pq; int n; n = ;
for (StatType::const_iterator sta_it = statistics.begin();
sta_it != statistics.end(); ++sta_it) {
pq.push(new TreeNode(sta_it->first, sta_it->second));
++n;
} TreeNode *p1, *p2, *p3;
int i;
for (i = ; i < n - ; ++i) {
p1 = pq.top();
pq.pop();
p2 = pq.top();
pq.pop(); p3 = new TreeNode('\0', p1->weight + p2->weight);
p3->left = p1;
p3->right = p2;
pq.push(p3);
} TreeNode *root = pq.top();
pq.pop(); string code = "";
calculateEncoding(root, encoding, code);
deleteTree(root);
} int main()
{
int i, n;
string s;
int weight;
StatType statistics;
EncodeType encoding; while (cin >> n && n > ) {
for (i = ; i < n; ++i) {
cin >> s >> weight;
statistics[s[]] = weight;
}
huffmanEncoding(statistics, encoding); for (EncodeType::const_iterator enc_it = encoding.begin();
enc_it != encoding.end(); ++enc_it) {
cout << enc_it->first << ':' << enc_it->second << endl;
}
cout << endl; statistics.clear();
encoding.clear();
} return ;
}