PYTHON LESSON 084
文件压缩大师
理解哈夫曼编码“常用的字符用短码”的思想，会用最小堆构造哈夫曼树并计算带权路径长度。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- import heapq 使用最小堆
- heapq.heappush / heappop 入堆出堆
- 每次合并最小的两堆（贪心）
01 · 核心概念
哈夫曼树与哈夫曼编码
哈夫曼树与哈夫曼编码：定长编码里每个字符占的位数一样多，很浪费。哈夫曼编码反其道而行：出现次数多的字符给短码，出现次数少的给长码，总长度立刻下降。这和摩尔斯电码给最常用的 E 安排最短信号是同一个道理。
GESP Python 6 级 · 哈夫曼树GESP Python 6 级 · 哈夫曼编码标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
02 · 语法与规则
先记住这 3 条，再开始写程序
import heapq 使用最小堆先准确读出这条写法的结构与作用。
heapq.heappush / heappop 入堆出堆换一组最小数据，手工推演一次结果。
每次合并最小的两堆（贪心）再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 文件压缩大师：哈夫曼树贪心合并
import heapq
# 一段文字里各字符出现的次数
freq = {"A": 5, "B": 2, "R": 2, "C": 1, "D": 1}
heap = []
for ch, w in freq.items():
heapq.heappush(heap, (w, ch))
total = 0 # 压缩后的总长度（带权路径长度 WPL）
print("初始小堆：", heap)
while len(heap) > 1:
w1, c1 = heapq.heappop(heap)
w2, c2 = heapq.heappop(heap)
merged = w1 + w2
total = total + merged
print(f"合并 {c1}({w1}) 和 {c2}({w2}) → 重量 {merged}")
heapq.heappush(heap, (merged, c1 + "+" + c2))
print("压缩后总长度：", total, "比特")
print("定长 3 比特编码需要：", sum(freq.values()) * 3, "比特")初始小堆： [(1, 'C'), (1, 'D'), (2, 'R'), (5, 'A'), (2, 'B')] 合并 C(1) 和 D(1) → 重量 2 合并 B(2) 和 C+D(2) → 重量 4 合并 R(2) 和 B+C+D(4) → 重量 6 合并 A(5) 和 R+B+C+D(6) → 重量 11 压缩后总长度： 23 比特 定长 3 比特编码需要： 33 比特
每次取最小的两堆合并，合并代价之和就是压缩后的总比特数。
04 · 逐步理解
每一步只解决一个问题
- 01
压缩的核心思想
定长编码里每个字符占的位数一样多，很浪费。哈夫曼编码反其道而行：出现次数多的字符给短码，出现次数少的给长码，总长度立刻下降。这和摩尔斯电码给最常用的 E 安排最短信号是同一个道理。
- 02
造树规则：最小的两堆先合并
哈夫曼树这样造：每个字符是一堆叶子，重量是它的出现次数；每次取出重量最小的两堆，合并成一堆新树（重量相加），放回队伍；重复到只剩一堆为止。这棵树的形状就决定了每个字符的编码。
while len(heap) > 1: w1, c1 = heapq.heappop(heap) w2, c2 = heapq.heappop(heap) heapq.heappush(heap, (w1 + w2, c1 + "+" + c2)) - 03
最小堆：自动排队的小助手
heapq 模块把普通列表变成最小堆：heappop 永远弹出最小元素，heappush 放入新元素并自动维持秩序。比每次 sort 快得多，是贪心算法的标配工具。
import heapq heapq.heappush(heap, (5, "A")) smallest = heapq.heappop(heap) - 04
带权路径长度 WPL
树里每个字符的“编码长度 × 出现次数”加起来叫带权路径长度，也就是压缩后的总比特数。神奇的结论是：把每次合并的重量累加起来，正好等于 WPL——不用真的画出树也能算出来。
total = total + merged - 05
为什么贪心是对的
出现最少的两个字符，编码一定最长，让它们最早合并（坐进树的最深处）最划算；每步都做当前最优的选择，最终就是全局最优——这就是贪心思想。竞赛里“哈夫曼式合并”还会出现在合并果子、绳索拼接等题目里。
- 06
试试新的频次表
把 freq 改成自己名字的拼音字母频次，跑一次看看压缩率。再把某个字符的频次调到特别大，观察它是不是越来越靠近树根（编码越来越短）。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，跟踪每一次合并过程
- 2改一个字符的频次，看总长度怎么变
- 3手算 A、C、D 三个字符的哈夫曼树
- 4想一想：出现次数越多的字符，编码越短还是越长
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
程序组织模块、导入与常用标准库正确导入模块，并按用途查找 math、random、statistics、collections、heapq、bisect 等标准工具。＋
正式定义
模块是可导入的 Python 代码单元，包把模块组织成层次。import 先加载模块并创建模块对象，再把名字绑定到当前命名空间；标准库随 Python 分发，不等于第三方包。
必须掌握
- import module 保留清晰命名空间；from module import name 只导入指定名字；避免 from module import *。
- math 提供 sqrt、floor、ceil、gcd、log、sin 等数学函数和 pi、e 等常量。
- random 用于伪随机模拟，不适合密码安全；需要安全随机时使用 secrets。
- collections.deque 适合双端队列，Counter 适合计数，defaultdict 可按工厂创建缺省值。
- heapq 实现最小堆，bisect 在已排序序列中二分定位，itertools 提供高效迭代组合工具。
- if __name__ == '__main__': 用来区分文件被直接运行还是被导入。
常见误区
- 文件名写成 math.py 导致遮蔽标准库
- import * 污染命名空间
- 把 random 当成加密随机数
- 没有理解工具的数据复杂度就盲目调用
适用边界
- 标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
- Turtle 需要图形窗口，本站文本判题环境不伪造其画布。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
str 是不可变的 Unicode 字符序列。下标访问单个字符，切片生成新字符串；任何看似“修改字符串”的方法都会返回新对象。
必须掌握
- 下标从 0 开始，负下标从末尾开始；切片 s[start:stop:step] 不包含 stop，step 不能为 0。
- 转义序列用于在字面量中表示换行、制表、引号、反斜杠或码点；原始字符串仍有末尾反斜杠限制。
- find 找不到返回 -1，index 找不到抛 ValueError；count 统计不重叠出现次数。
- split 把字符串拆成列表，join 用一个字符串连接可迭代对象中的字符串，strip 只删除两端字符。
- f-string 的格式说明可控制宽度、对齐、精度、进制和百分比；格式化不改变原值。
- isalpha/isdigit 等按 Unicode 定义，不只识别英文字母和 ASCII 数字。
常见误区
- 尝试 s[0] = 'A' 原地修改字符串
- 把 strip('ab') 误解为删除完整子串 'ab'
- find 返回 -1 后直接拿去当有效下标
- 把字节长度与字符长度混为一谈
适用边界
- 正则表达式不在低等级字符串必修范围，但复杂模式匹配时应使用 re，而不是堆叠大量 split/find。
- 面向用户的字符计数还可能涉及组合字符和字素簇，len 统计的是 Unicode 码点序列长度。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
完成检查