当前位置：首页 > news >正文

哈夫曼编码原理分析与仿真实现（P124302047程心惠）

news 2026/6/29 14:05:28

一、研究背景与意义

在数字信息传输与存储过程中，原始信源数据普遍存在大量冗余信息，包括统计冗余、空间冗余、时间冗余等，极大占用了存储资源与传输带宽。信源编码作为信息论的核心技术，核心目标就是通过合理的编码规则，去除信源冗余、压缩数据量，同时保证解码后信息无失真恢复。

变长编码是信源无损编码的重要分支，相较于定长编码，其能够根据符号概率分布动态分配码长，压缩效率更高。哈夫曼编码由戴维·哈夫曼于1952年提出，是目前已知的单符号最优前缀编码，满足前缀编码特性、无译码歧义，且算法逻辑简单、易于工程实现，是无损压缩领域的基础核心算法，被广泛应用于JPEG图像压缩、MP3音频压缩、ZIP文件压缩等主流技术中。

二、研究目标

1、系统梳理离散信源信息熵、自信息量、平均码长、编码效率等基础理论，明确无失真信源编码的理论下界与前缀码约束条件，为哈夫曼编码的最优性分析提供理论支撑。

2、深入研究二元哈夫曼编码的建树规则、码字分配机制与算法流程，总结哈夫曼编码的最优特性、适用场景以及算法固有局限性。

3、基于Python语言搭建完整的哈夫曼编码仿真系统，实现信源概率输入、哈夫曼树自动构建、最优码字生成、序列编码与无失真译码还原的全套功能。

4、完成多组不同概率分布信源的对比仿真，分别计算各组信源的信息熵、平均码长、编码效率与冗余度，量化分析信源概率均匀程度对压缩性能的影响规律。

三、理论基础分析

1、离散无记忆信源与信息熵

设离散无记忆信源：S =

单符号自信息量：符号携带的信息量(单位：bit)；

信源信息熵：信源平均信息量，无失真编码理论下界

；

平均码长：每个信源符号对应码字平均比特数

为符号对应的码字长度；

编码效率：衡量编码压缩性能 η=100%

理想无失真编码满足， η越接近1编码性能越好；

冗余度：γ=1-η，代表编码存在的多余比特。

2、前缀码（即时码）定义

任意一个码字都不能是其他码字的前缀，译码时无需分隔符，收到完整码字即可立即译出对应符号，哈夫曼编码生成的码字天然满足前缀码条件。

3、哈夫曼编码核心原理

哈夫曼编码的核心思想是概率加权最优匹配，通过贪心算法构建最优二叉树（哈夫曼树），将出现概率高的符号置于树的浅层，对应短码字；概率低的符号置于树的深层，对应长码字，最终实现平均码长最小化，无限逼近信源熵极限。

哈夫曼树为带权路径长度最短的二叉树，树中所有叶子节点对应信源符号，节点权重为符号出现概率，带权路径长度即为平均码长。

4、哈夫曼编码构造算法步骤（二元编码）

（1）将所有信源符号按概率从小到大排序；

（2）选取概率最小的两个符号作为左右叶子，合并生成新节点，新节点概率为两节点概率之和；

（3）将合并后的新节点放回符号集合，再次排序；

（4）重复步骤 2、3，直至集合中仅剩余一个根节点，哈夫曼树构建完成；

（5）从根节点出发，左分支标记 0、右分支标记 1（或反之），遍历到叶子节点得到各符号哈夫曼码字。

5、哈夫曼编码最优性说明

在所有二元前缀码中，哈夫曼编码拥有最小平均码长，是单符号离散信源最优无失真前缀码；
但存在局限性：

（1）符号概率分布越均匀，编码效率越低；

（2）符号数量m不为时，存在长短码字差异；

（3）仅针对单符号离散信源最优，扩展信源可进一步提升效率。

四、仿真设计

1、开发环境

编程语言：Python 3.8+
2、整体功能模块划分

（1）节点类模块：定义哈夫曼树节点，存储符号、概率、左右子树；

（2）哈夫曼树构建模块：利用最小堆循环合并低概率节点；

（3）码字生成模块：递归遍历哈夫曼树，生成每个符号对应 0/1 码字；

（4）性能计算模块：自动计算信息熵、平均码长、编码效率；

（5）编码函数：输入原始符号序列，输出压缩二进制串；

（6）译码函数：输入二进制编码串，依据哈夫曼树还原原始符号；

（7）仿真测试模块：多组测试用例自动输出全部结果。

3、完整 Python 仿真代码

