数信息论

k叉哈夫曼树

字数统计: 3.3k字   |   阅读时长: 16分
, , , ,

摘要: K叉哈夫曼树的链式实现，字符串编码解码的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 哈夫曼树与哈夫曼编码 中学习了二叉哈夫曼树与哈夫曼编码的原理，并给出基于数组实现的代码模板，并解决了力扣 271。

本文我们学习 K 叉哈夫曼树的原理，并给出链式实现的代码模板，最后同样解决力扣 271。

$1 k叉哈夫曼树

建树算法，同时也是贪心算法的构造性证明

  • step1: 权值集合 ${w_{0}, w_{1}, …, w_{n-1}}$
  • step2: 森林 $F = {T_{0}, T_{1}, …, T_{n-1}}$
  • step3: 新建节点 node，在 F 中选权值最小的 k 颗, 作为 node 的子树, 合为一棵树, node 的权为 k 个子节点的权之和，设置相关节点的关系字段 parent, children。
  • step4: 选中的两颗从 F 中删掉, 将合并后的新树加入 F 中.
  • step5: 重复 step3,step4 直到 F 中只有一棵树

最终构造出的树，非叶子节点都有 k 个子节点，因此初始数据长度为 n，则建树后的节点个数为 $\frac{n - 1}{k - 1}k + 1$，其中 n 个为叶子节点即原始数据，$\frac{n - 1}{k - 1}$ 个为新建的节点。

将 k=2 代入，就是 2 叉哈夫曼树结论。

节点定义

在 贪心-哈夫曼编码 中是用数组维护的节点信息，这里用指针维护，也就是链式存储的实现方式。

根据建树算法所需信息，节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using HFType = char;
const HFType PLACEHOLDER = '#';

struct HFNode
{
    HFType data;
    int weight;
    HFNode *parent;
    vector<HFNode*> children;
    HFNode(){}
    HFNode(int k, const HFType& v, int w)
    {
        children = vector<HFNode*>(k);
        data = v;
        weight = w;
    }
};

建树算法实现

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
struct HeapCmp
{
    bool operator()(const HFNode*& node1, const HFNode*& node2) const
    {
        return node1 -> weight > node2 -> weight;
    }
};

void HuffmanTree::build(const vector<HFType>& v, const vector<int>& w, int K)
{
    this -> n = v.size();
    this -> k = K;
    // n 个叶子节点
    priority_queue<HFNode*, vector<HFNode*>, HeapCmp> pq; // 小顶堆
    for(int i = 0; i < n; ++i)
    {
        HFNode *node = new HFNode(k, v[i], w[i]);
        pq.push(node);
    }
    // 如果有必要，加 m 个虚节点
    if((n - 1) % (k - 1) != 0)
    {
        int m = k - ((n - 1) % (k - 1)) - 1;
        for(int i = 0; i < m; ++i)
        {
            HFNode *node = new HFNode(k, PLACEHOLDER, 0);
            pq.push(node);
        }
    }

    while((int)pq.size() > 1)
    {
        HFNode *fa = new HFNode(k, PLACEHOLDER, 0);
        for(int j = 0; j < k; ++j)
        {
            HFNode *node = pq.top();
            pq.pop();
            fa -> weight += node -> weight;
            (fa -> children)[j] = node;
            node -> parent = fa;
        }
        pq.push(fa);
    }
    root = pq.top();
}

获取字符集的哈夫曼编码

1
枚举出所有的叶子节点。对每个节点打印出到根节点的路径即可

这里延续链式存储的实现方法，数组实现参考 贪心-哈夫曼编码。

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
vector<HFCode> get_code()
{
    vector<HFCode> result;
    string code;
    dfs(root, result, code);
    return result;
}

void dfs(HFNode *node, vector<HFCode>& hfcodes, string& code)
{
    if(!(node -> children)[0])
    {
        hfcodes.push_back(HFCode());
        hfcodes.back().data = node -> data;
        hfcodes.back().code = code;
        return;
    }
    for(int i = 0; i < k; ++i)
    {
        HFNode *child = (node -> children)[i];
        if(child)
        {
            code += '0' + i;
            dfs(child, hfcodes, code);
            code.pop_back();
        }
    }
}

$2 哈夫曼编码和解码

在哈夫曼树中增加编码和解码的接口：

1
2
string HuffmanTre::encode(const vector<HFType>& data)
vector<HFType> HuffmanTree::decode(const string& seq)

编码

利用字符集和对应的频率建树之后，可以随时获取字符集的编码。有了字符集的编码，就可以对原数据进行编码了。编码的过程类似于查字典：

