哈夫曼编码和译码pta

### 哈夫曼编码和译码原理

哈夫曼编码是一种用于数据压缩的前缀编码方式。该算法通过构建一棵二叉树来表示字符及其频率，从而生成最短长度的加权路径[^1]。

#### 构建哈夫曼树的过程如下：

- 统计输入字符串中各个字符出现的概率；
- 创建一个节点列表，其中每个节点代表一个字符以及其对应的概率；
- 将这些节点按照从小到大顺序排列形成最小堆；
- 反复取出两个具有最低权重的节点创建一个新的父节点直到只剩下一个根节点为止；

最终得到的就是所谓的“哈夫曼树”，这棵树决定了如何给定字符分配唯一且最优比特串作为编码[^2]。

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))


text = "this is an example of a huffman tree"
frequency = Counter(text)


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

上述代码实现了基于Python语言版本的哈夫曼编码过程，可以用来计算任意一段文本中的各字符所对应的最佳编码方案[^3]。

---

对于解码部分，则是从左至右遍历已知序列并沿着哈夫曼树向下查找直至找到叶子结点即为当前位串所属符号，重复此操作直至整个消息被完全解析出来[^4]。

def decode_string(encoded_data, huffman_dict):
    rev_huff_dict = {v:k for k,v in huffman_dict}
    decoded_output = ""
    temp = ""

    for bit in encoded_data:
        temp += bit
        
        if temp in rev_huff_dict:
            character = rev_huff_dict[temp]
            decoded_output += character
            temp=""
                
    return decoded_output


encoded_message="1011100011100101000001010110000110101100000110011100101000001010110000110101100000110011100101000001010110000110101100000110011100101"

decoded_text=decode_string(encoded_message,{item[1]: item[0] for item in huff_code})
print(decoded_text)

这段程序展示了怎样利用之前建立好的映射表来进行有效的反向转换工作——即将经过哈夫曼编码后的二进制流还原成原始的信息内容[^5]。