python实现哈夫曼编码

以下是Python实现哈夫曼编码的示例代码：

import heapq
from collections import defaultdict

# 定义节点类
class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    # 定义小于运算符，用于堆排序
    def __lt__(self, other):
        return self.freq < other.freq

# 构建哈夫曼树
def build_huffman_tree(freq_dict):
    heap = []
    for char, freq in freq_dict.items():
        heapq.heappush(heap, Node(char, freq))

    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged_node = Node(None, node1.freq + node2.freq)
        merged_node.left = node1
        merged_node.right = node2
        heapq.heappush(heap, merged_node)

    return heap[0]

# 递归遍历哈夫曼树，生成编码字典
def traverse_huffman_tree(node, current_code, encoding_dict):
    if node is None:
        return

    if node.char is not None:
        encoding_dict[node.char] = current_code
        return

    traverse_huffman_tree(node.left, current_code + "0", encoding_dict)
    traverse_huffman_tree(node.right, current_code + "1", encoding_dict)

# 对文本进行编码
def encode_text(text, encoding_dict):
    encoded_text = ""
    for char in text:
        encoded_text += encoding_dict[char]
    return encoded_text

# 对编码后的文本进行解码
def decode_text(encoded_text, decoding_dict):
    current_code = ""
    decoded_text = ""
    for bit in encoded_text:
        current_code += bit
        if current_code in decoding_dict:
            decoded_text += decoding_dict[current_code]
            current_code = ""
    return decoded_text

# 统计字符出现频率
def count_freq(text):
    freq_dict = defaultdict(int)
    for char in text:
        freq_dict[char] += 1
    return freq_dict

# 示例
text = "hello world"
freq_dict = count_freq(text)
huffman_tree = build_huffman_tree(freq_dict)
encoding_dict = {}
traverse_huffman_tree(huffman_tree, "", encoding_dict)
encoded_text = encode_text(text, encoding_dict)
decoding_dict = {v: k for k, v in encoding_dict.items()}
decoded_text = decode_text(encoded_text, decoding_dict)

print("编码字典：", encoding_dict)
print("编码后的文本：", encoded_text)
print("解码后的文本：", decoded_text)