注：以下代码的查字典的过程可以用哈希表优化：

1
2
3
4
5
6
7
8
9
10
11
12
string encode(const vector<HFType>& data)
{
    vector<HFCode> hfcode = get_code();
    string result;
    for(const HFType &item: data)
    {
        for(const HFCode &code_info: hfcode)
            if(code_info.data == item)
                result += code_info.code;
    }
    return result;
}

解码

基于以上的哈夫曼树实现的编码，产生的是前缀码，即没有任何码是其它码的前缀，这需要证明，但是略繁琐。

前缀码可以达到最优的压缩率，这也需要证明。

以上需要证明的内容参考信息论相关理论的资料，这里不展开。

前缀码的特性可以简化解码过程，如果产生的不是前缀码，在解码的时候可能还要用搜索引擎中常用的基于字典的中文分词的那一套：正向最大匹配算法、逆向最大匹配算法。

因为是前缀码，没有码是其它码的前缀，所以开头的码是没有歧义的，从编码序列开头开始，就可以无歧义地识别出第一个字符，对编码序列的剩余部分，依然可以重复这个过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<HFType> decode(const string& seq)
{
    vector<HFType> result;
    int n_seq = seq.size();
    int iter = 0;
    while(iter < n_seq)
    {
        HFNode *node = root;
        HFType data = _decode(node, seq, iter);
        result.push_back(data);
    }
    return result;
}

HFType _decode(HFNode* node, const string& seq, int& iter)
{
    while((node -> children)[0])
    {
        node = (node -> children)[seq[iter] - '0'];
        ++iter;
    }
    return node -> data;
}

$3 测试及完整代码

测试结果

代码 (C++，模板)

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include <string>
#include <vector>
#include <climits>
#include <unordered_map>
#include <iostream>
#include <queue>
#include <functional>

using namespace std;

using HFType = char;
const HFType PLACEHOLDER = '#';

struct HFNode
{
    HFType data;
    int weight;
    HFNode *parent;
    vector<HFNode*> children;
    HFNode(){}
    HFNode(int k, const HFType& v, int w)
    {
        children = vector<HFNode*>(k);
        data = v;
        weight = w;
    }
};

struct HFCode
{
    HFType data;
    string code;
};

struct HeapCmp
{
    bool operator()(HFNode*& node1, HFNode*& node2) const
    {
        return node1 -> weight > node2 -> weight;
    }
};

class HuffmanTree
{
private:
    void delete_sub_tree(HFNode* node)
    {
        if(!node) return;
        for(HFNode *child: node -> children)
            if(child)
                delete_sub_tree(child);
        delete node;
        node = nullptr;
    }

public:
    HuffmanTree(){}
    ~HuffmanTree()
    {
        delete_sub_tree(root);
    }

    void build(const vector<HFType>& v, const vector<int>& w, int K)
    {
        this -> n = v.size();
        this -> k = K;
        // n 个叶子节点
        priority_queue<HFNode*, vector<HFNode*>, HeapCmp> pq; // 小顶堆
        for(int i = 0; i < n; ++i)
        {
            HFNode *node = new HFNode(k, v[i], w[i]);
            pq.push(node);
        }
        // 如果有必要，加 m 个虚节点
        if((n - 1) % (k - 1) != 0)
        {
            int m = k - ((n - 1) % (k - 1)) - 1;
            for(int i = 0; i < m; ++i)
            {
                HFNode *node = new HFNode(k, PLACEHOLDER, 0);
                pq.push(node);
            }
        }

        while((int)pq.size() > 1)
        {
            HFNode *fa = new HFNode(k, PLACEHOLDER, 0);
            for(int j = 0; j < k; ++j)
            {
                HFNode *node = pq.top();
                pq.pop();
                fa -> weight += node -> weight;
                (fa -> children)[j] = node;
                node -> parent = fa;
            }
            pq.push(fa);
        }
        root = pq.top();
    }

private:
    void dfs(HFNode *node, vector<HFCode>& hfcodes, string& code)
    {
        if(!(node -> children)[0])
        {
            hfcodes.push_back(HFCode());
            hfcodes.back().data = node -> data;
            hfcodes.back().code = code;
            return;
        }
        for(int i = 0; i < k; ++i)
        {
            HFNode *child = (node -> children)[i];
            if(child)
            {
                code += '0' + i;
                dfs(child, hfcodes, code);
                code.pop_back();
            }
        }
    }

public:
    vector<HFCode> get_code()
    {
        vector<HFCode> result;
        string code;
        dfs(root, result, code);
        return result;
    }

