首页 > 代码库 > Huffman
Huffman
huffman是非常基础的压缩算法。
实现霍夫曼树的方式有很多种，可以使用优先队列（Priority Queue）简单达成这个过程，给与权重较低的符号较高的优先级（Priority），算法如下：
⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n
⒉如果队列内的节点数>1，则：
⑴从队列中移除两个最大的Pi节点，即连续做两次remove(max(Pi), Priority_Queue)
⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和
⑶把（2）产生之节点加入优先队列中
⒊最后在优先队列里的点为树的根节点（root）
而此算法的时间复杂度（ Time Complexity）为O（n log n）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（log n）。
此外，有一个更快的方式使时间复杂度降至线性时间（Linear Time）O(n)，就是使用两个队列（Queue）创件霍夫曼树。第一个队列用来存储n个符号（即n个终端节点）的权重，第二个队列用来存储两两权重的合（即非终端节点）。此法可保证第二个队列的前端（Front）权重永远都是最小值，且方法如下:
⒈把n个终端节点加入第一个队列（依照权重大小排列，最小在前端）
⒉如果队列内的节点数>1，则:
⑴从队列前端移除两个最低权重的节点
⑵将（1）中移除的两个节点权重相加合成一个新节点
⑶加入第二个队列
⒊最后在第一个队列的节点为根节点
虽然使用此方法比使用优先队列的时间复杂度还低，但是注意此法的第1项，节点必须依照权重大小加入队列中，如果节点加入顺序不按大小，则需要经过排序，则至少花了O（n log n）的时间复杂度计算。
但是在不同的状况考量下，时间复杂度并非是最重要的，如果我们今天考虑英文字母的出现频率，变量n就是英文字母的26个字母，则使用哪一种算法时间复杂度都不会影响很大，因为n不是一笔庞大的数字。
1 #include <iostream> 2 #include <algorithm> 3 #include <unordered_map> 4 #include <vector> 5 #include <queue> 6 #include <fstream> 7 #include <sstream> 8 #include <string> 9 10 using namespace std; 11 12 class Huffman { 13 public: 14 Huffman() {} 15 ~Huffman() { 16 freeTree(root); 17 } 18 19 void init(string filename) { 20 ifstream in(filename.c_str()); 21 string line; 22 while(getline(in, line)) { 23 stringstream ss(line); 24 char symbol; 25 float p; 26 ss >> symbol >> p; 27 symbolInfo.push_back(new Node(symbol, p)); 28 } 29 root = buildTree2(); 30 generateCodes(root, ""); 31 } 32 33 void print() const { 34 for (auto it = codes.begin(); it != codes.end(); ++it) { 35 cout << it->first << ": " << it->second << endl; 36 } 37 } 38 39 string encode(string input) { 40 stringstream ans; 41 for (int i = 0; i < input.length(); ++i) { 42 ans << codes[input[i]]; 43 } 44 return ans.str(); 45 } 46 47 string decode(string input) { 48 if (root == NULL) return ""; 49 stringstream ans; 50 for (int i = 0; i < input.length(); ) { 51 Node* p = root; 52 for ( ; p != NULL; ++i) { 53 if (p->left == NULL && p->right == NULL) { 54 ans << p->symbol; 55 break; 56 } 57 if (input[i] == ‘0‘) { 58 p = p->left; 59 } else if (input[i] == ‘1‘) { 60 p = p->right; 61 } else { 62 return ""; 63 } 64 } 65 } 66 return ans.str(); 67 } 68 private: 69 struct Node { 70 char symbol; 71 float p; 72 Node* left; 73 Node* right; 74 Node(char s, float p, Node* l = NULL, Node* r = NULL):symbol(s), p(p), left(l), right(r) {} 75 }; 76 77 static bool nodeCompare(Node* n1, Node* n2) { 78 return n1->p > n2->p; 79 } 80 81 // O(nlgn) 82 Node* buildTree() { 83 if (symbolInfo.empty()) return NULL; 84 make_heap(symbolInfo.begin(), symbolInfo.end(), nodeCompare); 85 while (symbolInfo.size() > 1) { 86 // get the smallest 87 Node* n1 = symbolInfo.front(); 88 pop_heap(symbolInfo.begin(), symbolInfo.end(), nodeCompare); 89 symbolInfo.pop_back(); 90 // get the second smallest 91 Node* n2 = symbolInfo.front(); 92 pop_heap(symbolInfo.begin(), symbolInfo.end(), nodeCompare); 93 symbolInfo.pop_back(); 94 95 Node* n3 = new Node(‘@‘, n1->p + n2->p, n1, n2); 96 symbolInfo.push_back(n3); 97 push_heap(symbolInfo.begin(), symbolInfo.end(), nodeCompare); 98 } 99 return symbolInfo[0];100 }101 102 class Comparator {103 public:104 bool operator() (const Node* n1, const Node* n2) const {105 return n1->p > n2->p;106 }107 };108 109 Node* buildTree2() {110 if (symbolInfo.empty()) return NULL;111 priority_queue<Node*, vector<Node*>, Comparator> queue(symbolInfo.begin(), symbolInfo.end());112 while (queue.size() > 1) {113 Node* n1 = queue.top(); 114 queue.pop();115 Node* n2 = queue.top();116 queue.pop();117 Node* n3 = new Node(‘@‘, n1->p + n2->p, n1, n2);118 queue.push(n3); 119 }120 return queue.top();121 }122 123 void freeTree(Node* p) {124 if (p == NULL) return;125 freeTree(p->left);126 freeTree(p->right);127 delete p;128 p = NULL;129 }130 131 void generateCodes(Node* p, string str) {132 if (p == NULL) return;133 if (p->left == NULL && p->right == NULL) {134 codes[p->symbol] = str;135 }136 137 generateCodes(p->left, str + "0");138 generateCodes(p->right, str + "1");139 }140 141 vector<Node*> symbolInfo;142 unordered_map<char, string> codes;143 Node* root;144 };145 146 int main() {147 Huffman huffman;148 huffman.init("input.txt");149 huffman.print();150 151 string str = "abcdabcdab";152 string encode = huffman.encode(str);153 cout << str << endl << encode << endl;154 cout << huffman.decode(encode) << endl;155 return 0;156 }
这里用了stl的make_heap之类的函数，也尝试用priority_queue。但是两指重构的比较器的形式不同。注意priority_queue的比较器是作为模板参数传进去的，而且是定义成类。
可以用两个简单队列实现O(n)的算法，前提是一开始频率已经排好序。用vector是可以模拟queue，但是pop_front()的效率比较低。
Huffman