浙大数据结构第五周之05-树9 Huffman Codes

**浙大数据结构第五周之05-树9 Huffman Codes**

在前面的几周中，我们已经学习了基本的树结构，如二叉树、AVL树等。然而，在实际应用中，二叉树可能并不总是最优选择。在某些情况下，我们需要一种更高效的编码方式来压缩数据。这就是Huffman Codes的作用。

**什么是Huffman Codes**

Huffman Codes是一种变长编码方式，它通过构造一棵 Huffman 树来实现。这种树结构能够根据输入数据的分布特征自适应地调整编码长度，从而达到最小化平均编码长度的目的。

**Huffman Codes的构建过程**

1. **统计频率**:首先，我们需要统计出每个符号出现的频率。
2. **构造 Huffman 树**:根据频率从高到低排序，选择两个频率最低的符号作为根节点，然后将它们合并成一个新的内部结点，其频率为两个结点频率之和。重复此过程直至所有符号都被处理。
3. **编码**:对每个符号进行编码，根据 Huffman 树的结构，从根结点开始，沿着左子树或右子树移动，直到达到叶结点（即原始符号）。编码长度为从根结点到叶结点所经过的路径长度。

**Huffman Codes的优点**

1. **平均编码长度最小**:通过自适应地调整编码长度，Huffman Codes能够实现平均编码长度最小化。
2. **压缩率高**:由于变长编码方式，Huffman Codes能够有效地压缩数据。

**Huffman Codes的缺点**

1. **构建时间较长**:构造 Huffman 树需要花费一定的时间和资源。
2. **编码长度不确定**:由于 Huffman Codes是变长编码方式，其编码长度不确定，可能会导致解码过程复杂化。

**示例代码**

import heapqclass Node:
 def __init__(self, char, freq):
 self.char = char self.freq = freq self.left = None self.right = Nonedef build_huffman_tree(freqs):
 #1. 统计频率 nodes = [Node(char, freq) for char, freq in freqs.items()]
 #2. 构造 Huffman 树 heap = []
 for node in nodes:
 heapq.heappush(heap, (node.freq, len(heap), node))
 while len(heap) >1:
 freq1, _, node1 = heapq.heappop(heap)
 freq2, _, node2 = heapq.heappop(heap)
 new_node = Node(None, freq1 + freq2)
 new_node.left = node1 new_node.right = node2 heapq.heappush(heap, (new_node.freq, len(heap), new_node))
 return heap[0]

def build_codes(root):
 codes = {}
 def dfs(node, code):
 if node.char is not None:
 codes[node.char] = code else:
 dfs(node.left, code + "0")
 dfs(node.right, code + "1")
 dfs(root, "")
 return codes# 测试数据freqs = {
 'A':10,
 'B':5,
 'C':7,
 'D':3}

root = build_huffman_tree(freqs)
codes = build_codes(root)

print(codes) # {'A': '0', 'B': '110', 'C': '1110', 'D': '1111'}