c++实现哈夫曼树编码
时间: 2024-06-23 07:02:16 浏览: 9
Huffman树(也称为最优二叉树或哈夫曼编码)是一种用于数据压缩的自定义二叉树,它通过对字符的频率进行排序并构建一棵树,使得频率低的字符用较短的编码表示,频率高的字符用较长的编码。在C++中实现Huffman树编码,通常包括以下步骤:
1. **字符频率统计**:收集文本中的每个字符及其出现次数。
2. **构建优先队列**:使用优先队列(最小堆或斐波那契堆)存储字符和它们的频率,初始时所有字符都作为单独的节点。
3. **构建Huffman树**:
a. 从队列中取出频率最低的两棵树,合并为一个新的树,新树的左子树和右子树分别对应原来的两棵树。
b. 将新树放回队列,更新频率。
c. 重复步骤a和b,直到队列只剩下一个树,这个树就是Huffman树。
4. **编码规则**:遍历生成的Huffman树,对于每个节点,如果它的左子树为空,右子树为空,则对应的字符使用一个'0';反之,使用'1'。这样就能得到每个字符的编码。
5. **压缩编码**:将原始文本中每个字符替换为其对应的Huffman编码。
6. **解码**:在接收编码后的数据时,根据相同的规则读取编码,还原出原始字符。
相关问题
哈夫曼树编码与实现c++
哈夫曼树编码是一种常用的无损压缩算法。该算法的核心思想是将出现频率较高的字符用较短的编码表示,出现频率较低的字符用较长的编码表示,从而实现对文本的压缩。哈夫曼树编码的实现包括以下几个步骤:
1. 统计文本中每个字符的出现频率,并将其存储在一个数组或者哈希表中。
2. 创建一个最小堆,并将每个字符的出现频率作为节点的权值。
3. 从最小堆中选择两个权值最小的节点,将它们合并成一个新节点,新节点的权值为两个节点权值之和。将新节点插入到最小堆中。
4. 重复步骤3,直到最小堆中只剩下一个节点为止。该节点即为哈夫曼树的根节点。
5. 遍历哈夫曼树,将每个字符对应的编码存储在一个数组或者哈希表中。
6. 对原始文本进行编码,将编码后的二进制数据存储在文件中。
7. 对编码后的文件进行解码,根据哈夫曼树和编码表还原原始文本。
下面是一个使用C++实现哈夫曼树编码的示例代码:
```cpp
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct TreeNode {
char data; // 字符
int freq; // 出现频率
TreeNode *left, *right;
TreeNode(char c, int f) : data(c), freq(f), left(nullptr), right(nullptr) {}
~TreeNode() {
delete left;
delete right;
}
};
struct cmp {
bool operator()(const TreeNode* a, const TreeNode* b) const {
return a->freq > b->freq;
}
};
void buildHuffmanTree(unordered_map<char, int>& freqMap, TreeNode*& root) {
priority_queue<TreeNode*, vector<TreeNode*>, cmp> minHeap;
for (auto& p : freqMap) {
minHeap.push(new TreeNode(p.first, p.second));
}
while (minHeap.size() > 1) {
auto left = minHeap.top();
minHeap.pop();
auto right = minHeap.top();
minHeap.pop();
auto node = new TreeNode('$', left->freq + right->freq);
node->left = left;
node->right = right;
minHeap.push(node);
}
root = minHeap.top();
}
void buildCodeTable(TreeNode* root, unordered_map<char, string>& codeTable, string code) {
if (!root) return;
if (root->data != '$') {
codeTable[root->data] = code;
}
buildCodeTable(root->left, codeTable, code + "0");
buildCodeTable(root->right, codeTable, code + "1");
}
string encode(unordered_map<char, string>& codeTable, string text) {
string res;
for (char c : text) {
res += codeTable[c];
}
return res;
}
string decode(TreeNode* root, string encodedText) {
string res;
auto curr = root;
for (char c : encodedText) {
if (c == '0') curr = curr->left;
else curr = curr->right;
if (!curr->left && !curr->right) {
res += curr->data;
curr = root;
}
}
return res;
}
int main() {
string text = "hello world";
unordered_map<char, int> freqMap;
for (char c : text) {
freqMap[c]++;
}
TreeNode* root = nullptr;
buildHuffmanTree(freqMap, root);
unordered_map<char, string> codeTable;
buildCodeTable(root, codeTable, "");
string encodedText = encode(codeTable, text);
cout << "Encoded Text: " << encodedText << endl;
string decodedText = decode(root, encodedText);
cout << "Decoded Text: " << decodedText << endl;
delete root;
return 0;
}
```
使用c++实现哈夫曼树
哈夫曼树是一种基于字符频率来构建的最优二叉树,用于压缩和解压缩数据。在 C++ 中,可以通过以下步骤来实现哈夫曼树:
1. 定义结构体存储哈夫曼树节点信息,包括字符、权值、左右子节点等信息。
```
struct TreeNode {
char ch;
int freq;
TreeNode *left, *right;
};
```
2. 构建哈夫曼树的主要过程是先将字符按照频率从小到大排序,然后将最小的两个节点合并为一个新节点,其权值为两个节点权值之和。重复此过程直到只剩下一个节点,即为哈夫曼树的根节点。可以使用 STL 中的 priority_queue 来实现节点合并的过程。
```
struct cmp {
bool operator() (TreeNode* a, TreeNode* b) {
return a->freq > b->freq;
}
};
void buildHuffmanTree(vector<char>& chars, vector<int>& freqs) {
priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
for (int i = 0; i < chars.size(); ++i) {
TreeNode* node = new TreeNode(chars[i], freqs[i]);
pq.push(node);
}
while (pq.size() > 1) {
TreeNode* left = pq.top(); pq.pop();
TreeNode* right = pq.top(); pq.pop();
TreeNode* parent = new TreeNode('#', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
}
```
3. 对于给定的字符串,可以通过哈夫曼树得到每个字符的编码,即左子节点对应编码为 0,右子节点对应编码为 1。可以使用递归的方式遍历哈夫曼树,生成编码表。
```
unordered_map<char, string> generateCodeMap(TreeNode* root) {
unordered_map<char, string> codeMap;
function<void(TreeNode*, string)> dfs = [&](TreeNode* node, string code) {
if (!node) return;
if (node->ch != '#') codeMap[node->ch] = code;
dfs(node->left, code + "0");
dfs(node->right, code + "1");
};
dfs(root, "");
return codeMap;
}
```
以上就是使用 C++ 实现哈夫曼树的基本步骤。