贪心算法哈弗曼编码证明

### 贪心算法中的哈夫曼编码证明解释

#### 哈夫曼编码简介
哈夫曼编码是一种用于数据压缩的有效前缀码，广泛应用于文件压缩工具中。该方法通过构建最优二叉树来实现最小化加权路径长度的目标[^1]。

#### 构建过程
为了创建哈夫曼树，首先统计字符频率并将其作为节点权重；接着不断选取两个具有最低频次的未加入任何子树结构内的结点组成新的父级节点直到只剩下一个根节点为止。最终形成的这棵特殊的二叉树即为哈夫曼树，在此过程中始终遵循着贪心策略的选择原则——每次操作都力求局部最优解从而达到全局最优化效果。

#### 正确性证明要点
要证明哈夫曼编码方案能够得到最佳解决方案，可以采用反证法来进行说明：

假设存在一种更优的方法X能生成比Huffman Tree更好的编码方式，则意味着对于某些特定输入序列S而言，利用这种方法所获得的结果R(X,S)会优于由后者产生的相应输出R(H,S)，然而事实上这是不可能发生的因为当按照上述流程建立起来之后已经确保了每一个阶段都是基于当前条件下所能做出的最佳决策之上继续推进下去因此不存在其他途径可以在相同前提下做得更好。

import heapq
from collections import defaultdict, Counter


def build_huffman_tree(frequencies):
    heap = [[weight, [symbol, ""]] for symbol, weight in 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 of a huffman tree"
frequency = dict(Counter(data))
huff_code = build_huffman_tree(frequency)


for char, code in huff_code:
    print(f"{char}\t{code}")