Python 哈夫曼算法实现：编码与解码

以下是使用 Python 实现哈夫曼编码和解码算法的代码：

from heapq import heappush, heappop, heapify
from collections import defaultdict


def huffman_encoding(data):
    # Step 1: Calculate frequency of each character in the data
    freq = defaultdict(int)
    for char in data:
        freq[char] += 1

    # Step 2: Create a priority queue of nodes, by frequency
    pq = [[freq[char], char] for char in freq]
    heapify(pq)

    # Step 3: Build Huffman tree
    while len(pq) > 1:
        freq1, char1 = heappop(pq)
        freq2, char2 = heappop(pq)
        node = [freq1 + freq2, [char1, char2]]
        heappush(pq, node)

    # Step 4: Generate Huffman codes
    codes = {}
    def generate_codes(node, code=''):
        if isinstance(node, list):
            generate_codes(node[0], code + '0')
            generate_codes(node[1], code + '1')
        else:
            codes[node] = code

    root = heappop(pq)
    generate_codes(root[1])

    # Step 5: Encode the data using the Huffman codes
    encoded_data = ''.join([codes[char] for char in data])

    return encoded_data, codes


def huffman_decoding(encoded_data, codes):
    # Step 1: Invert the codes dictionary
    inverse_codes = {code: char for char, code in codes.items()}

    # Step 2: Decode the encoded data using the Huffman codes
    decoded_data = ''
    code = ''
    for bit in encoded_data:
        code += bit
        if code in inverse_codes:
            decoded_data += inverse_codes[code]
            code = ''

    return decoded_data

这个代码实现了哈夫曼编码和解码的功能。其中，huffman_encoding 函数用来对输入数据进行哈夫曼编码，返回编码后的数据和编码表；huffman_decoding 函数用来对编码后的数据进行解码，返回解码后的数据。

具体实现过程如下：

1. 首先，统计输入数据中每个字符的出现频率。
2. 根据字符频率构建一个优先队列，每个队列元素是一个列表，包含字符的频率和字符本身。
3. 从优先队列中取出频率最小的两个元素，合并成一个新的元素，频率为两个元素频率之和，字符为两个元素组成的列表。将新元素插入到优先队列中。
4. 重复步骤3，直到优先队列中只剩下一个元素，这就是哈夫曼树的根节点。
5. 通过遍历哈夫曼树，生成每个字符的哈夫曼编码。左子树为0，右子树为1。
6. 将输入数据中的每个字符替换为它对应的哈夫曼编码，得到编码后的数据。
7. 对编码后的数据进行解码。从左往右读取每个比特位，如果读到的比特位能够对应到一个字符，就将这个字符加入到解码后的数据中。

这个代码使用了 Python 的 heapq 和 collections 模块，分别用于构建优先队列和统计字符频率。在编码和解码过程中，都是通过遍历哈夫曼树来实现的，因此这个代码也可以看作是一个哈夫曼树的实现。