---
title: Tokenization：子词切分的数学体系
draft: false
tags:
  - Tokenization
  - BPE
  - SentencePiece
  - WordPiece
  - NLP
  - 大语言模型
---

# Tokenization：子词切分的数学体系

---

## 一、问题引入：为什么需要子词切分

### 1.1 词级切分的问题

**词级（Word-level）切分**将文本分割为单词集合：
- 词表大小受语料库词汇量限制
- 未登录词（OOV）无法处理
- 多语言场景下词表膨胀

**数学表示**：

设词表为 $V$，单词 $w \in V$。对句子 $s = w_1 w_2 \ldots w_T$，词级切分要求 $w_i \in V, \forall i$。

当遇到新词 $w_{i} \notin V$ 时，系统必须返回 UNK（unknown） token，这丢失了所有语义信息。

### 1.2 字符级切分的问题

**字符级（Character-level）切分**将文本分割为字符集合：
- 彻底解决 OOV 问题
- 序列长度大幅增加（英文增加约 4-8倍，中文增加更多）
- 字符的语义信息远低于词

**序列长度对比**（以英文为例）：

| 切分方式 | 平均序列长度倍数 |
|---------|----------------|
| 词级 | 1×（基准） |
| 子词级 | 1.3-1.7× |
| 字符级 | 4-8× |

### 1.3 子词切分的核心思想

**子词切分（Subword Tokenization）**是两种极端之间的平衡：

> 将罕见词拆分成更小的子词片段，同时保留高频词的完整性。

**关键观察**：
- 词的内部结构是有意义的（如 "unexpected" = "un" + "expect" + "ed"）
- 语言的词形态变化有规律（如 "running" = "run" + "n" + "ing"）
- 子词片段可以跨词共享（如 "un" 出现在 "unexpected", "unfair", "undo"）

**目标**：
1. 将开放词表问题变成**有限词表问题**
2. 保持合理的序列长度
3. 保留子词的语义可解释性

---

## 二、BPE（Byte Pair Encoding）

### 2.1 算法起源与核心思想

BPE 最初是 Gage（1994）提出的一种数据压缩算法，用于压缩稀有字节序列。后被 Sennrich et al.（2016）引入 NLP 作为子词切分算法。

**关键区分（两类工业主流BPE）**：

1. **Sennrich 字符级 BPE**：机器翻译使用，拆分英文单词字符
2. **GPT 字节级 BPE**：大模型标配，**直接操作 UTF-8 字节**，无语言字符依赖，彻底杜绝 OOV

**核心思想**：

在语料库中迭代地合并最高频的相邻字节对（byte pairs），最终构建一个包含所有子词单元的固定词表。

### 2.2 算法的数学形式化

**定义（字符序列）**：

设语料库为 $C$，其中每个样本是字符序列 $c_1 c_2 \ldots c_n$。

**定义（BPE 合并操作）**：

给定字符序列，定义所有相邻对（pair）为：
$$\mathcal{P}(c_1 \ldots c_n) = \{ (c_i, c_{i+1}) : 1 \leq i < n \}$$

**定义（合并频率）**：

对于每个 pair $p = (a, b)$，定义其在语料库中的出现频率：
$$\text{freq}(p) = \sum_{s \in C} \text{count}_s(p) \tag{2.1}$$

其中 $\text{count}_s(p)$ 是 pair $p$ 在序列 $s$ 中出现的次数。

### 2.3 BPE 算法步骤

**Algorithm: BPE Tokenization**

**输入**：语料库 $C$，目标词表大小 $|V|$（不含 UNK 和句子开始/结束等特殊 token）

**预处理**：
1. 将每个词拆分为字符序列
2. 统计所有字符级别的 pair 频率
3. **现代大模型规范**：使用前缀空格符 Ġ 替代老式 `</w>` 词尾标记，便于解码保真

**迭代**：
```
while |V| < target_size:
    1. 找到语料库中频率最高的 pair (a, b)
    　freq_max = argmax_{(a,b)} freq(a,b)
    2. 将语料库中所有 (a, b) 合并为新符号 "ab"
    　- 更新所有包含 (a, b) 的序列
    　- 更新 pair 频率表
    3. 将 "ab" 加入词表 V
```

