Tokenizer

1. 背景：为什么需要分词 (Tokenization)？

计算机本质上只能理解数字。在将自然语言喂给模型之前，必须将其转换为数字编码格式。这个过程叫分词 (Tokenization)，由分词器 (Tokenizer) 完成，输出的结果称为词元 (Token)。

早期的分词方式存在明显局限：

• 按词分词 (Word-based)：用空格或符号切分单词。缺点是词表极大、无法处理未登录词 (OOV)，且难以捕捉相近词的语义关系。
• 按字符分词 (Character-based)：将文本切分为单个字符。优点是能处理 OOV，缺点是序列过长，模型难以捕捉长距离语义依赖。

为了兼顾词表大小和语义表达，现代大模型普遍采用子词分词 (Subword Tokenization)：将常见的词保留，将罕见的词拆分为多个有意义的子词（词根）。

2. 字节对编码算法 (BPE)

代表模型：GPT 系列

2.1 核心思想

BPE 是一种基于频率的贪心合并算法：

1. 初始化词表为所有语料库中出现的基本字符。
2. 统计相邻词元对的出现频率，找到频率最高的一对。
3. 将它们合并成一个新词元。
4. 重复步骤 2-3，直到词表大小达到预设阈值。

2.2 代码实现示例

import re
import collections

def get_stats(vocab):
    """统计词汇表中所有相邻字符对的出现频率"""
    pairs = collections.defaultdict(int)
    for word, freq in vocab.items():
        symbols = word.split()
        for i in range(len(symbols) - 1):
            pairs[symbols[i], symbols[i+1]] += freq
    return pairs

def merge_vocab(pair, v_in):
    """将最高频的字符对合并，并更新词汇表"""
    v_out = {}
    bigram = re.escape(' '.join(pair))
    # 确保匹配的是被空格或字符串边界包围的完整 bigram
    p = re.compile(r'(?<!\S)' + bigram + r'(?!\S)')
    
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out

# 初始化词汇表
vocab = {
    'h u g </w>': 1, 
    'p u g </w>': 1, 
    'p u n </w>': 1, 
    'b u n </w>': 1
}

num_merges = 4
for i in range(num_merges):
    pairs = get_stats(vocab)
    if not pairs:
        break
    best = max(pairs, key=pairs.get)
    print(f"Merge {i+1}: {best} -> {''.join(best)}")
    vocab = merge_vocab(best, vocab)

print("\n最终词汇表:")
for word, freq in vocab.items():
    print(f"{word}: {freq}")

3. WordPiece 分词算法

代表模型：Google BERT

3.1 核心定义

WordPiece 基于 BPE 衍生而来，其核心改进在于合并标准：从 BPE 的“最高共现频率”改为“最大化提升语料库语言模型概率 (Likelihood)”。

3.2 与 BPE 的关键差异

3.3 数学原理：最大化似然增益

目标函数：
$\Delta \log P = \log P(C_{\text{after}}) - \log P(C_{\text{before}})$

近似公式：
$\Delta \log P \approx n_{ab} \cdot \log \frac{P(ab)}{P(a) \cdot P(b)} = n_{ab} \cdot \text{PMI}(a, b)$

其中 $\text{PMI}(a, b)$ 为点互信息：
$\text{PMI}(a, b) = \log \frac{P(a, b)}{P(a)P(b)}$

• PMI > 0：正相关（如 q 和 u），一起出现的概率高于随机预期。
• PMI = 0：独立。
• PMI < 0：负相关。

结论：WordPiece 优先合并那些既高频又具有强关联性的字符对。

3.4 实例对比

• BPE 会选择 (x, y)（频率最高）。
• WordPiece 会选择 (q, u)（似然增益最大，因为 qu 几乎总是成对出现，合并后能显著简化编码）。

3.5 WordPiece 实例演示

假设我们有一个微型语料库，目标是构建一个小型词汇表。

初始状态：

• 语料：["hug", "pug", "pun", "bun"]（每个词出现 1 次）
• 初始词汇表 $V_0$：{h, u, g, p, n, b, </w>} （</w> 表示词尾）
• 分词结果：[h, u, g, </w>], [p, u, g, </w>], [p, u, n, </w>], [b, u, n, </w>]

第一轮迭代

1. 统计频率与概率：
   • 总 Token 数 $N = 4 \times 4 = 16$
   • $P(u) = 4/16 = 0.25$, $P(g) = 2/16 = 0.125$, $P(n) = 2/16 = 0.125$
   • Pair (u, g) 出现 2 次，Pair (u, n) 出现 2 次。
2. 计算 PMI 与得分：
   • 对于 (u, g)：
     • $P(ug) = 2/16 = 0.125$
     • $\text{PMI}(u, g) = \log \frac{0.125}{0.25 \times 0.125} = \log 4 \approx 1.386$
     • WordPiece 得分：$2 \times 1.386 = \mathbf{2.772}$
   • 对于 (u, n)：
     • $P(un) = 2/16 = 0.125$
     • $\text{PMI}(u, n) = \log \frac{0.125}{0.25 \times 0.125} = \log 4 \approx 1.386$
     • WordPiece 得分：$2 \times 1.386 = \mathbf{2.772}$

   (注：在此简单例子中两者得分相同，假设我们按字母顺序优先选择 (u, g))

3. 执行合并：
   • 合并 u 和 g 为 ug。
   • 新词汇表 $V_1$：{h, u, g, p, n, b, </w>, ug}
4. 更新语料分词：
   • "hug" → [h, ug, </w>]
   • "pug" → [p, ug, </w>]
   • "pun" → [p, u, n, </w>] (未受影响)
   • "bun" → [b, u, n, </w>] (未受影响)

