huffman编码

使用优先队列进行优化的haffman编码。

1. 统计文章中的词频
2. 使用优先队列(堆)创建haffman树
3. 遍历Haffman树得到每一个字符的huffman编码， 保存在enc(unordered_map)中
4. 文章进行编码
5. 使用huffman树和haffman编码进行解码。

创建huffman树的时间复杂度$O(ClogC)$其中C是单词种类的个数。
编码的时间复杂度$O(n)$，只需要遍历一遍字符串就行了。
解码的时间复杂度$O(m)$，只需要遍历一遍编码后的字符串就行了。

huffman编码是现代压缩技术的基础。应该写个输入输出测试一下对文件的压缩的情况的。
char是8个bit, 而bit数组中的一位是1个bit。所以肯定会有压缩的效果。
文件最后保存的是haffman树以及对应的huaffman编码。在解码的时候先读取haffmans树，然后对二进制文件进行解码。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

// Encodes a URL to a shortened URL.
struct HuffmanTree {
    HuffmanTree *l, *r;
    int cnt;
    char ch;                              // 词频和单词
    HuffmanTree(int cnt, char ch, HuffmanTree *l, HuffmanTree *r):cnt(cnt), ch(ch), l(l), r(r) {}
};
class cmp{
public:
    /* Node::priority 大的优先, 重写小于号 */
    bool operator () (HuffmanTree* &a, HuffmanTree* &b) const
    {
        return a->cnt > b->cnt;
    }
};

typedef pair<int, char>PR;
priority_queue<HuffmanTree*, vector<HuffmanTree*>, cmp>que, bakcup;
unordered_map<char, int>mp;

HuffmanTree* buildHuffman() {
    bakcup = que;
    while (!bakcup.empty()) {
        printf("%d %c\n", bakcup.top()->cnt, bakcup.top()->ch);
        bakcup.pop();
    }

    while (que.size() >= 2) {
        HuffmanTree* t1 = que.top(); que.pop();
        HuffmanTree* t2 = que.top(); que.pop();
        HuffmanTree *fa = new HuffmanTree(t1->cnt + t2->cnt, '#', t1, t2);
        que.push(fa);
    }
    return que.top();
}
HuffmanTree *root;
unordered_map<char, string>enc;
void travel(HuffmanTree *root, string s) {              // 获取每个结点的huffman编码
    if (root == NULL) return ;
    // 叶子结点, 统计编码
    if (root->l == NULL && root->r == NULL) {
        cout << root->ch << " " << s << endl;
        enc[root->ch] = s;
        return ;
    }
    travel(root->l, s + '0');
    travel(root->r, s + '1');
}
string encode(string longUrl) {
    for (char ch : longUrl) {
        mp[ch]++;
    }
    for (auto [ch, cnt] : mp) {
        que.push(new HuffmanTree(cnt, ch, NULL, NULL)); // 存放的是指针。
    }

    root = buildHuffman();
    travel(root, "");                                   // 遍历haffman树获取Huffman编码
    string ans;
    for (char ch : longUrl) {
        ans += enc[ch];
    }
    return ans;
}


string treeDecode(HuffmanTree *root, int &cur, string &s) {
    if (root == NULL) return "";
    if (root->l == NULL && root->r == NULL) {
        string ans = "";
        ans += root->ch;
        return ans;
    }
    cur++;
    if (s[cur] == '0') return treeDecode(root->l, cur, s);
    else return treeDecode(root->r, cur, s);
}
// Decodes a shortened URL to its original URL.
string decode(string shortUrl) {
    int cur = -1;
    string ans;
    int n = shortUrl.size();
    for (cur; cur < n - 1;) {
        printf("cur = %d\n", cur);
        string s = treeDecode(root, cur, shortUrl);
        cout << s << endl;
        ans += s;
    }
    return ans;
}

int main() {

    string s = "aaabbc";
    s = encode(s);
    cout << s << endl;
    cout << decode(s) << endl;
}

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109