**输出**：词表 $V$（包含字符、合并后的子词、以及特殊 token）

### 2.4 BPE 的编码与解码

**编码（Tokenization）**：

给定词 $w = c_1 c_2 \ldots c_n$，编码过程：

1. 初始化：$w = [c_1, c_2, \ldots, c_n]$
2. 如果词不在词表中，重复以下直到所有片段都在词表中：
   - **从右向左**找到最长的、在词表中的子词（工业界标准 BPE 编码方向）
   - 如果找不到，替换为 UNK
3. 返回子词序列

**贪心最长匹配编码**（实际使用）：

```
def encode(word):
    if word not in word_set:
        return [UNK]

    tokens = []
    pos = 0
    while pos < len(word):
        # 尝试最长匹配
        end = len(word)
        found = False
        while end > pos:
            substr = word[pos:end]
            if substr in vocab:
                tokens.append(substr)
                pos = end
                found = True
                break
            end -= 1

        if not found:
            tokens.append(UNK)
            break

    return tokens
```

**解码（Detokenization）**：

给定子词序列 $t_1, t_2, \ldots, t_k$：
1. 去掉所有 </w> 标记
2. 直接拼接相邻子词
3. 返回拼接结果

**注意**：解码需要正确处理空格。例如：
- 子词序列 ["Ġthe", "Ġcat"] 解码为 " the cat"
- Ġ 表示空格

### 2.5 BPE 的数学性质

**性质（词表大小控制）**：

BPE 的词表大小 $|V|$ 可以通过合并次数近似控制：

$$|V| \approx |V_{\text{base}}| + N_{\text{merge}} \tag{2.2}$$

其中 $|V_{\text{base}}|$ 是基础字符数（通常 256-500），$N_{\text{merge}}$ 是执行的合并次数。**注意**：由于合并操作可能产生子词覆盖、冗余淘汰，实际词表大小并非严格线性相加，该等式仅为近似关系。

**性质（OOV 处理）**：

对于未登录词 $w$，编码过程保证：
1. 如果 $w$ 可以完全分解为词表中的子词，则编码成功
2. 否则，包含 UNK token

**性质（子词共享）**：

设两个词 $w_1$ 和 $w_2$ 共享一个子词单元 $s$，则在编码表示中：
$$I(w_1) \cap I(w_2) \neq \emptyset \tag{2.3}$$

其中 $I(w)$ 是词 $w$ 编码后的子词索引序列。

### 2.6 BPE 的变种与改进

**Faster BPE（基于 Trie 树）**：

使用 Trie 树存储词表，可以 $O(1)$ 查找子词：
- 节点表示字符
- 边表示子词片段
- 时间复杂度从 $O(n \cdot m)$ 降到 $O(n)$

**BPE-Dropout**：

在编码时随机跳过合并操作：
- 训练时使用 dropout：每次以概率 $p$ 跳过某个合并
- 推理时不使用 dropout
- **完整作用**：1. 增强分词鲁棒性 2. 生成多粒度子词序列 3. 大幅提升低资源语种泛化能力

---

## 三、SentencePiece

### 3.1 设计动机

**BPE 的问题**：

1. **需要预处理**：BPE 假设文本已经被"空格分隔"，但很多语言（如中文、日文）不使用空格分词
2. **语言依赖**：分词器需要针对每种语言单独开发
3. **歧义问题**：空格分词在某些语言中本身就有歧义（如德语复合词）

**SentencePiece 的核心思想**：

> 将整个句子视为一个字符序列，不依赖任何预处理的分词，直接在原始文本上运行 BPE。

**核心规则**：`▁`（U+2581）仅作为子词**开头前缀**，不会出现在子词中部，是解码保真的关键。

### 3.2 算法描述

**Algorithm: SentencePiece Training**

**输入**：
- 原始语料库（未分词的文本）
- 目标词表大小 $|V|$
- 字符归一化配置（Unicode NFC/NFD）

**预处理**：
1. **字符归一化**：将 Unicode 文本标准化（如将 é 转为 e + accent 的组合）
2. **空格替换**：将空格替换为特殊字符 ▁（U+2581）
3. 直接构建字符序列

**训练**：与标准 BPE 完全相同