第二轮迭代

1. 重新统计：
   • 现在 u 的频率降低了（只剩 2 次），ug 的频率为 2 次。
   • 新的候选 pair 包括 (p, u), (p, ug), (h, ug) 等。
2. 计算得分：
   • 假设 (p, u) 的共现次数为 2，且 $P(p)$ 较低，其 PMI 可能会非常高。
   • WordPiece 会再次选择得分最高的 pair 进行合并。

最终效果对比

如果继续迭代，WordPiece 生成的词汇表可能包含：{h, p, b, ug, un, </w>}。

• “hug” 会被编码为：[h, ug, </w>]
• “pug” 会被编码为：[p, ug, </w>]
• “pun” 会被编码为：[p, un, </w>]

关键点：WordPiece 倾向于将 ug 和 un 这种在特定语境下（如跟在 p 后面）具有强预测性的组合合并在一起，而不仅仅是看谁出现得最多。

3.5 WordPiece 实例演示

假设我们有一个微型语料库，目标是构建一个小型词汇表。

初始状态：

• 语料：["hug", "pug", "pun", "bun"]（每个词出现 1 次）
• 初始词汇表 $V_0$：{h, u, g, p, n, b, </w>} （</w> 表示词尾）
• 分词结果：[h, u, g, </w>], [p, u, g, </w>], [p, u, n, </w>], [b, u, n, </w>]

第一轮迭代

1. 统计频率与概率：
   • 总 Token 数 $N = 4 \times 4 = 16$
   • $P(u) = 4/16 = 0.25$, $P(g) = 2/16 = 0.125$, $P(n) = 2/16 = 0.125$
   • Pair (u, g) 出现 2 次，Pair (u, n) 出现 2 次。
2. 计算 PMI 与得分：
   • 对于 (u, g)：
     • $P(ug) = 2/16 = 0.125$
     • $\text{PMI}(u, g) = \log \frac{0.125}{0.25 \times 0.125} = \log 4 \approx 1.386$
     • WordPiece 得分：$2 \times 1.386 = \mathbf{2.772}$
   • 对于 (u, n)：
     • $P(un) = 2/16 = 0.125$
     • $\text{PMI}(u, n) = \log \frac{0.125}{0.25 \times 0.125} = \log 4 \approx 1.386$
     • WordPiece 得分：$2 \times 1.386 = \mathbf{2.772}$

   (注：在此简单例子中两者得分相同，假设我们按字母顺序优先选择 (u, g))

3. 执行合并：
   • 合并 u 和 g 为 ug。
   • 新词汇表 $V_1$：{h, u, g, p, n, b, </w>, ug}
4. 更新语料分词：
   • "hug" → [h, ug, </w>]
   • "pug" → [p, ug, </w>]
   • "pun" → [p, u, n, </w>] (未受影响)
   • "bun" → [b, u, n, </w>] (未受影响)

第二轮迭代

1. 重新统计：
   • 现在 u 的频率降低了（只剩 2 次），ug 的频率为 2 次。
   • 新的候选 pair 包括 (p, u), (p, ug), (h, ug) 等。
2. 计算得分：
   • 假设 (p, u) 的共现次数为 2，且 $P(p)$ 较低，其 PMI 可能会非常高。
   • WordPiece 会再次选择得分最高的 pair 进行合并。

最终效果对比

如果继续迭代，WordPiece 生成的词汇表可能包含：{h, p, b, ug, un, </w>}。

• “hug” 会被编码为：[h, ug, </w>]
• “pug” 会被编码为：[p, ug, </w>]
• “pun” 会被编码为：[p, un, </w>]

关键点：WordPiece 倾向于将 ug 和 un 这种在特定语境下（如跟在 p 后面）具有强预测性的组合合并在一起，而不仅仅是看谁出现得最多。

4. SentencePiece 算法

代表模型：Llama, T5

4.1 核心定义

SentencePiece 是一个通用的、语言无关的子词分词框架。其核心创新在于摒弃了预分词 (Pre-tokenization) 步骤，将空格视为普通字符处理，从而实现了从原始字节流到 Token 的直接转换，以及从 Token 到原始文本的完全可逆还原。

4.2 与 BPE/WordPiece 的关键差异

4.3 两种底层算法模式

1. BPE 模式：逻辑与传统 BPE 一致，但输入是包含空格的原始字符串。
2. Unigram LM 模式（Llama 默认采用）：
   • 从一个大词汇表开始，迭代删除使语料库似然下降最小的 token。
   • 推理时使用 Viterbi 算法寻找最优子词序列，使得总概率最大。
   • 优势：对未登录词更鲁棒，同一个词在不同语境下可能有不同的分割方式。

5. 总结对比：三大主流分词算法

| 特性 | BPE (GPT) | WordPiece (BERT) | SentencePiece (Llama) |
| ———— | —————— | ———————— | ———————— |
| 合并标准 | 最高共现频率 | 最大似然增益 (PMI) | BPE 频率 或 Unigram 概率 |
| 空格处理 | 预分割 | 预分割/特殊标记 | 普通字符 (▁) |
| 子词标记 | 无 | ## | ▁ (前缀空格) |
| 主要优势 | 实现简单，生成流畅 | 适合语言建模，语义表达强 | 多语言通用，完全可逆 |

6. 分词器的意义

• 上下文窗口限制：大模型的上下文窗口是以Token数量计算的，不同分词器下，Token数量相差巨大。
• API成本：API是以Token数量计费的，了解分词器才能控制成本。
• 模型表现的异常：在设计提示词和解析模型时，要考虑query是否会被模型切分成易于理解的Token。