四大子词分词算法详解-平芜编程栈

四大子词分词算法详解

1. BPE (Byte Pair Encoding)

原理

BPE是最基础的子词分词算法，通过迭代地合并最频繁出现的字符对来构建词表。

训练过程

输入语料：

low: 5次 lower: 2次 newest: 6次 widest: 3次

步骤：

初始化：将每个单词拆分为字符，并在末尾添加特殊符号表示词尾

l o w </w>: 5 l o w e r </w>: 2 n e w e s t </w>: 6 w i d e s t </w>: 3

统计字符对频率：

“e” + “s”: 6+3=9次
“es” + “t”: 9次
“l” + “o”: 5+2=7次
“o” + “w”: 5+2=7次
等等…

迭代合并：

第1轮：合并最高频的"es" + “t” → “est”

l o w </w>: 5 l o w e r </w>: 2 n e w est </w>: 6 w i d est </w>: 3

第2轮：合并"est" + “” → “est”

l o w </w>: 5 l o w e r </w>: 2 n e w est</w>: 6 w i d est</w>: 3

第3轮：合并"l" + “o” → “lo”

lo w </w>: 5 lo w e r </w>: 2 n e w est</w>: 6 w i d est</w>: 3

持续迭代直到达到预设的词表大小或合并次数。

推理（分词）过程

输入："lowest"

步骤：

初始化：l o w e s t </w>
应用学到的合并规则（按训练时的顺序）：
- l o→lo：lo w e s t </w>
- e s→es：lo w es t </w>
- es t→est：lo w est </w>
- est </w>→est</w>：lo w est</w>

输出：["lo", "w", "est</w>"]

2. BBPE (Byte-level BPE)

原理

BBPE是BPE的字节级变体，直接在字节序列上操作，而不是字符。这使得它可以处理任何Unicode字符。

训练过程

输入：中文文本"你好世界"

步骤：

转换为字节：

你 → [0xE4, 0xBD, 0xA0] 好 → [0xE5, 0xA5, 0xBD] 世 → [0xE4, 0xB8, 0x96] 界 → [0xE7, 0x95, 0x8C]

初始词表：256个字节值（0x00-0xFF）
统计字节对频率并合并：
假设在大规模语料中：

[0xE4, 0xBD] 经常一起出现 → 合并为新token 256
[256, 0xA0] 经常一起出现 → 合并为新token 257（代表"你"）
以此类推…

推理过程

输入："你好"

步骤：

转字节：[0xE4, 0xBD, 0xA0, 0xE5, 0xA5, 0xBD]
应用合并规则：[257, 258]（假设257=“你”，258=“好”）

输出：[257, 258]

优势：可以处理任何语言，包括emoji、罕见字符，词表大小固定且可控。

3. WordPiece

原理

WordPiece与BPE类似，但合并准则不同。它选择能最大化训练数据似然的字符对进行合并。

训练过程

输入语料（带频率）：

unwanted: 100次 unwan: 50次 wanted: 200次

步骤：

初始化：

词表: [u, n, w, a, n, t, e, d, ##t, ##e, ##d] （##表示非词首的subword）

计算合并得分：

对于候选合并"un"：

得分 = log(P(un)) / (log(P(u)) + log(P(n)))

假设计算结果：

“un” 得分: 0.85
“wa” 得分: 0.72
“te” 得分: 0.91 ← 最高
“ed” 得分: 0.88

迭代合并：

第1轮：选择"te"合并

词表添加: [te] unwanted → un wan te d wanted → wan te d

第2轮：选择"ed"合并

词表添加: [ed] unwanted → un wan te d wanted → wan ted

第3轮：选择"un"合并

词表添加: [un] unwanted → un wan ted unwan → un wan

推理过程

输入："unwanted"

步骤：贪心最大匹配

从左到右，尝试匹配最长的词表中的token
"unwanted"→ 尝试整个词（不在）→ 尝试"unwante"（不在）→ … → 找到"un"
剩余"wanted" → 找到"wan" → 剩余"ted" → 找到"ted"

输出：["un", "##wan", "##ted"]

4. Unigram Language Model

原理

Unigram采用自上而下的方法，从一个大词表开始，逐步删除对损失函数影响最小的token。

训练过程

输入语料：

"hello": 10次 "world": 8次 "help": 5次

步骤：

初始化大词表（包含所有可能的子串）：

词表: {h:15, e:15, l:25, o:10, w:8, r:8, d:8, p:5, he:15, el:15, ll:15, lo:10, hel:15, ell:15, hello:10, help:5, wor:8,orld:8, world:8, ...}

计算每个token的概率：

P(token) = count(token) / total_chars P(hello) = 10/总字符数

评估移除影响：

对每个token，计算移除后的损失增加：

ΔLoss(token) = -Σ log P(语料能否用剩余词表表示)

假设计算结果：

移除"hel": ΔLoss = 0.02（影响小）
移除"hello": ΔLoss = 2.5（影响大）
移除"p": ΔLoss = 0.8（中等）

迭代删除：
每轮删除影响最小的10-20%的token，直到达到目标词表大小。

第1轮删除：移除"hel", "ell"等低影响token

剩余词表: {h, e, l, o, w, r, d, p, he, ll, lo, hello, help, wor, world, ...}

推理过程

输入："hello"

步骤：使用Viterbi算法找最优分词

列举所有可能的分词：
- [hello]: P = P(hello) = 0.15
- [he, llo]: P = P(he) × P(llo) = 0.08 × 0.05 = 0.004
- [hel, lo]: P = P(hel) × P(lo) = 0.09 × 0.06 = 0.0054
- [h, e, l, l, o]: P = 0.05^5 = 0.0000003125
- …
选择概率最大的分词：

max{0.15, 0.004, 0.0054, ...} = 0.15

输出：["hello"]

复杂示例输入："helping"

可能的分词及其概率：

[help, ##ing]: P = 0.08 × 0.12 = 0.0096
[hel, ##p, ##ing]: P = 0.05 × 0.03 × 0.12 = 0.00018
[he, ##lp, ##ing]: P = 0.08 × 0.04 × 0.12 = 0.00384

输出：["help", "##ing"](概率最高)

四种算法对比总结

算法	方向	合并准则	优点	代表模型
BPE	自底向上	频率最高	简单高效	GPT-2
BBPE	自底向上	频率最高(字节级)	多语言友好	GPT-3, LLaMA
WordPiece	自底向上	似然最大	更优的概率模型	BERT
Unigram	自顶向下	损失最小	多种分词，可计算概率	T5, XLNet