Tokenization：子词切分的数学体系

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

1.1 词级切分的问题

词级（Word-level）切分将文本分割为单词集合：

词表大小受语料库词汇量限制
未登录词（OOV）无法处理
多语言场景下词表膨胀

数学表示：

设词表为，单词。对句子，词级切分要求。

当遇到新词时，系统必须返回 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”）

目标：

将开放词表问题变成有限词表问题
保持合理的序列长度
保留子词的语义可解释性

二、BPE（Byte Pair Encoding）

2.1 算法起源与核心思想

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

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

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

核心思想：

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

2.2 算法的数学形式化

定义（字符序列）：

设语料库为，其中每个样本是字符序列。

定义（BPE 合并操作）：

给定字符序列，定义所有相邻对（pair）为：

定义（合并频率）：

对于每个 pair ，定义其在语料库中的出现频率：

其中是 pair 在序列中出现的次数。

2.3 BPE 算法步骤

Algorithm: BPE Tokenization

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

预处理：

将每个词拆分为字符序列
统计所有字符级别的 pair 频率
现代大模型规范：使用前缀空格符 Ġ 替代老式 </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

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

2.4 BPE 的编码与解码

编码（Tokenization）：

给定词，编码过程：

初始化：
如果词不在词表中，重复以下直到所有片段都在词表中：
- 从右向左找到最长的、在词表中的子词（工业界标准 BPE 编码方向）
- 如果找不到，替换为 UNK
返回子词序列

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

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）：

给定子词序列：

去掉所有标记
直接拼接相邻子词
返回拼接结果

注意：解码需要正确处理空格。例如：

子词序列 [“Ġthe”, “Ġcat”] 解码为 ” the cat”
Ġ 表示空格

2.5 BPE 的数学性质

性质（词表大小控制）：

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

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

性质（OOV 处理）：

对于未登录词，编码过程保证：

如果可以完全分解为词表中的子词，则编码成功
否则，包含 UNK token

性质（子词共享）：

设两个词和共享一个子词单元，则在编码表示中：

其中是词编码后的子词索引序列。

2.6 BPE 的变种与改进

Faster BPE（基于 Trie 树）：

使用 Trie 树存储词表，可以查找子词：

节点表示字符
边表示子词片段
时间复杂度从降到

BPE-Dropout：

在编码时随机跳过合并操作：

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

三、SentencePiece

3.1 设计动机

BPE 的问题：

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

SentencePiece 的核心思想：

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

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

3.2 算法描述

Algorithm: SentencePiece Training

输入：

原始语料库（未分词的文本）
目标词表大小
字符归一化配置（Unicode NFC/NFD）

预处理：

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

训练：与标准 BPE 完全相同

解码：

将 ▁ 替换为空格
拼接子词
逆标准化

3.3 与标准 BPE 的关键区别

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

3.4 归一化与逆标准化

Unicode 归一化：

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

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

逆标准化：

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

3.5 子词平滑与置信度

定义（子词置信度）：

对于编码后的子词序列，定义子词置信度：

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

应用：

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

四、WordPiece

4.1 算法起源与与 BPE 的区别

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

与 BPE 的关键区别：

维度	BPE	WordPiece
选择合并的依据	最高频率的 pair	最大似然的 pair
合并判据
编码策略	Longest-match-first	同样使用 Longest-match-first
语言学偏好	无	可能倾向于有语言学意义的切分

4.2 WordPiece 的数学推导

核心思想：

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

设语料库为，词可以被切分为子词序列。

定义（词的似然）：

其中是子词在语料库中的（归一化）频率。

定义（合并得分）：

对于候选 pair ，定义合并得分：

推导：

考虑将和合并为。合并后的似然变化为：

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

等价的频率解释：

部分实现使用频率近似替代对数似然比：

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

4.3 WordPiece 算法步骤

Algorithm: WordPiece Training

输入：语料库，目标词表大小

预处理：

将每个词初始化为字符序列
统计所有子词（包括字符）的频率

迭代：

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

4.4 编码算法

Algorithm: WordPiece Encoding

输入：词，词表

初始化：

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

贪心切分：

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

与 BPE 的细微区别：

WordPiece 的编码更严格地依赖词表。在 BERT 实现中：

使用 [UNK] token 表示单个未知字符
如果整个词都无法编码，也使用 [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 编码在最坏情况下是的。

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

使用 Trie 树（或者 BERT 使用的改进版）实现编码：

构建 Trie 树，节点是字符，边是子词
从根节点开始，贪心地寻找最长匹配
每一步查找是，总复杂度

字典树实现的关键操作：

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
合并依据	频率	频率（同 BPE）	似然
核心公式
输入格式	预分词文本	原始文本	预分词文本
语言依赖	需要分词器	语言无关	需要分词器

5.2 词表大小对性能的影响

词表大小与 OOV 率的关系：

设语料库中词的频率分布为，词表大小为。定义截断分布：

OOV 率：

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

对于大规模英文语料：

：覆盖率约 85-90%
：覆盖率约 95-98%
：覆盖率约 98-99%

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

5.3 子词切分的质量指标

定义（子词信息熵）：

对于子词序列，定义其信息熵：

其中是子词在词表中的（归一化）频率。

定义（子词完整性）：

对于词，定义子词完整性：

其中是切分后所有子词的总长度（字符数），是原词长度。比值越大代表切分越零碎（与原文相反）。

澄清：子词信息熵仅用于衡量词表整体分布均衡性，不能直接用于评判单条文本分词质量。

5.4 训练中的常见问题

问题 1：词表大小选择

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

解决方案：

从 10K 开始，逐步增大到 50K，观察 OOV 率和序列长度
选择使最小的

问题 2：特殊字符处理

解决方案：

统一 Unicode 归一化（NFKC）
处理控制字符和格式字符
对于中文字符，通常按单个字符处理

问题 3：训练语料偏置

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

解决方案：

下采样高频词
使用分层采样

六、数学公式速查

6.1 BPE 核心公式

Pair 频率：

词表大小：

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

6.2 WordPiece 核心公式

合并得分：

6.3 性能指标

OOV 率：

子词信息熵：

七、总结

三种 Tokenizer 的定位：

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

核心洞察：

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

工程实践要点：

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

延伸阅读：

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

Huajishe Notes

Explorer

1-Tokenization：子词切分的数学体系

Tokenization：子词切分的数学体系

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

1.1 词级切分的问题

1.2 字符级切分的问题

1.3 子词切分的核心思想

二、BPE（Byte Pair Encoding）

2.1 算法起源与核心思想

2.2 算法的数学形式化

2.3 BPE 算法步骤

2.4 BPE 的编码与解码

2.5 BPE 的数学性质

2.6 BPE 的变种与改进

三、SentencePiece

3.1 设计动机

3.2 算法描述

3.3 与标准 BPE 的关键区别

3.4 归一化与逆标准化

3.5 子词平滑与置信度

四、WordPiece

4.1 算法起源与与 BPE 的区别

4.2 WordPiece 的数学推导

4.3 WordPiece 算法步骤

4.4 编码算法

4.5 BERT 中的 WordPiece 实现

4.6 线性时间实现

五、三种 Tokenizer 的对比与实践

5.1 数学对比

5.2 词表大小对性能的影响

5.3 子词切分的质量指标

5.4 训练中的常见问题

六、数学公式速查

6.1 BPE 核心公式

6.2 WordPiece 核心公式

6.3 性能指标

七、总结

Graph View

Table of Contents