Tokenization Algorithm

1 BPE

Byte-Pair Encoding (BPE)，一种词表压缩算法，核心思想是合并频繁出现的字符对来创建新的词汇，逐步建立起一个子词的词表。

BPE算法的步骤：
- 将文本数据集中的词汇切分为基础字符（如字母、标点符号等），并为每个基础字符后加上终止符，以表示词的边界。
- 统计所有相邻字符对的频率，并找出出现次数最多的字符对。
- 将最频繁的字符对合并，创建一个新的符号，并且将文本中的这些字符对替换为这个新符号。
- 重复步骤3和步骤4，直到达到预定的词表大小或者没有可以合并的字符对为止。
应用场景：
- 通过字母级别的合并压缩，可以讲单词分割出前缀、后缀、时态、复数等常见的变化。这样，就能很好的压缩词汇表。最直观的例子就是 highest、lowest -> high、low、est，对比的是 high、highest、low、lowest
局限：
- 它过于关注频率最高的对，可能在语义边界上产生不合理的分割。
代码资源：

from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import Whitespace

# 创建一个基本的BPE模型
tokenizer = Tokenizer(BPE(unk_token="[UNK]"))

# 使用 Whitespace作为预处理器
tokenizer.pre_tokenizer = Whitespace()

# 创建一个 BPE trainer，设置vocab_size为5000
trainer = BpeTrainer(vocab_size=5000, special_tokens=["[UNK]", "[CLS]", "[SEP]", "[PAD]", "[MASK]"])

# 指定文件路径列表来训练tokenizer
files = ["your_text_file_1.txt", "your_text_file_2.txt"]
tokenizer.train(files, trainer)

# 保存tokenizer到文件
tokenizer.save("bpe.tokenizer.json")

1.1 Reference

自然语言处理之Subword子词算法 – 标点符
 ChatGPT 举例合并时态例子

2 BBPE

Chatgpt 2 使用
字节级别的合并

BPE的算法最开始的基础词表也可能会很大，比如如果将所有的unicode 字符都放入基础词表，一开始的词表大小就有十几万了。在GPT-2论文中使用了bytes作为基础词表，因此它就可以表示任意单词，并且其基础词表只有256的大小，再加上一个特殊的结束符号，使用50000大小的merge，最终GPT-2的词表大小为50257.（GPT-2在merge的时候还有一些特殊规则，比如不将不同类型的bytes合并等）

由于所有的字符都可以转换成字节序列，所以BBPE的词表中可以包含所有可能的单字节符号，这样就确保了模型不会出现任何未登录词，同时也可以有效地控制词表的规模。

BBPE的主要优点在于，它可以实现真正的无UNK处理，同时也能较好地处理多语言文本。因为它基于字节，所以可以很好地处理任何UTF-8编码的文本，无论这些文本是哪种语言，都不需要做任何特殊处理。

2.1 Reference

子词分词器BPE和WordPiece理解_wordpeice-CSDN博客
 自然语言处理之Subword子词算法 – 标点符

3 WordPiece

Bert 使用
初始化：每个单词最初通过在单词内的所有字符前添加前缀# 来分割例如：“word” 被分割为：

w ##o ##r ##d

合并的规则变化为：

s c o r e = \frac{f r e q o f p a i r}{f r e q o f f i r s t e l e m e n t \times f r e q o f s e c o n d e l e m e n t}

该规则认为合并后出现的频率越高，这个组合就越应该发生；合并前出现的频率越高，就越不该合并，这是合理的；

4 Unigram Language Model (ULM)

4.1 核心思想

Unigram Language Model 将分词视为概率问题：

一句文本可能有多种切分方式
给每个子词 $s_{i}$ 分配概率 $p (s_{i})$
一种切分方式的概率是所有子词概率的乘积
句子的概率是所有切分方式概率之和
使用 EM 算法训练子词概率
最终使用 Viterbi 寻找最优切分

模型会自然偏向“更能解释数据的子词”，如更长、更常用的子词。

4.2 模型定义

一个切分方式 $S = (s_{1}, s_{2}, . . ., s_{k})$ 的概率为：

$P (S) = \prod_{j} p (s_{j})$

句子 $X$ 的概率为：

$P (X) = \sum_{S \in all segmentations of X} P (S)$

目标：最大化整个训练语料的对数似然。

4.3 EM 训练流程

4.3.1 E 步：计算期望出现次数

对每个切分方式计算：

切分概率
切分在句子中的占比（后验概率）
子词在该切分中的出现次数

子词 $s_{i}$ 的期望出现次数：

$c_{i} = \sum_{segmentations} (seg posterior) \times (count of s_{i})$

4.3.2 M 步：更新子词概率

$p_{i} = \frac{c_{i}}{\sum_{j} c_{j}}$

4.3.3 剪枝

删除贡献低的子词（如删除 20%），重复 EM，直到词表收敛到目标大小。

4.4 完整例子（含 E 步和 M 步）

4.4.1 语料

abab

4.4.2 初始子词

a: 0.4
b: 0.4
ab: 0.2

4.4.3 所有可能切分及概率

切分	概率计算	概率
[a, b, a, b]	0.4 × 0.4 × 0.4 × 0.4	0.0256
[ab, a, b]	0.2 × 0.4 × 0.4	0.032
[a, b, ab]	0.4 × 0.4 × 0.2	0.032
[ab, ab]	0.2 × 0.2	0.04

总概率：

$P_{total} = 0.0256 + 0.032 + 0.032 + 0.04 = 0.1296$

4.4.4 各切分占比（后验概率）

切分	概率	占比
[a, b, a, b]	0.0256	0.1975
[ab, a, b]	0.032	0.2469
[a, b, ab]	0.032	0.2469
[ab, ab]	0.04	0.3086

占比 = 子切分概率 $/$ $P_{total}$ 。

4.4.5 期望出现次数（E 步）

4.4.5.1 c(a)

切分	占比	a 出现次数	贡献
[a, b, a, b]	0.1975	2	0.3951
[ab, a, b]	0.2469	1	0.2469
[a, b, ab]	0.2469	1	0.2469
[ab, ab]	0.3086	0	0

$c (a) = 0.8889$

4.4.5.2 c(b)

与 $a$ 对称：

$c (b) = 0.8889$

4.4.6 c(ab)

切分	占比	ab 出现次数	贡献
[a, b, a, b]	0	0	0
[ab, a, b]	1	0.2469
[a, b, ab]	1	0.2469
[ab, ab]	2	0.6173

$c (a b) = 1.1111$

4.4.7 更新概率（M 步）

总出现期望：

$sum = 0.8889 + 0.8889 + 1.1111 = 2.8889$

更新后：

$p (a) = 0.3077$
$p (b) = 0.3077$
$p (a b) = 0.3846$

模型提高了 ab 的概率 → 更偏向较长且更有效的子词。

4.5 总结

Unigram LM 用概率机制自动选择最优子词集合
句子概率 = 所有切分概率之和
EM 训练：
- E 步：期望出现次数
- M 步：概率归一化
定期剪枝以获得最优词表
分词时用 Viterbi 找最高概率切分

5 SentencePiece

核心要点：unicode 实现跨越语言、支持多种字词算法，端到端，不假设已经有了基本的字符集

SentencePiece 主要包含两个模型：

BPE（Byte-Pair Encoding）
Unigram Language Model
默认一般使用 Unigram。

#待研究数据驱动-SmilesPE