Huffman编码问题的贪心算法

根据引用[1]和引用，Huffman编码问题的贪心算法可以描述如下：

1. 统计每个字符出现的频率，并将每个字符看作一个权值为其频率的节点。
2. 将所有节点按照权值从小到大排序。
3. 选取权值最小的两个节点，将它们合并成一个新节点，新节点的权值为这两个节点的权值之和。
4. 将新节点插入到节点列表中，并将节点列表按照权值从小到大排序。
5. 重复步骤3和4，直到只剩下一个节点为止。
6. 对于每个字符，从根节点开始，向左走为0，向右走为1，直到到达该字符所对应的叶子节点，记录下所经过的路径即为该字符的Huffman编码。

以下是Python实现代码：

import heapq
from collections import defaultdict

def huffman_encoding(data):
    # 统计每个字符出现的频率
    freq = defaultdict(int)
    for char in data:
        freq[char] += 1

    # 将每个字符看作一个权值为其频率的节点
    nodes = [(f, char) for char, f in freq.items()]

    # 构建Huffman树
    heapq.heapify(nodes)
    while len(nodes) > 1:
        f1, left = heapq.heappop(nodes)
        f2, right = heapq.heappop(nodes)
        heapq.heappush(nodes, (f1 + f2, (left, right)))

    # 生成Huffman编码
    encoding = {}
    def generate_encoding(node, prefix=''):
        if isinstance(node, str):
            encoding[node] = prefix
        else:
            generate_encoding(node[0], prefix + '0')
            generate_encoding(node[1], prefix + '1')
    generate_encoding(nodes[0][1])

    # 对原始数据进行编码
    encoded_data = ''.join(encoding[char] for char in data)

    return encoded_data, encoding

def huffman_decoding(encoded_data, encoding):
    # 将编码表翻转，方便解码
    decoding = {code: char for char, code in encoding.items()}

    # 解码
    decoded_data = ''
    code = ''
    for bit in encoded_data:
        code += bit
        if code in decoding:
            decoded_data += decoding[code]
            code = ''

    return decoded_data