3.1 变长编码（Variable-Length Encoding）

核心思想

• 高频符号 → 短码
• 低频符号 → 长码
  这样可以降低平均码长，从而实现压缩
  这种操作既可以在 源编码器（source encoder） 里完成，也可以交给单独的 compressor 来做

历史类比：摩尔斯电码

• 在第2章教材就提过：摩尔斯电码是最早的变长编码例子
  • 高频字母（如 E, T）用短符号（. 或 -）
  • 低频字母（如 Q, Z）用更长符号
• 整体上平均下来，比“所有字母都等长”要节省
  这就是平均意义上的压缩

数学直觉

• 设字母表$X={x1​,…,xn​}$，每个符号概率为 $p(xi​)$，对应码长$L(xi​)$
• 平均码长：
  $Lˉ=i∑​p(xi​)L(xi​)$
• 如果符号频率极不均衡，合理设计 $L(xi)$ 可以大幅减少 $Lˉ$
• 极限情况：$Lˉ≥H(X)$ （这在信息论的“源编码定理”里严格证明）

必须满足的条件：前缀码

• 问题：如果不小心设计出“某个码是另一个码的前缀”，解码就会歧义
  • 例：若 A=0，B=01，那 01 到底是 A + ? 还是 B？
• 解决：用 前缀码（prefix-free code）。任何码字都不是另一码字的前缀
  • 例如摩尔斯电码通过加空格来实现同步（虽然摩尔斯本身不是严格前缀码）

优缺点

✅ 优点

• 压缩效果显著（尤其是分布不均时）
• 概念简单，广泛应用（霍夫曼、算术编码等都属于变长编码）
  ⚠️ 缺点
• 错误传播：比定长码更敏感，一旦某个 bit 错位，后面可能全错
• 同步问题：需要精心设计（前缀码 / 加分隔符）
  太好了 👍 你这个格式清晰明了，完全可以拿来当讲义。那我就按照你给的 Markdown 格式，把 3.2 游程编码（Run-Length Encoding, RLE） 整理成同样的结构，方便你直接接着用。

3.2 游程编码（Run-Length Encoding, RLE）

核心思想

• 连续重复的符号 → 压缩为 (符号, 次数)
  • 这样避免逐个重复写符号，用更短的表示来存储长序列
• 适合有长片段重复的数据

例子

原始消息：
a B B B B B a a a B B a a a a
编码后：
a 1 B 5 a 3 B 2 a 4

历史/应用类比

• 国旗示例：德国国旗（黑、红、黄三条纯色带），可以只存“黑多少行、红多少行、黄多少行”，而不是每个像素逐一存
• 传真技术：黑白文档扫描 → 只需传“多少个白点/黑点”，因为只有两种颜色，不需要重复写颜色本身

数学直觉

• 假设一段连续符号长度为 $k$：
  • 普通存储：需要 $k$ 个符号
  • RLE 存储：只需 1 个符号 + 次数表示（$\log k$ 位）
• 当 $k$ 很大时，压缩率接近 $1/k$，节省极大

必须满足的条件

• 数据必须存在长游程（长段重复），否则压缩效果很差
• 编码格式必须明确区分“符号本身”和“次数表示”

优缺点

✅ 优点

• 对图像大色块、二值文档等非常高效
• 算法简单，编码/解码速度快
  ⚠️ 缺点
• 对照片、彩色渐变等场景几乎无压缩效果，甚至可能变大（因为要额外存次数）
• 噪声敏感：即便数据本身相似，但被噪声打断游程，压缩率也会急剧下降

3.3 静态字典（Static Dictionary）

核心思想

• 如果编码系统有未用到的码字，就可以把它们分配给高频的字符串，作为缩写
• 这样一整个常用词（如“the”）就能用一个码字表示，节省空间
• 这种字典（codebook）是静态的，即在所有消息中固定不变

历史/应用类比

• 英国海军百叶窗光学电报（1796）：
  • 每个信号站有6片百叶，开/关组合可形成64种状态
  • 除了字母、数字和控制符号外，多余的状态被分配给常见词语和短语，例如 “the”“Portsmouth”“Admiral”“east”等
  • 从伦敦到普利茅斯 500 英里，信息往返仅需3分钟

数学直觉

• 假设原来常用词需要 $k$ 个字母 → $kL$ 比特（每字母$L$比特）
• 如果用未用码字替换，只需 $L$ 比特
• 平均码长减少，压缩率取决于该常用词出现的频率

必须满足的条件

• 所有通信双方必须事先共享同一份字典
• 字典不能随意更改，否则解码会失败

优缺点

✅ 优点

• 一次分发，长期复用；适合领域内高频短语固定的场景
• 对“专业、固定语境”的通信（如军事/协议）非常高效
  ⚠️ 缺点
• 错误放大：一个比特错误可能导致完全错误的词语（如“east”变“south”）
• 适应性差：面对多样化文本时效果很差；难以覆盖所有场景

3.4 半自适应字典（Semi-adaptive Dictionary）

核心思想

• 与静态字典不同，半自适应字典是针对每条消息单独构建的
• 能更好地利用该消息的高频模式，提高压缩率

数学直觉

• 分析整条消息，找出最常见的符号串作为字典项
• 压缩效果比静态字典更好，但需要额外传输字典，开销增加

必须满足的条件

• 必须完整读取消息后才能分析并生成字典 → 导致高延迟
• 发送方需附带字典，接收方才能解码 → 增加额外传输成本
• 需要足够内存来存放整条消息和字典

