编辑“︁哈夫曼编码”︁

{{DISPLAYTITLE:哈夫曼编码}}

'''哈夫曼编码'''（Huffman Coding）是一种基于[[贪心算法]]的[[无损数据压缩]]方法，由大卫·哈夫曼（David A. Huffman）于1952年提出。它通过为不同频率的字符分配不同长度的编码，使得高频字符使用较短的编码，低频字符使用较长的编码，从而实现数据的高效压缩。

== 基本概念 ==
哈夫曼编码的核心思想是构造一棵'''最优前缀编码树'''（即哈夫曼树），使得编码后的数据总长度最短。其特点包括：
* '''前缀编码'''：没有任何一个编码是另一个编码的前缀，避免解码时的歧义。
* '''贪心选择'''：每次合并频率最低的两个节点，保证局部最优解最终导向全局最优解。

=== 数学表示 ===
给定字符集 <math>C = \{c_1, c_2, \dots, c_n\}</math> 及其对应频率 <math>f(c_i)</math>，哈夫曼编码的目标是最小化总编码长度：
<math>
B(T) = \sum_{i=1}^n f(c_i) \cdot d_T(c_i)
</math>
其中 <math>d_T(c_i)</math> 是字符 <math>c_i</math> 在树 <math>T</math> 中的深度（即编码位数）。

== 算法步骤 ==
哈夫曼编码的构造过程如下：
# 统计字符频率，为每个字符创建叶子节点。
# 将节点按频率升序排列，放入优先队列（最小堆）。
# 循环执行以下操作，直到队列中只剩一个节点：
  ## 取出频率最小的两个节点，合并为新节点（频率为两者之和）。
  ## 将新节点放回队列。
# 最后剩下的节点即为哈夫曼树的根节点。
# 从根节点出发，左分支标记0，右分支标记1，生成每个字符的编码。

=== 示例 ===
假设字符集为 <math>\{A, B, C, D\}</math>，频率分别为 <math>\{50, 10, 20, 20\}</math>。构造过程如下：

<mermaid>
graph TD
    A[合并B(10)和C(20) → 30] -->|0| B[B:10]
    A -->|1| C[C:20]
    D[D:20] -->|0| E[合并A(50)和D(20) → 70]
    A -->|1| E
    E -->|0| F[A:50]
    E -->|1| G[D:20]
</mermaid>

最终编码：
* A: 0
* B: 100
* C: 101
* D: 11

== 代码实现 ==
以下是Python实现的哈夫曼编码：

<syntaxhighlight lang="python">
import heapq

class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(freq_map):
    heap = [HuffmanNode(char=c, freq=f) for c, f in freq_map.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, merged)
    
    return heap[0]

def generate_codes(root, current_code="", codes={}):
    if root is None:
        return
    if root.char is not None:
        codes[root.char] = current_code
    generate_codes(root.left, current_code + "0", codes)
    generate_codes(root.right, current_code + "1", codes)
    return codes

# 示例输入
freq_map = {'A': 50, 'B': 10, 'C': 20, 'D': 20}
huffman_tree = build_huffman_tree(freq_map)
codes = generate_codes(huffman_tree)
print("Huffman Codes:", codes)
</syntaxhighlight>

'''输出：'''
<pre>
Huffman Codes: {'A': '0', 'B': '100', 'C': '101', 'D': '11'}
</pre>

== 实际应用 ==
哈夫曼编码广泛应用于：
* '''文件压缩'''：如ZIP、GZIP等格式的核心算法之一。
* '''图像压缩'''：JPEG格式的熵编码阶段使用哈夫曼编码。
* '''通信协议'''：优化数据传输效率。

=== 案例分析 ===
在英文文本中，字母'''E'''的出现频率最高（约12.7%），而'''Z'''最低（约0.07%）。哈夫曼编码会为E分配最短的编码（如1位），为Z分配较长的编码（如6位），整体压缩率可达40%~50%。

== 复杂度分析 ==
* '''时间复杂度'''：使用优先队列构建哈夫曼树为 <math>O(n \log n)</math>（<math>n</math>为字符数）。
* '''空间复杂度'''：存储哈夫曼树需要 <math>O(n)</math> 空间。

== 扩展阅读 ==
* 动态哈夫曼编码（Adaptive Huffman Coding）
* 算术编码（Arithmetic Coding）

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:贪心算法]]