**解码**：
1. 将 ▁ 替换为空格
2. 拼接子词
3. 逆标准化

### 3.3 与标准 BPE 的关键区别

| 维度 | 标准 BPE | SentencePiece |
|------|---------|--------------|
| **输入** | 预分词文本（空格分隔） | 原始句子（无需分词） |
| **空格处理** | 丢失（被空格分词） | 保留（替换为 ▁） |
| **语言依赖** | 需要语言特定分词器 | 语言无关 |
| **解码保真度** | 空格可能丢失 | 完全恢复原始文本 |

### 3.4 归一化与逆标准化

**Unicode 归一化**：

SentencePiece 使用 Unicode 归一化确保一致的字符表示。**工业界统一使用 NFKC**：

| 形式 | 示例 | 说明 |
|------|------|------|
| **NFC** | é（单一字符） | 组合形式 |
| **NFD** | e + combining accent | 分解形式 |
| **NFKC** | é（单一字符） | **业界标配**，规范化兼容区字符（如全角转半角） |
| **NFKD** | e + combining accent | 分解兼容区字符 |

**逆标准化**：

训练时记录归一化映射，解码时逆应用以恢复原始表示。

### 3.5 子词平滑与置信度

**定义（子词置信度）**：

对于编码后的子词序列 $s_1, s_2, \ldots, s_k$，定义子词置信度：
$$\text{conf}(s_i) = \frac{\text{freq}(s_i)}{\sum_{j=1}^k \text{freq}(s_j)} \tag{3.1}$$

这衡量了子词在训练语料中的统计显著性。

**应用**：

在某些实现中，低置信度的子词可以被进一步拆分或标记为 UNK。

---

## 四、WordPiece

### 4.1 算法起源与与 BPE 的区别

WordPiece 由 Schuster 和 Nakajima（2012）提出，最早用于 Google 的日语/韩语语音搜索系统，后被 BERT 采用。

**与 BPE 的关键区别**：

| 维度 | BPE | WordPiece |
|------|-----|----------|
| **选择合并的依据** | 最高频率的 pair | 最大似然的 pair |
| **合并判据** | $\text{freq}(a,b)$ | $\text{score}(a,b) = \log P(a,b) - \log P(a) - \log P(b)$ |
| **编码策略** | Longest-match-first | 同样使用 Longest-match-first |
| **语言学偏好** | 无 | 可能倾向于有语言学意义的切分 |

### 4.2 WordPiece 的数学推导

**核心思想**：

BPE 基于频率，WordPiece 基于**子词序列的似然**。

设语料库为 $C$，词 $w$ 可以被切分为子词序列 $s_1, s_2, \ldots, s_k$。

**定义（词的似然）**：

$$P(w) = \prod_{i=1}^k P(s_i) \tag{4.1}$$

其中 $P(s)$ 是子词 $s$ 在语料库中的（归一化）频率。

**定义（合并得分）**：

对于候选 pair $(a, b)$，定义合并得分：
$$\text{score}(a,b) = \log P(ab) - \log P(a) - \log P(b) \tag{4.2}$$

**推导**：

考虑将 $a$ 和 $b$ 合并为 $ab$。合并后的似然变化为：
$$\Delta = \log P(ab) - (\log P(a) + \log P(b)) \tag{4.3}$$

当 $\Delta > 0$ 时，合并能提高整体似然。WordPiece 选择使 $\Delta$ 最大的 pair 进行合并。

**等价的频率解释**：

部分实现使用频率近似替代对数似然比：
$$\text{score}(a,b) \approx \log \frac{\text{freq}(ab)}{\text{freq}(a) \cdot \text{freq}(b)}$$

这是对互信息的简化近似。**注意**：原版 WordPiece 核心是基于对数似然的得分公式（式 4.2），频率等价形式仅为工程实现近似，并非官方标准形式。

### 4.3 WordPiece 算法步骤

**Algorithm: WordPiece Training**

**输入**：语料库 $C$，目标词表大小 $|V|$

**预处理**：
1. 将每个词初始化为字符序列
2. 统计所有子词（包括字符）的频率

**迭代**：
```
while |V| < target_size:
    1. 对于每个候选 pair (a,b)，计算 score(a,b)
    　- 使用动态规划避免重复计算
    2. 找到 score 最高的 pair
    3. 合并该 pair，加入词表
    4. 更新频率表
```

