项目说明
本次实验项目是一个简单的Huffman编码工具，作了两种不同的实现。
由于在前面的课程中实现了Huffman树的C++类，所以这个项目实现起来相当容易，对应hufftree.cpp中的代码，但是该方法并没有用到书上的Huffman Table，而是直接利用指针的形式构建出了一颗树，因此没有去完成项目要求的输出Table的终态。
因此，为完成上述的要求，又撰写了一份与书上代码更接近的版本放在hufftable.cpp中，实现了Table的输出。
Huffman Tree
对于链式的Huffman树，我们可以有以下的节点定义：
1
2
3
4
5
6
7
8
| struct Node {
char symbol;
int frequency;
Node* left;
Node* right;
Node(char sym, int freq) : symbol(sym), frequency(freq), left(nullptr), right(nullptr) {}
};
|
Huffman树的定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class HuffmanTree {
private:
Node* root;
unordered_map<char, string> codes;
void buildCodes(Node* node, string code="") {}
public:
HuffmanTree(const vector<pair<char, int>>& frequencies) {}
string encode(const string& text) {}
string decode(const string& encoded) {}
void showCodes() {}
private:
struct CompareFrequency {};
};
|
接下来，主要是重点分析一些比较重要的功能实现：
树的构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| HuffmanTree(const vector<pair<char, int>>& frequencies) {
priority_queue<Node*, vector<Node*>, CompareFrequency> pq;
for (const auto& pair : frequencies) {
pq.push(new Node(pair.first, pair.second));
}
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
Node* parent = new Node('\0', left->frequency + right->frequency);
parent->left = left;
parent->right = right;
pq.push(parent);
}
root = pq.top();
buildCodes(root);
}
|
在树的构造中，由于涉及到获取最小的节点，我在这里使用了优先队列可以方便的完成排序的操作，进而可以很容易的完成树的构建，不过使用优先队列需要自己定义一个CompareFrequency类，用于比较两个节点的大小。
编码
可以看到在树的构造函数中，最后一步是调用buildCodes()函数，在codes中存储的是所涉及到各个字符的编码，这样就不必在树中回溯来完成编码。
1
2
3
4
5
6
7
8
9
10
11
| void buildCodes(Node* node, string code="") {
if (!node) return;
if (node->symbol != '\0') {
codes[node->symbol] = code;
} else {
buildCodes(node->left, code + "0");
buildCodes(node->right, code + "1");
}
}
|
直接利用递归就可以完成编码表的构建啦～
那么编码的实现非常简单，只需要遍历输入的文本，然后根据编码表找到对应的编码，然后拼接起来即可。
1
2
3
4
5
6
7
| string encode(const string& text) {
string encoded;
for (char c : text) {
encoded += codes[c];
}
return encoded;
}
|
解码
解码的实现非常简单，只需要遍历输入的编码，然后根据树的结构找到对应的字符即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| string decode(const string& encoded) {
string decoded;
Node* curr = root;
for (char bit : encoded) {
if (bit == '0') {
curr = curr->left;
} else {
curr = curr->right;
}
if (curr->symbol != '\0') {
decoded += curr->symbol;
curr = root;
}
}
return decoded;
}
|
主函数
在主函数之前，我们还要编写一个buildFrequencies()函数，用于读取输入的文本，然后统计各个字符出现的频率。
这个函数的算法思路就是构建一个unordered_map，然后遍历输入的文本，如果字符已经出现过，则将其频率加一，否则将其加入到map中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<pair<char, int>> buildFrequencies(const string& str) {
vector<pair<char, int>> freq;
unordered_map<char, int> count;
for (char c : str) {
count[c]++;
}
for (const auto& pair : count) {
freq.push_back(pair);
}
return freq;
}
|
那么接下来我们的主函数就很容易实现了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int main() {
string input;
while(true) {
cout << "Enter a string (0 to exit): ";
getline(cin, input);
if (input == "0") break;
vector<pair<char, int>> frequencies = buildFrequencies(input);
HuffmanTree huffman(frequencies);
cout << "Code Map: " << endl;
huffman.showCodes();
string encoded = huffman.encode(input);
cout << "Encoded text: " << encoded << endl;
string decoded = huffman.decode(encoded);
cout << "Decoded text: " << decoded << endl;
}
return 0;
}
|
Huffman Table
Huffman Table的节点和表的定义要稍作修改，但是大体上的接口都可以保持一致，以方便开发。
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
| struct Node {
char symbol;
int frequency;
int parent;
int left;
int right;
Node(char sym, int freq) :
symbol(sym),
frequency(freq),
parent(-1),
left(-1),
right(-1)
{}
};
class HuffmanTable {
private:
vector<Node> nodes;
unordered_map<char, string> codes;
pair<int, int> getMinTwo() {}
void buildCodes(Node node, string code="") {}
public:
HuffmanTable(const vector<pair<char, int>>& frequencies) {}
string encode(const string& text) {}
string decode(const string& encoded) {}
void showTable() {}
void showCodes() {}
};
|
树的构造
树的构造和之前一样，不过这里需要使用一个辅助函数getMinTwo()来获取最小的两个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| pair<int, int> getMinTwo() {
int min1 = INT_MAX, min2 = INT_MAX;
int min1_index = -1, min2_index = -1;
for (int i = 0; i < nodes.size(); i++) {
if (nodes[i].frequency < min1 && nodes[i].parent == -1) {
min2 = min1;
min2_index = min1_index;
min1 = nodes[i].frequency;
min1_index = i;
} else if (nodes[i].frequency < min2 && nodes[i].parent == -1) {
min2 = nodes[i].frequency;
min2_index = i;
}
}
return make_pair(min1_index, min2_index);
}
|
构造函数如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| HuffmanTable(const vector<pair<char, int>>& frequencies) {
int n = frequencies.size();
for (int i = 0; i < n; i++) {
nodes.push_back(Node(frequencies[i].first, frequencies[i].second));
}
for(int i=0; i<n-1; i++) {
pair<int, int> minTwo = getMinTwo();
Node parent = Node(
'\0',
nodes[minTwo.first].frequency + nodes[minTwo.second].frequency
);
parent.left = minTwo.first;
parent.right = minTwo.second;
nodes.push_back(parent);
nodes[minTwo.first].parent = nodes.size()-1;
nodes[minTwo.second].parent = nodes.size()-1;
}
buildCodes(nodes[nodes.size()-1]);
}
|
核心的改变就是parent left right全都变成了int类型，需要一些改动。所有原先的node->left node->right node->parent都变成了nodes[nodes[i].right] nodes[node[i].parent]。根节点则是nodes[nodes.size()-1]（最后一个节点）。
所以除开这些改动，Huffman Table的实现和之前一样。所以对于编码解码等操作只要按照上述修改即可。
