贪心法求解哈夫曼编码问题python

哈夫曼编码是一种用于编码信息的技术，它利用每个字符出现的频率来构建一棵二叉树，并将编码存储在树中。该编码方案将出现频率较高的字符映射到较短的编码中，而较低频率的字符则映射到较长的编码中。

以下是使用贪心算法求解哈夫曼编码问题的Python实现：

class Node:
    def __init__(self, freq, symbol, left=None, right=None):
        self.freq = freq
        self.symbol = symbol
        self.left = left
        self.right = right
        self.huff = ''

def printNodes(node, val=''):
    newVal = val + str(node.huff)
    if(node.left):
        printNodes(node.left, newVal)
    if(node.right):
        printNodes(node.right, newVal)
    if(not node.left and not node.right):
        print(f"{node.symbol} -> {newVal}")

def huffmanCode(freq):
    nodes = []
    for key in freq:
        nodes.append(Node(freq[key], key))
    while len(nodes) > 1:
        nodes = sorted(nodes, key=lambda x: x.freq)
        left = nodes[0]
        right = nodes[1]
        left.huff = 0
        right.huff = 1
        newNode = Node(left.freq+right.freq, left.symbol+right.symbol, left, right)
        nodes.remove(left)
        nodes.remove(right)
        nodes.append(newNode)
    printNodes(nodes[0])

# 测试
freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
huffmanCode(freq)

在上面的代码中，我们首先定义了一个节点类`Node`，它包含了每个字符的出现频率、字符本身、左右子节点和哈夫曼编码。然后我们定义了一个打印节点的函数`printNodes`，它将递归遍历树并打印每个叶子节点的字符和哈夫曼编码。接下来我们定义了一个`huffmanCode`函数，它接受一个包含每个字符出现频率的字典作为输入，并使用贪心算法构建哈夫曼树。最后，我们调用`huffmanCode`函数并将测试数据传递给它以生成哈夫曼编码。

上述程序的输出将如下所示：

a -> 1100
c -> 100
b -> 1110
e -> 101
d -> 1111
f -> 0

这些是每个字符的哈夫曼编码。可以看到，频率最高的字符`f`被映射到了最短的编码中，而较低频率的字符则被映射到了较长的编码中。