### 4.4 编码算法

**Algorithm: WordPiece Encoding**

**输入**：词 $w$，词表 $V$

**初始化**：
$$S = [c_1, c_2, \ldots, c_n]$$

其中 $c_i$ 是字符，末尾不加特殊标记（与 BPE 不同）

**贪心切分**：
```
while S is not empty:
    1. 从 S 的起始位置开始
    2. 尝试找到最长的、在词表中的前缀
    　- 如果找到长度 L 的子词，加入结果，消耗 L 个字符
    　- 如果没找到，输出 [UNK]
    3. 重复直到 S 为空
```

**与 BPE 的细微区别**：

WordPiece 的编码更严格地依赖词表。在 BERT 实现中：
1. 使用 [UNK] token 表示单个未知字符
2. 如果整个词都无法编码，也使用 [UNK]

### 4.5 BERT 中的 WordPiece 实现

**BERT 使用的 WordPiece 标志性规则**：**词内子词添加 `##` 前缀**

例如 `running` → `run ##ning`

这使得 BERT 能够区分：
- `run` 是独立词
- `##ning` 是词内子词（接在前面的词后面）

**特殊 Token**：

| Token | 含义 |
|-------|------|
| [PAD] | 填充 |
| [UNK] | 未知词 |
| [CLS] | 分类任务特殊位 |
| [SEP] | 句子分隔 |
| [MASK] | 掩码 |

**词表结构**：

BERT 的词表包含：
- 约 30,522 个 WordPiece token
- 覆盖英文的 BPE 风格子词
- 包含常见标点和符号

### 4.6 线性时间实现

**问题**：朴素的 WordPiece 编码在最坏情况下是 $O(n^2)$ 的。

**解决方案（最大前缀匹配）**：

使用 Trie 树（或者 BERT 使用的改进版）实现 $O(n)$ 编码：

1. 构建 Trie 树，节点是字符，边是子词
2. 从根节点开始，贪心地寻找最长匹配
3. 每一步查找是 $O(1)$，总复杂度 $O(n)$

**字典树实现的关键操作**：

```python
def encode(self, text):
    tokens = []
    pos = 0
    while pos < len(text):
        # 在 Trie 中找最大匹配
        node = self.root
        longest = 0
        for i in range(pos, len(text)):
            if text[i] not in node.children:
                break
            node = node.children[text[i]]
            if node.is_word_end:
                longest = i - pos + 1
        if longest > 0:
            tokens.append(text[pos:pos+longest])
            pos += longest
        else:
            tokens.append([UNK])
            pos += 1
    return tokens
```

---

## 五、三种 Tokenizer 的对比与实践

### 5.1 数学对比

| 维度 | BPE | SentencePiece | WordPiece |
|------|-----|--------------|-----------|
| **合并依据** | 频率 $\max \text{freq}(a,b)$ | 频率（同 BPE） | 似然 $\max \text{score}(a,b)$ |
| **核心公式** | $\text{freq}(ab)$ | $\text{freq}(ab)$ | $\log P(ab) - \log P(a) - \log P(b)$ |
| **输入格式** | 预分词文本 | 原始文本 | 预分词文本 |
| **语言依赖** | 需要分词器 | 语言无关 | 需要分词器 |

### 5.2 词表大小对性能的影响

**词表大小 $|V|$ 与 OOV 率的关系**：

设语料库中词的频率分布为 $P(w)$，词表大小为 $|V|$。定义截断分布：
$$P_V(w) = \begin{cases} P(w) & \text{if } w \in V \\ \sum_{w' \notin V} P(w') & \text{if } w = \text{UNK} \end{cases} \tag{5.1}$$

**OOV 率**：
$$\text{OOVRate} = \sum_{w \notin V} P(w) \tag{5.2}$$

**词表大小与覆盖率的实验规律**：

对于大规模英文语料：
- $|V| = 10,000$：覆盖率约 85-90%
- $|V| = 30,000$：覆盖率约 95-98%
- $|V| = 50,000$：覆盖率约 98-99%

**中文场景注意**：上述英文数据**不能套用于中文**。中文以单字为基础单元，需要更大词表（通常 50K-100K+），序列长度变化规律与英文完全不同。