import heapq import math # 1. 定义哈夫曼树节点类 class HuffmanNode: def __init__(self, symbol=None, prob=0.0, left=None, right=None): self.symbol = symbol # 信源符号 self.prob = prob # 符号概率 self.left = left # 左子树 0 self.right = right # 右子树 1 # 重载小于号，支持堆排序按概率升序 def __lt__(self, other): return self.prob < other.prob # 2. 构建哈夫曼树 def build_huffman_tree(symbol_prob_dict): heap = [] # 初始化最小堆，存入所有叶子节点 for sym, p in symbol_prob_dict.items(): heapq.heappush(heap, HuffmanNode(symbol=sym, prob=p)) # 循环合并最小概率两个节点 while len(heap) > 1: node1 = heapq.heappop(heap) node2 = heapq.heappop(heap) # 生成新父节点，概率相加 new_node = HuffmanNode(prob=node1.prob + node2.prob, left=node1, right=node2) heapq.heappush(heap, new_node) return heap[0] if heap else None # 3. 递归遍历树，生成符号-码字映射字典 def generate_code_dict(root): code_dict = {} def traverse(node, current_code): if node is None: return # 到达叶子节点，保存码字 if node.symbol is not None: code_dict[node.symbol] = current_code return traverse(node.left, current_code + "0") traverse(node.right, current_code + "1") traverse(root, "") return code_dict # 4. 计算信源信息熵 H(X) def calc_entropy(symbol_prob_dict): entropy = 0.0 for p in symbol_prob_dict.values(): if p > 0: entropy -= p * math.log2(p) return entropy # 5. 计算平均码长 L def calc_avg_length(symbol_prob_dict, code_dict): avg_len = 0.0 for sym, p in symbol_prob_dict.items(): avg_len += p * len(code_dict[sym]) return avg_len # 6. 编码函数：符号序列转二进制串 def huffman_encode(symbol_list, code_dict): bit_str = "" for sym in symbol_list: bit_str += code_dict[sym] return bit_str # 7. 译码函数：二进制串还原符号序列 def huffman_decode(bit_str, root): res_symbols = [] cur_node = root for bit in bit_str: if bit == "0": cur_node = cur_node.left else: cur_node = cur_node.right # 到达叶子节点，读出符号并回到根节点 if cur_node.symbol is not None: res_symbols.append(cur_node.symbol) cur_node = root return res_symbols # ====================== 仿真测试主程序 ====================== if __name__ == "__main__": # 测试1：标准5符号离散信源 print("========== 测试1：5符号离散信源 ==========") source1 = { "a": 0.4, "b": 0.2, "c": 0.2, "d": 0.1, "e": 0.1 } # 构建树、生成码字 tree_root1 = build_huffman_tree(source1) code_table1 = generate_code_dict(tree_root1) H1 = calc_entropy(source1) L1 = calc_avg_length(source1, code_table1) eta1 = H1 / L1 * 100 print("符号 | 概率 | 哈夫曼码字") print("-" * 25) for sym, p in source1.items(): print(f"{sym} | {p:.2f} | {code_table1[sym]}") print(f"\n信源熵 H(X) = {H1:.4f} bit/符号") print(f"平均码长 L = {L1:.4f} bit/符号") print(f"编码效率 η = {eta1:.2f} %") # 编码译码验证 test_seq = ["a", "b", "a", "c", "d", "a", "e"] encode_bits = huffman_encode(test_seq, code_table1) decode_seq = huffman_decode(encode_bits, tree_root1) print(f"\n原始符号序列：{test_seq}") print(f"编码二进制串：{encode_bits}") print(f"译码还原序列：{decode_seq}") print("译码校验：", "正确" if test_seq == decode_seq else "错误") # 测试2：概率均匀信源，对比编码效率 print("\n\n========== 测试2：4符号等概率信源 ==========") source2 = {"w": 0.25, "x": 0.25, "y": 0.25, "z": 0.25} tree_root2 = build_huffman_tree(source2) code_table2 = generate_code_dict(tree_root2) H2 = calc_entropy(source2) L2 = calc_avg_length(source2, code_table2) eta2 = H2 / L2 * 100 print("符号 | 概率 | 哈夫曼码字") print("-" * 25) for sym, p in source2.items(): print(f"{sym} | {p:.2f} | {code_table2[sym]}") print(f"\n信源熵 H(X) = {H2:.4f} bit/符号") print(f"平均码长 L = {L2:.4f} bit/符号") print(f"编码效率 η = {eta2:.2f} %")

4、仿真结果与数据分析

（1）测试1（非均匀概率信源）

信源分布：

1、哈夫曼码字分配：
a：11；b：01；c：00；d：100；e：101

2、计算指标：

信息熵：符号

平均码长：符号

编码效率：η=96.45%

3、编码译码验证：
原始序列["a","b","a","c","d","a","e"]编码后二进制串可无失真还原，译码正确。

4、分析：

（1）信源概率分布差距大，高概率符号分配短码字，低概率符号分配长码字，符合哈夫曼编码核心思想。

（2）平均码长2.20，略大于信源熵2.1219，满足无失真编码下界定理；