使用Python实现哈夫曼编码

哈夫曼编码是一种无损压缩算法，通过使用变长编码来表示不同的字符，使得频繁出现的字符使用较短的编码，从而减小了数据的存储空间。以下是使用 Python 实现哈夫曼编码的代码示例：

import heapq
from collections import defaultdict


class Node:
    def __init__(self, freq, char=None):
        self.freq = freq
        self.char = char
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq


def build_huffman_tree(text):
    freq_dict = defaultdict(int)
    for char in text:
        freq_dict[char] += 1

    heap = []
    for char, freq in freq_dict.items():
        heapq.heappush(heap, Node(freq, char))

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = Node(left.freq + right.freq)
        parent.left = left
        parent.right = right
        heapq.heappush(heap, parent)

    return heap[0]


def build_huffman_table(node, code='', table={}):
    if node.char:
        table[node.char] = code
    else:
        build_huffman_table(node.left, code + '0', table)
        build_huffman_table(node.right, code + '1', table)

    return table


def encode(text):
    huffman_tree = build_huffman_tree(text)
    huffman_table = build_huffman_table(huffman_tree)
    encoded_text = ''
    for char in text:
        encoded_text += huffman_table[char]

    return encoded_text


def decode(encoded_text, huffman_tree):
    decoded_text = ''
    node = huffman_tree
    for bit in encoded_text:
        if bit == '0':
            node = node.left
        else:
            node = node.right

        if node.char:
            decoded_text += node.char
            node = huffman_tree

    return decoded_text


if __name__ == '__main__':
    text = 'hello world'
    encoded_text = encode(text)
    print('Encoded Text:', encoded_text)

    huffman_tree = build_huffman_tree(text)
    decoded_text = decode(encoded_text, huffman_tree)
    print('Decoded Text:', decoded_text)

该代码中的 `build_huffman_tree` 函数使用给定的文本构建哈夫曼树，并返回根节点。`build_huffman_table` 函数使用构建好的哈夫曼树生成编码表，编码表以字典的形式返回。`encode` 函数使用编码表将文本编码为哈夫曼编码，并返回编码后的字符串。`decode` 函数使用给定的哈夫曼树将编码的字符串解码为原始文本，并返回解码后的字符串。