贪心算法最优前缀编码

### 贪婪算法实现最优前缀编码

#### 实现原理
最优前缀编码通常指的是霍夫曼编码，这是一种广泛应用于数据压缩的技术。通过构建一棵二叉树来表示字符及其频率，并利用贪婪策略最小化加权路径长度。

在霍夫曼编码中，每个叶节点代表一个字符以及其出现的概率或频次；内部节点则不对应任何实际意义的数据项而是用于连接子节点形成完整的树结构。对于给定的一组符号与其对应的概率分布{p(x)}, 霍夫曼编码的目标是在满足前缀性质的前提下使平均码字长度最短[^1]。

#### Python代码示例
下面是一个简单的Python程序用来展示如何基于贪婪方法创建霍夫曼编码：

import heapq
from collections import defaultdict, Counter


def huffman_encoding(symbols_with_frequencies):
    heap = [[weight, [symbol, ""]] for symbol, weight in symbols_with_frequencies.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]

        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))


data = "this is an example for huffman encoding"
frequency = Counter(data)


huff_code = huffman_encoding(frequency)
print("Symbol".ljust(10) + "Frequency".ljust(10)+ "Huffman Code")
for p in huff_code:
    print(f"{p[0].ljust(10)} {str(frequency[p[0]]).ljust(10)} {p[1]}")

此段代码首先统计输入字符串`data`中的各个字符出现次数作为权重建立初始堆队列，之后不断取出两个具有最低频率的元素组合成新的父节点直到只剩下一个根节点为止，在这个过程中动态调整各分支上的编码值最终得到整个字母表的最佳前缀编码方案。