    string encode(const vector<HFType>& data)
    {
        vector<HFCode> hfcode = get_code();
        string result;
        for(const HFType &item: data)
        {
            for(const HFCode &code_info: hfcode)
                if(code_info.data == item)
                    result += code_info.code;
        }
        return result;
    }

private:
    HFType _decode(HFNode* node, const string& seq, int& iter)
    {
        while((node -> children)[0])
        {
            node = (node -> children)[seq[iter] - '0'];
            ++iter;
        }
        return node -> data;
    }

public:
    vector<HFType> decode(const string& seq)
    {
        vector<HFType> result;
        int n_seq = seq.size();
        int iter = 0;
        while(iter < n_seq)
        {
            HFNode *node = root;
            HFType data = _decode(node, seq, iter);
            result.push_back(data);
        }
        return result;
    }

private:
    HFNode *root;
    int k; // 字符集大小
    int n; // 叶节点个数
};


int main()
{
    string data;
    cout << "数据： " << endl;
    cin >> data;
    int n = data.size();
    cout << "数据长度： " << n << endl;
    cout << "字符集长度： ";
    int k;
    cin >> k;
    // 统计字符和频率
    unordered_map<int, int> mapping;
    for(const char& ch: data)
        ++mapping[ch];
    vector<char> v;
    vector<int> w;
    for(const auto &item: mapping)
    {
        v.push_back(item.first);
        w.push_back(item.second);
    }
    int m = v.size();
    cout << "字符数： " << m << endl;
    cout << "(字符，频率)： " << endl;
    for(int i = 0; i < m; ++i)
        cout << v[i] << " " << w[i] << endl;
    HuffmanTree hftree;
    hftree.build(v, w, k);

    cout << "build done" << endl;

    vector<HFCode> result = hftree.get_code();
    cout << endl;
    cout << "编码结果： " << endl;
    for(int i = 0; i < (int)result.size(); ++i)
    {
        HFCode cur = result[i];
        cout << cur.data << " : " << cur.code << endl;
    }

    cout << "原数据的编码序列: " << endl;
    string seq = hftree.encode(vector<HFType>(data.begin(), data.end()));
    cout << seq << endl;
    cout << "解码结果: " << endl;
    vector<HFType> d_seq = hftree.decode(seq);
    cout << string(d_seq.begin(), d_seq.end()) << endl;
}

$4 271. 字符串的编码与解码

请你设计一个算法，可以将一个 字符串列表 编码成为一个 字符串。这个编码后的字符串是可以通过网络进行高效传送的，并且可以在接收端被解码回原来的字符串列表。

1 号机（发送方）有如下函数：

1
2
3
4
string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

2 号机（接收方）有如下函数：

1
2
3
4
vector<string> decode(string s) {
  //... your code
  return strs;
}

1 号机（发送方）执行：

1
string encoded_string = encode(strs);

2 号机（接收方）执行：

1
vector<string> strs2 = decode(encoded_string);

此时，2 号机（接收方）的 strs2 需要和 1 号机（发送方）的 strs 相同。

请你来实现这个 encode 和 decode 方法。

注意：

1
2
3
因为字符串可能会包含 256 个合法 ascii 字符中的任何字符，所以您的算法必须要能够处理任何可能会出现的字符。
请勿使用 “类成员”、“全局变量” 或 “静态变量” 来存储这些状态，您的编码和解码算法应该是非状态依赖的。
请不要依赖任何方法库，例如 eval 又或者是 serialize 之类的方法。本题的宗旨是需要您自己实现 “编码” 和 “解码” 算法。

算法：哈夫曼编码

将前面实现的哈夫曼树套用过来，并将编码过程的查字典这一步用哈希表优化。

边界处理：

1
2
3
[]
[""]
字符集只有一个字符

代码 (C++)

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
using KHFType = char;
const KHFType PLACEHOLDER = (char)256;

struct KHFNode
{
    KHFType data;
    int weight;
    KHFNode *parent;
    vector<KHFNode*> children;
    KHFNode(){}
    KHFNode(int k, const KHFType& v, int w)
    {
        children = vector<KHFNode*>(k);
        data = v;
        weight = w;
    }
};

struct KHFCode
{
    KHFType data;
    string code;
};

struct HeapCmp
{
    bool operator()(KHFNode*& node1, KHFNode*& node2) const
    {
        return node1 -> weight > node2 -> weight;
    }
};

