四大子词分词算法详解

四大子词分词算法详解

1. BPE (Byte Pair Encoding)

原理

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

训练过程

输入语料：

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

步骤：

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

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

2. 统计字符对频率：

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

3. 迭代合并：

第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"

步骤：

1. 初始化：l o w e s t </w>
2. 应用学到的合并规则（按训练时的顺序）：
   • 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字符。

训练过程

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

步骤：

1. 转换为字节：

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

2. 初始词表：256个字节值（0x00-0xFF）

3. 统计字节对频率并合并：
   假设在大规模语料中：

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

推理过程

输入："你好"

步骤：

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

输出：[257, 258]

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

3. WordPiece

原理

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

训练过程

输入语料（带频率）：

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

步骤：

1. 初始化：

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

2. 计算合并得分：

对于候选合并"un"：

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

假设计算结果：

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

3. 迭代合并：

第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"

步骤：贪心最大匹配

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

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

4. Unigram Language Model

原理

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

训练过程

输入语料：

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

步骤：

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

词表: {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, ...}

2. 计算每个token的概率：

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

3. 评估移除影响：

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

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

假设计算结果：

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

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

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

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

推理过程

输入："hello"

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

1. 列举所有可能的分词：

   • [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
   • …

2. 选择概率最大的分词：

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"](概率最高)

四种算法对比总结

实际应用示例

输入句子："preprocessing"

• BPE输出：["pre", "process", "ing"]
• WordPiece输出：["pre", "##process", "##ing"]
• Unigram输出：["pre", "processing"]或["prep", "ro", "cessing"]（取决于概率）
• BBPE输出：字节序列对应的token ID列表

希望这个详细的讲解能帮助你理解这四种分词算法！如果有任何疑问，欢迎继续提问。