概念

无损压缩

霍夫曼编码按概率分配变长码字，算术编码实现任意精度压缩，Lempel-Ziv 系列（如 ZIP）在数据流中寻找重复模式。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

无损压缩信息论与编码

01定义

无损压缩剔除统计冗余、保留全部信息：霍夫曼编码按概率分配变长码字，算术编码把整条消息编码为一个区间逼近熵极限，LZ 系列在数据流中引用重复模式——ZIP、PNG、gzip 背后的三大家族。

霍夫曼树：概率决定码长

贪心合并最小概率节点构造二叉树：所得前缀码在整数码长中最优，平均长度 $\in[H,H+1)$ ；符号概率为 2 的负幂时恰达到熵。

按累积概率把消息映射到 $[0,1)$ 的子区间，区间端点二进制展开即码字：每符号平均码长任意逼近 $H$ ——突破霍夫曼的整数码长限制。

LZ77（滑动窗口引用）与 LZ78/LZW（显式字典）无需预知概率即可通用压缩：DEFLATE = LZ77 + 霍夫曼，是 gzip/PNG/ZIP 的共同内核。

H(X)\leq\bar{L}<H(X)+1,\quad \text{算术编码}\ \bar{L}\to H

香农 1948 年给出熵下界与费诺编码；霍夫曼 1952 年作为课程作业发明最优前缀码；Lempel 与 Ziv 1977-78 年提出字典压缩，成为通用压缩的事实标准。

文件压缩（ZIP、7z）、无损图像（PNG、FLIF）、文本索引与搜索（倒排索引 + 压缩）、基因组序列压缩。

哈夫曼编码：最优前缀码逐步合并最小概率节点，构建编码树

step 合并次数0