霍夫曼编码

构造最优前缀码的贪心算法：反复合并概率最小的两个符号为一棵子树，自底向上建树，左右枝标 $0/1$，叶子路径即码字。它使平均码长最短，逼近熵。

算术编码

把整条消息编码为 $[0,1)$ 内的一个小区间，按符号概率不断细分。它能突破「整数比特/符号」的限制，比霍夫曼更贴近熵，尤其当概率极不均时。

字典编码（LZ 系列）

LZ77/LZ78 不需先验概率，而是动态地用「指向先前出现过的子串」的指针替换重复内容。ZIP、gzip、PNG 都基于它（常与霍夫曼组合，如 DEFLATE）。

例题

例　符号 $(A,B,C,D)$ 概率 $(0.4,0.3,0.2,0.1)$：霍夫曼合并 $D+C\to0.3$、再 $+B\to0.6$、再 $+A$，得码长 $(1,2,3,3)$，平均 $1.9$ bit，优于定长 $2$ bit。

应用

霍夫曼用于 JPEG、MP3、DEFLATE 的熵编码阶段；算术/区间编码用于 H.264/H.265、bzip2；LZ 字典编码是 ZIP/gzip/PNG 的骨架。压缩软件几乎都是它们的组合。