### 5.3 子词切分的质量指标

**定义（子词信息熵）**：

对于子词序列 $s_1, \ldots, s_k$，定义其信息熵：
$$H(s) = -\sum_{i=1}^k P(s_i) \log P(s_i) \tag{5.3}$$

其中 $P(s_i)$ 是子词 $s_i$ 在词表中的（归一化）频率。

**定义（子词完整性）**：

对于词 $w$，定义子词完整性：
$$\text{Integrity}(w) = \frac{\text{len}(I(w))}{\text{len}(w)} \tag{5.4}$$

其中 $\text{len}(I(w))$ 是切分后所有子词的总长度（字符数），$\text{len}(w)$ 是原词长度。**比值越大代表切分越零碎**（与原文相反）。

**澄清**：子词信息熵 $H(s) = -\sum P(s_i)\log P(s_i)$ 仅用于衡量**词表整体分布均衡性**，不能直接用于评判单条文本分词质量。

### 5.4 训练中的常见问题

**问题 1：词表大小选择**

- **过大**：过拟合到训练语料，泛化能力差
- **过小**：OOV 率高，子词序列过长

**解决方案**：

1. 从 10K 开始，逐步增大到 50K，观察 OOV 率和序列长度
2. 选择使 $f(|V|) = \alpha \cdot \text{OOVRate} + \beta \cdot \text{AvgSeqLen}$ 最小的 $|V|$

**问题 2：特殊字符处理**

**解决方案**：
1. 统一 Unicode 归一化（NFKC）
2. 处理控制字符和格式字符
3. 对于中文字符，通常按单个字符处理

**问题 3：训练语料偏置**

如果训练语料中某类词出现频率过高，词表会偏向这些词。

**解决方案**：
1. 下采样高频词
2. 使用分层采样

---

## 六、数学公式速查

### 6.1 BPE 核心公式

**Pair 频率**：
$$\text{freq}(a,b) = \sum_{s \in C} \text{count}_s(a,b) \tag{6.1}$$

**词表大小**：
$$|V| \approx |V_{\text{base}}| + N_{\text{merge}} \tag{6.2}$$

（近似关系，非严格等式）

### 6.2 WordPiece 核心公式

**合并得分**：
$$\text{score}(a,b) = \log P(ab) - \log P(a) - \log P(b) \tag{6.3}$$

### 6.3 性能指标

**OOV 率**：
$$\text{OOVRate} = \sum_{w \notin V} P(w) \tag{6.5}$$

**子词信息熵**：
$$H(s) = -\sum_{s_i} P(s_i) \log P(s_i) \tag{6.6}$$

---

## 七、总结

**三种 Tokenizer 的定位**：

| Tokenizer | 适用场景 | 核心优势 |
|---------|---------|---------|
| **BPE** | 英文为主的西方语言 | 简单高效，易于实现 |
| **SentencePiece** | 多语言、无分词语言的场景 | 语言无关，端到端训练 |
| **WordPiece** | BERT 等需要高质量表示的任务 | 语言学意义的切分倾向 |

**核心洞察**：

> 子词切分是连接"字符级无 OOV"和"词级语义丰富"的最优解。BPE/WordPiece 通过统计语料库中的 n-gram 频率，在数据驱动和人工设计之间找到了平衡点。SentencePiece 通过端到端的训练方式，使得子词切分不再依赖语言特定的预处理，为多语言模型提供了统一的基础设施。

**工程实践要点**：

1. 词表大小需要根据具体任务调整，中文通常需要更大的词表
2. SentencePiece 是当前多语言模型的事实标准
3. 编码时使用 Trie 树可以显著加速

---

**延伸阅读**：

1. Gage, "A New Algorithm for Data Compression" (1994) — BPE 原始论文
2. Sennrich et al., "Neural Machine Translation of Rare Words with Subword Units" (2016) — BPE 引入 NLP
3. Schuster and Nakajima, "Japanese and Korean Voice Search" (2012) — WordPiece 原始论文
4. Kudo, "Subword Regularization: Breaking Text into Subwords for Neural MT" (2018) — SentencePiece
5. Provilkov et al., "BPE-Dropout: Simple and Effective Subword Regularization" (2020)