从贪心匹配到动态规划：子词最优分割的工程实践

引言：贪心 BPE 的局限

在大型语言模型的预处理流水线中，分词器（Tokenizer）往往被视为一个 "黑盒" 组件。开发者通常直接使用预训练的 BPE（Byte-Pair Encoding）分词器，却很少关注其内部的分割策略。然而，传统的贪心 BPE 分割算法存在一个根本性问题：它采用局部最优的合并顺序，可能导致全局上并非最优的 token 序列。

以英语复合词 "policymakers" 为例，贪心 BPE 可能将其分割为 "p"、"olic"、"ym"、"akers" 四个 token，而最优分割应该是 "policy" 和 "makers"。这种次优分割不仅增加了序列长度（Transformer 的计算复杂度与序列长度呈平方关系），还可能破坏词法边界，影响模型对语义单元的学习。

研究表明，在形态丰富的语言（如土耳其语、芬兰语、印尼语）和低资源语言中，这种效率损失尤为明显。最优分割算法相比贪心策略可减少 3-5% 的 token 数量，在复杂词汇上压缩率甚至可达 20%。

最优分割的算法原理

问题定义

给定词汇表 V 和文档 d，分割任务 S (d) = {t₁, t₂, ..., tₖ} 的目标是将文档划分为来自 V 的 token 序列。最优分割 S * 定义为最小化 token 数量的分割方案：

S* = argminₛ |S(d)|

动态规划求解

最优分割问题可以通过动态规划在多项式时间内求解。定义 dp [i] 为分割前缀 d₀d₁...dᵢ所需的最少 token 数，递推关系为：

dp [i] = min₀≤ⱼ≤ᵢ (dp [j-1] + 1)，其中 dⱼdⱼ₊₁...dᵢ ∈ V

初始条件为 dp [-1] = 0。通过维护父指针数组 par [i] 记录最优分割点，可在 O (N・M) 时间内求解，其中 N 为文档长度，M 为词汇表中最长 token 长度。

Trie 结构优化

为了高效判断子串是否属于词汇表，算法在反向词汇表上构建 Trie 树。这种设计允许在 O (L) 时间内完成单次查找，其中 L 为匹配长度。值得注意的是，该算法的最坏时间复杂度 O (N・M) 与贪心 BPE 相同，空间复杂度也保持一致。

工程实现要点

Token Saving Ratio (TSR) 指标

为了量化评估分割质量，研究者提出了 TSR 指标：

TSR = (|S_B(d)| - |S_A(d)|) / |S_B(d)|

其中 S_B 为基线（贪心 BPE）分割结果，S_A 为待评估分割结果。TSR 为正表示 token 数量减少，直接对应更短的序列长度和更低的计算成本。

实现清单

在实际部署最优分割时，建议关注以下参数配置：

• 词汇表大小：50K、100K、200K 是常见选择，较大词汇表通常带来更高的 TSR
• 预处理缓存：由于动态规划计算量较大，建议对高频文本进行离线预处理并缓存
• 语言适配：优先在形态丰富的语言（土耳其语、芬兰语、印尼语等）上启用
• 回退策略：对于未匹配子串，保持字节级回退机制

实验验证与效果

多语言压缩效果

在 CC-100 数据集上的评估显示，最优分割在 116 种语言中均取得正 TSR。其中，奥罗莫语、斯瓦蒂语、克丘亚语等低资源语言的 TSR 超过 4.5%，即使在 200K 大词汇表下仍保持显著优势。

一个有趣的发现是：词长与 TSR 呈正相关。4 字符单词的 TSR 约为 0.15，而 11-12 字符单词的 TSR 可达 0.30。这意味着形态复杂的复合词和派生词从最优分割中获益最大。

下游任务提升

在 GPT-2 模型（120M 参数）上的实验表明，最优分割在下游任务中带来实质性提升：

• 印尼语 Emot 任务：准确率从 40.23% 提升至 44.55%（+4.32%）
• 印尼语 WreTe 任务：准确率从 76.00% 提升至 78.00%（+2.00%）
• 土耳其语 XNLI 任务：准确率从 64.35% 提升至 64.91%（+0.56%）
• 芬兰语 TyDiQA：准确率从 82.91% 提升至 83.76%（+0.85%）

值得注意的是，在仅包含贪心与最优分割存在差异的样本子集（TSR*）上，提升幅度更为显著，印尼语 Emot 任务在 TSR * 子集上提升达 5.64%。

英语性能保持

对于英语等形态简单的语言，最优分割不会带来性能退化。在 LAMBADA 数据集上的困惑度评估显示，最优分割与贪心 BPE 的差异微乎其微，证明该策略具有良好的跨语言兼容性。

落地建议与权衡

适用场景

最优分割特别适合以下场景：

1. 多语言模型：尤其是包含形态丰富语言的模型
2. 低资源语言：数据稀缺的语种对 token 效率更为敏感
3. 长文本处理：序列长度受限的应用场景
4. 小型模型：参数量较小的模型对表示效率要求更高

工程权衡

尽管最优分割带来显著收益，也需要考虑以下权衡：

• 预处理成本：动态规划计算量高于贪心算法，建议离线预处理
• 词汇表依赖：效果与词汇表质量强相关，需确保词汇表覆盖目标语言的常见词素
• 边际效益递减：对于英语等简单形态语言，改进幅度有限

结论与展望

从贪心匹配到动态规划最优分割，子词分词技术正在经历一场 "从局部到全局" 的范式转变。最优分割算法在不增加时间复杂度的情况下，显著提升了形态丰富语言的 token 效率，并在下游任务中展现出可观的性能提升。

对于工程实践者而言，最优分割提供了一种 "即插即用" 的优化方案：无需重新训练词汇表，仅需替换分割策略即可获益。随着多语言模型和低资源语言应用的普及，这一技术有望在更广泛的场景中发挥价值。

未来的研究方向包括探索自适应分词策略（根据输入动态选择分割方法）、结合子词正则化（Subword Regularization）进一步提升模型鲁棒性，以及将最优分割思想扩展到更大规模的基础模型（如 LLaMA-3）中。

参考资料

• Raj S B, et al. "When Every Token Counts: Optimal Segmentation for Low-Resource Language Models." arXiv:2412.06926, 2024.
• Kudo T. "Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation." ACL 2020.

ai-systems