贪心算法实现哈夫曼编码问题

哈夫曼编码是一种压缩算法，可以将一串数据压缩为更短的编码序列，从而节省存储空间。贪心算法可以用来实现哈夫曼编码，具体步骤如下：

1. 统计每个字符出现的频率，并将每个字符看作一个节点。

2. 将这些节点放入一个优先队列中，按照节点的频率从小到大排序。

3. 从队列中取出频率最小的两个节点，将它们合并成一个新节点，新节点的频率等于这两个节点的频率之和。将新节点插入队列中。

4. 重复步骤3，直到队列中只剩一个节点，这个节点就是哈夫曼树的根节点。

5. 对哈夫曼树进行遍历，将每个字符的编码记录下来。遍历时，从根节点出发，如果走左子树就记录一个0，如果走右子树就记录一个1。当到达叶子节点时，记录下这个字符的编码。

代码实现如下：

import heapq

# 定义哈夫曼树节点类
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 count_freq(text):
    freq = {}
    for char in text:
        if char in freq:
            freq[char] += 1
        else:
            freq[char] = 1
    return freq

# 构建哈夫曼树
def build_huffman_tree(freq):
    heap = [Node(freq[char], char) for char in freq]
    heapq.heapify(heap)
    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged = Node(node1.freq + node2.freq)
        merged.left = node1
        merged.right = node2
        heapq.heappush(heap, merged)
    return heap[0]

# 遍历哈夫曼树并记录编码
def traverse_tree(node, code, codes):
    if node.char:
        codes[node.char] = code
    else:
        traverse_tree(node.left, code + '0', codes)
        traverse_tree(node.right, code + '1', codes)

# 哈夫曼编码
def huffman_encoding(text):
    freq = count_freq(text)
    root = build_huffman_tree(freq)
    codes = {}
    traverse_tree(root, '', codes)
    encoded_text = ''.join(codes[char] for char in text)
    return encoded_text, codes

# 哈夫曼解码
def huffman_decoding(encoded_text, codes):
    inv_codes = {code: char for char, code in codes.items()}
    decoded_text = ''
    code = ''
    for bit in encoded_text:
        code += bit
        if code in inv_codes:
            decoded_text += inv_codes[code]
            code = ''
    return decoded_text

# 测试
text = 'hello world'
encoded_text, codes = huffman_encoding(text)
print('Encoded text:', encoded_text)
print('Huffman codes:', codes)
decoded_text = huffman_decoding(encoded_text, codes)
print('Decoded text:', decoded_text)

在以上代码中，我们首先定义了一个 `Node` 类来表示哈夫曼树的节点。然后，我们实现了 `count_freq` 函数来统计字符频率，`build_huffman_tree` 函数来构建哈夫曼树，`traverse_tree` 函数来遍历哈夫曼树并记录编码，以及 `huffman_encoding` 和 `huffman_decoding` 函数来实现哈夫曼编码和解码的功能。最后，我们对代码进行了测试，输出了编码后的文本、哈夫曼编码表和解码后的文本。