哈夫曼树编码代码实现，Python与C++经典示例
Python实现哈夫曼树编码
哈夫曼树是一种用于数据压缩的树形结构。它的基本思想是根据数据出现的频率构建一棵树，出现频率高的数据对应的节点离根节点近，出现频率低的数据对应的节点离根节点远。
python
import heapq
from collections import namedtuple
定义节点
Node = namedtuple('Node', ['left', 'right', 'value'])
def huffman_encode(s):
创建一个优先队列
pq = [(len(v), v) for v in s]
heapq.heapify(pq)
while len(pq) > 1:
freq1, c1 = heapq.heappop(pq)
freq2, c2 = heapq.heappop(pq)
创建一个新的节点，它的左右子节点分别是c1和c2
它的频率是c1和c2的频率之和
它的编码是c1和c2的编码的前缀，再加上一个表示c1或c2的字符
node = Node(c1, c2, (c1[0], c2[0]))
heapq.heappush(pq, (freq1 + freq2, node))
取出最后剩下的节点
return pq[0][1].value
编码函数
def huffman_encode_string(s):
huffman_tree = huffman_encode(s)
def build_huffman_tree(node, prefix):
if isinstance(node, str):
return {node: prefix}
else:
return {build_huffman_tree(node.left, prefix + '0'): build_huffman_tree(node.right, prefix + '1')}
return build_huffman_tree(huffman_tree, '')
测试
s = 'this is a test'
encoded_dict = huffman_encode_string(s)
for c in s:
print(c, encoded_dict[c])
C++实现哈夫曼树编码
cpp
include
include
include
include
using namespace std;
struct Node {
char data;
int freq;
Node left, right;
Node(char data, int freq, Node left = nullptr, Node right = nullptr)
: data(data), freq(freq), left(left), right(right) {}
};
struct cmp {
bool operator()(Node l, Node r) {
return l->freq > r->freq;
}
};
void buildHuffmanTree(vector& nodes, int n) {
priority_queue, cmp> pq;
for (int i = 0; i < n; i++)
pq.push(nodes[i]);
while (pq.size() != 1) {
Node left = pq.top();
pq.pop();
Node right = pq.top();
pq.pop();
Node parent = new Node('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
nodes[0] = pq.top();
}
void printCodes(Node root, string str, map& codes) {
if (root->left == nullptr && root->right == nullptr) {
codes[root->data] = str;
return;
}
printCodes(root->left, str + "0", codes);
printCodes(root->right, str + "1", codes);
}
int main() {
string s = "this is a test";
vector nodes;
for (char c : s)
nodes.push_back(new Node(c, 0));
for (int i = 0; i < s.length(); i++)
nodes[i]->freq = 1;
buildHuffmanTree(nodes, s.length());
map codes;
printCodes(nodes[0], "", codes);
for (auto c : s)
cout << c << ": " << codes[c] << endl;
return 0;
}
这两个示例都实现了哈夫曼树编码。Python示例使用了heapq库来维护优先队列，C++示例使用了C++ STL中的priority_queue。这两个示例都使用了递归来构建哈夫曼树和生成编码。
