哈夫曼编码通过为高频字符分配短码、低频字符分配长码的变长编码策略，并确保编码为前缀码以避免歧义，从而显著减少表示相同信息所需的总比特数，达到节省内存的目的。
以下通过一个具体例子对比常规的等长编码与哈夫曼编码，清晰展示其节省内存的原理。
示例：编码字符串 “ABRACADABRA”
假设我们需编码的字符集为 {A, B, C, D, R}。首先统计各字符在字符串中的出现频率（概率）：
| A | 5 | 5/11 ≈ 0.455 |
| B | 2 | 2/11 ≈ 0.182 |
| R | 2 | 2/11 ≈ 0.182 |
| C | 1 | 1/11 ≈ 0.091 |
| D | 1 | 1/11 ≈ 0.091 |
1. 常规等长编码（如ASCII或固定位宽编码）
对于5个不同字符，至少需要3位二进制数（2³=8 > 5）才能唯一表示每个字符。一种可能的等长编码方案如下：
| A | 000 |
| B | 001 |
| C | 010 |
| D | 011 |
| R | 100 |
编码字符串 “ABRACADABRA”：
A B R A C A D A B R A
000 001 100 000 010 000 011 000 001 100 000
总编码长度 = 11个字符 × 3位/字符 = 33位。
2. 哈夫曼编码（变长前缀编码）
根据字符频率构建哈夫曼树（构建过程遵循贪心算法，每次合并频率最小的两个节点），并为从根到叶子的路径分配编码（通常左0右1），得到如下哈夫曼编码表：
| A（频率最高） | 0 | 1位 |
| B | 110 | 3位 |
| R | 111 | 3位 |
| C | 100 | 3位 |
| D | 101 | 3位 |
注意：此编码是前缀码，任何字符的编码都不是另一个字符编码的前缀，确保了解码的唯一性。
使用哈夫曼编码对同一字符串进行编码：
A B R A C A D A B R A
0 110 111 0 100 0 101 0 110 111 0
计算总编码长度：
- A（出现5次）：5 × 1位 = 5位
- B（出现2次）：2 × 3位 = 6位
- R（出现2次）：2 × 3位 = 6位
- C（出现1次）：1 × 3位 = 3位
- D（出现1次）：1 × 3位 = 3位 总长度 = 5 + 6 + 6 + 3 + 3 = 23位。
3. 节省内存对比分析
| 等长编码（3位） | 33 | – | |
| 哈夫曼编码（变长） | 23 | 10 | 约 30.3% |
节省原因的核心解析：
代码示例：哈夫曼树节点结构与编码计算（Python示意）
import heapq
from collections import defaultdict, Counter
class HuffmanNode:
def __init__(self, char, freq):
self.char = char
self.freq = freq self.left = None self.right = None # 用于堆比较 def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(text):
# 1. 统计频率
frequency = Counter(text)
# 2. 构建最小堆（优先队列）
heap = [HuffmanNode(char, freq) for char, freq in frequency.items()]
heapq.heapify(heap)
# 3. 贪心合并：每次弹出两个频率最小的节点，合并为新节点
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
return heap[0] # 返回根节点
def generate_codes(node, current_code="", code_map={}):
if node is None:
return # 叶子节点，存储字符到编码的映射
if node.char is not None:
code_map[node.char] = current_code
generate_codes(node.left, current_code + "0", code_map)
generate_codes(node.right, current_code + "1", code_map)
return code_map
# 示例运行
text = "ABRACADABRA"
root = build_huffman_tree(text)
huffman_codes = generate_codes(root)
print("哈夫曼编码表:", huffman_codes)
# 输出可能类似：{'A': '0', 'C': '100', 'D': '101', 'B': '110', 'R': '111'}
encoded_text = ''.join(huffman_codes[ch] for ch in text)
print("编码结果:", encoded_text)
print("原等长编码长度:", len(text) * 3) # 假设3位等长
print("哈夫曼编码长度:", len(encoded_text))
以上代码演示了哈夫曼树构建与编码生成的关键步骤，实际应用还需包含写入文件头（编码表）等完整压缩流程。
结论：哈夫曼编码通过统计字符频率、构建最优前缀码，使高频字符占用极短码字，从而在整体上大幅降低了数据的比特表示长度。相较于无视频率差异的等长编码，它在处理字符分布不均匀的数据时（这是现实数据的普遍特征），能实现显著的内存节省。
参考来源
- 哈夫曼编码
- 哈夫曼编码
- 哈夫曼编码（字符串压缩）
- 哈夫曼编码与解码
- 算法 {哈夫曼编码, 哈夫曼树}