优缺点

✅ 优点

• 针对性强，压缩率通常更高
  ⚠️ 缺点
• 延迟大
• 字典传输开销高
• 存储需求大

3.5 动态字典（Dynamic Dictionary, LZW）

核心思想

• 在处理消息的过程中，边读边生成字典
• 字典不需要随消息一起传输，编码器和解码器都能在运行中同步构建
• 代表算法：LZW (Lempel–Ziv–Welch)

背景

• Lempel 和 Ziv 提出了 LZ77 / LZ78 系列算法
• Welch 在 1984 年改进为 LZW，满足了“无需传输字典、单次扫描、可逆”的要求
• 被广泛用于文本压缩和图像压缩（如 GIF 格式）

数学直觉

• 初始字典只包含所有可能的单字符（以及控制符号 Start / Stop）
• 在读消息时：
  • 如果新串在字典中 → 继续扩展
  • 如果新串不在字典中 → 输出旧串的码字，并把新串加入字典
• 解码端用相同规则同步建字典 → 无需传字典本身

必须满足的条件

• 编码器和解码器的初始字典一致（通常是 ASCII 表）
• 都按照相同规则在相同顺序更新字典

优缺点

✅ 优点

• 无需传字典，传输开销小
• 单次扫描，适合流式处理
• 压缩率较高，尤其在重复模式较多的文本/图像上可达约 2×
• 应用广泛：ZIP、GIF、TIFF 等
  ⚠️ 缺点
• 在数据没有重复模式时，压缩率不高
• 历史上有过专利限制（现已过期）

3.6 不可逆压缩技术 (Irreversible / Lossy Compression)

核心思想

• 允许丢失部分信息，解码时只能得到“近似”的原始数据
• 目标是：对人类感知或应用需求来说 “足够好”，但比无损压缩节省得更多

特点

• 解码结果 ≠ 原始数据，但在感知上差异不明显
• 压缩比通常远高于无损方法
• 常用在图像、音频、视频、多媒体等场景

常见例子

• 浮点数表示：有限精度的小数存储本质上就是有损（部分小数无法精确表示）
• JPEG 图像压缩：利用 离散余弦变换 (DCT) 把图像分解为频率成分，低频成分保留，高频成分（人眼不敏感）被丢弃
• MP3 音频压缩：利用心理声学模型，去掉人耳听不到或不敏感的声音成分

数学直觉

• 如果数据 $X$ 中的信息熵为 $H(X)$，无损压缩的码长下界是 $H(X)$
• 有损压缩则是：放弃重建精确 $X$，只保证输出 $\hat{X}$ 与 $X$ 在某个失真度量 $D(X,\hat{X})$ 下“足够小”
• 这在信息论中由 率失真理论 (Rate-Distortion Theory) 严格刻画

优缺点

✅ 优点

• 压缩率极高
• 更符合感知需求（关注“看起来/听起来”相似）
  ⚠️ 缺点
• 信息不可逆丢失
• 误差可能在多次处理/传输后积累
• 需要仔细选择失真度量，确保“丢掉的部分”确实不重要

3.8 二维离散余弦变换 (2-D DCT)

核心思想

• DCT 是 JPEG 图像压缩的核心步骤
• 作用：把图像的像素块从 空间域 转换到 频率域
• 在频率域中：
  • 低频成分（整体亮度、平滑变化）对人眼最重要 → 保留
  • 高频成分（边缘、细节、噪声）人眼不敏感 → 可丢弃或量化得更粗
• 从而实现 有损压缩

数学直觉

• 一维情况：向量 $I$ 经过矩阵 $C$ 变换得到 $O=C I$
  • $C$ 的每一行相当于一个 基函数（cos 波形）
  • $O$ 的元素就是输入在这些基函数上的“投影系数”
  • 二维情况：图像块是矩阵 $X$，经过 DCT 得到 $Y$：
    • $Y = C^{T} X C$
    • $C$ 是 DCT 变换矩阵
    • 可以反变换：$X = C Y C^{T}$

基本性质

• DCT 的变换矩阵 $C$ 是 正交矩阵，其逆矩阵等于转置：$C^{-1} = C^{T}$
• 每个 $Y_{ij}$ 对应一个 空间频率模式
• 这些模式（称为 基图像 / basis images）像棋盘格一样：
  • 左上角：低频，整体平滑
  • 右下角：高频，快速变化

压缩原理

• 把图像分成 8×8 小块（JPEG 标准）
• 对每个块做 DCT，得到 64 个系数
• 低频系数：保留得精细
• 高频系数：量化时强烈压缩，很多直接置 0
• 这样高频细节被舍弃，但整体视觉质量仍然保持

示例

• 对 4×4/8×8/16×16 图像块，生成基图像：
  • 左上：均匀灰度（DC 分量，代表平均亮度）
  • 边缘附近：水平/垂直/斜线条纹
  • 右下：高频棋盘格图案
• JPEG 的量化表会专门针对右下角（高频区域）系数压得更狠

优缺点

✅ 优点

• 符合人眼感知特性（高频不敏感）
• 有快速算法（类似 FFT），高效实现
• 是 JPEG、MPEG 等图像/视频标准的核心
  ⚠️ 缺点
• 有损，不可完全还原
• 分块（8×8）可能造成 block artifacts（方格感）
• 高频细节容易丢失