class KHuffmanTree
{
private:
    void delete_sub_tree(KHFNode* node)
    {
        if(!node) return;
        for(KHFNode *child: node -> children)
            if(child)
                delete_sub_tree(child);
        delete node;
        node = nullptr;
    }

public:
    KHuffmanTree()
    {
        root = nullptr;
    }
    ~KHuffmanTree()
    {
        delete_sub_tree(root);
    }

    int charset_size()
    {
        return n;
    }

    void build(const string& v, const vector<int>& w, int K)
    {
        this -> n = v.size();
        this -> k = K;
        if(n == 0) return;
        // n 个叶子节点
        priority_queue<KHFNode*, vector<KHFNode*>, HeapCmp> pq; // 小顶堆
        for(int i = 0; i < n; ++i)
        {
            KHFNode *node = new KHFNode(k, v[i], w[i]);
            pq.push(node);
        }
        // 如果有必要，加 m 个虚节点
        if((n - 1) % (k - 1) != 0)
        {
            int m = k - ((n - 1) % (k - 1)) - 1;
            for(int i = 0; i < m; ++i)
            {
                KHFNode *node = new KHFNode(k, PLACEHOLDER, 0);
                pq.push(node);
            }
        }

        while((int)pq.size() > 1)
        {
            KHFNode *fa = new KHFNode(k, PLACEHOLDER, 0);
            for(int j = 0; j < k; ++j)
            {
                KHFNode *node = pq.top();
                pq.pop();
                fa -> weight += node -> weight;
                (fa -> children)[j] = node;
                node -> parent = fa;
            }
            pq.push(fa);
        }
        root = pq.top();
    }

private:
    void dfs(KHFNode *node, vector<KHFCode>& khfcodes, string& code)
    {
        if(!(node -> children)[0])
        {
            khfcodes.push_back(KHFCode());
            khfcodes.back().data = node -> data;
            khfcodes.back().code = code;
            return;
        }
        for(int i = 0; i < k; ++i)
        {
            KHFNode *child = (node -> children)[i];
            if(child)
            {
                code += '0' + i;
                dfs(child, khfcodes, code);
                code.pop_back();
            }
        }
    }

public:
    vector<KHFCode> get_code()
    {
        vector<KHFCode> result;
        string code;
        dfs(root, result, code);
        return result;
    }

    string encode(const string& data)
    {
        vector<KHFCode> khfcode = get_code();
        string result;
        for(const KHFType &item: data)
        {
            for(const KHFCode &code_info: khfcode)
                if(code_info.data == item)
                    result += code_info.code;
        }
        return result;
    }

private:
    KHFType _decode(KHFNode* node, const string& seq, int& iter)
    {
        while((node -> children)[0])
        {
            node = (node -> children)[seq[iter] - '0'];
            ++iter;
        }
        return node -> data;
    }

public:
    string decode(const string& seq)
    {
        string result;
        int n_seq = seq.size();
        int iter = 0;
        while(iter < n_seq)
        {
            KHFNode *node = root;
            KHFType data = _decode(node, seq, iter);
            result.push_back(data);
        }
        return result;
    }

private:
    KHFNode *root;
    int k; // 字符集大小
    int n; // 叶节点个数
};


class Codec {
public:
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        if(strs.empty()) return "";
        unordered_map<char, int> mapping = stat(strs);
        string v;
        vector<int> w;
        for(const auto &item: mapping)
        {
            v.push_back(item.first);
            w.push_back(item.second);
        }
        int K = 2;
        hftree.build(v, w, K);
        string seq;
        p = (char)256;
        if(hftree.charset_size() <= 1)
        {
            for(const string& str: strs)
            {
                seq += str + p;
            }
        }
        else
        {
            for(const string& str: strs)
            {
                seq += hftree.encode(str) + p;
            }
        }
        return seq;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        if(s.empty()) return {};
        vector<string> result;
        int n = s.size();
        int left = 0;
        while(left < n)
        {
            int right = left;
            while(right < n && s[right] != p)
                ++right;
            string seq = s.substr(left, right - left);
            string d_seq;
            if(hftree.charset_size() <= 1)
                d_seq = seq;
            else
                d_seq = hftree.decode(seq);
            result.push_back(d_seq);
            left = right + 1;
        }
        return result;
    }

private:
    KHuffmanTree hftree;
    char p;

    unordered_map<char, int> stat(const vector<string>& strs)
    {
        unordered_map<char, int> mapping;
        for(const string& str: strs)
        {
            for(const char& ch: str)
                ++mapping[ch];
        }
        return mapping;
    }
};
Share