什么是无监督分词算法（Byte Pair Encoding）？

无监督分词算法（Byte Pair Encoding，BPE）是一种子词切分（subword tokenization）方法，其思想源头是基于语法的文本压缩。它通过反复合并语料中出现频率最高的一对相邻符号，逐步构建出一个规模预先设定的词表（token dictionary），从而把任意文本切分成由词表内单元组成的序列。它要解决的问题是：在词表规模受限的前提下，如何自动地从原始文本中学习切分单元，而不依赖人工标注的分词边界。

为什么重要

在 BPE 这类方法被广泛采用之前，文本处理通常依赖按空格或标点切分的整词词表。这种做法有两个明显痛点：一是词表规模会随语料增长而迅速膨胀，二是遇到未登录词（如罕见词、拼写变体、形态丰富的语言中的屈折形式）时无法处理，只能退化为统一的未知词标记，丢失信息。

BPE 提供了一条折中路径：词表规模可以人为指定，常见词保持为整体单元，罕见词则被拆成更小的子词片段，从而在词表大小与覆盖率之间取得平衡。正因如此，它被用于机器翻译、大语言模型（LLM）预训练等多种语言处理任务。不过，正如 arXiv 论文《Theoretical Analysis of Byte-Pair Encoding》所指出的，迄今为止对 BPE 的大多数评价都是经验性的，其良好实际表现背后的原因并未被充分理解。

工作机制

BPE 的核心是一个迭代式的贪心合并过程，可以概括为以下要点：

初始化：把训练语料中的文本拆成最小单位（例如字符或字节）序列，此时词表就是这些最小单位。
统计相邻对：扫描当前序列，统计所有相邻符号对出现的频次。
合并最高频对：选出频次最高的那一对，把它合并成一个新的符号，并加入词表。
重复：用合并后的新符号替换序列中所有该对的出现，然后回到第 2 步，直到达到预设的合并次数或词表规模。

在表面上看，BPE 是一个贪心算法。ACL Anthology 收录的论文《A Formal Perspective on Byte-Pair Encoding》指出，BPE 所要解决的底层优化问题此前并未被明确写出，该论文将 BPE 形式化为一个组合优化问题，并借助子模函数（submodular functions）证明：迭代贪心版本是最优合并序列的一个 1/sigma*(1-e(-sigma)) 近似，其中 sigma 是相对于最优合并序列的总后向曲率（total backward curvature）；该论文报告近似下界的经验值约为 0.37。

同一篇论文还给出了一种更快的 BPE 实现，把运行时间复杂度从 O(NM) 改进为 O(N log M)，其中 N 是序列长度，M 是合并次数；此外，该论文用记忆化（memoization）优化了求解最优 BPE 的暴力算法。

arXiv 论文《Theoretical Analysis of Byte-Pair Encoding》则从另一角度切入：它关注 BPE 背后的优化问题，即寻找一种能达到最优压缩效用的对编码（pair encoding）。该论文证明这个问题是 APX-完全的（APX-complete），这意味着它不太可能存在多项式时间近似方案（PTAS）；这以更强的形式回答了 Zouhar 等人此前提出的一个问题。在正面结果方面，该论文证明 BPE 对最优对编码压缩效用的近似最坏情况倍数介于 0.333 与 0.625 之间，并称这是据其所知，首批对所有输入都成立的、关于 BPE 压缩效用的严格保证。

典型例子

根据 arXiv 论文《Theoretical Analysis of Byte-Pair Encoding》的描述，BPE 被用于机器翻译或大语言模型预训练等语言处理任务，用途是创建指定规模的词表。该论文的起源被描述为基于语法的文本压缩。

在理论侧，两篇论文给出了可直接引用的具体对象：ACL Anthology 论文《A Formal Perspective on Byte-Pair Encoding》由 Vilém Zouhar、Clara Meister、Juan Gastaldi、Li Du、Tim Vieira、Mrinmaya Sachan、Ryan Cotterell 撰写，发表于 Findings of the Association for Computational Linguistics: ACL 2023，页码 598–614，地点为加拿大多伦多。arXiv 论文《Theoretical Analysis of Byte-Pair Encoding》由 László Kozma 与 Johannes Voderholzer 撰写，提交于 2024 年 11 月 13 日，编号 arXiv:2411.08671，主题分类为数据结构与算法（cs.DS）以及计算与语言（cs.CL）。

边界与常见误解

第一，BPE 常被当作一个纯粹的工程技巧，而它其实对应一个明确的优化目标。ACL Anthology 论文明确指出，BPE 表面上像贪心算法，但其底层优化问题此前未被形式化；该论文的工作正是补上这一形式化。因此，把 BPE 的贪心合并等同于「最优切分」是一种误解。

第二，贪心合并并不保证最优。ACL Anthology 论文给出的是近似比结论，且该比值依赖总后向曲率 sigma；arXiv 论文则证明最优对编码问题是 APX-完全的，并给出 BPE 相对最优的近似倍数区间为 0.333 至 0.625。这些结论都来自相应论文，不应被推广为对任意实现、任意语料的性能承诺。

第三，关于运行效率的改进有明确前提。ACL Anthology 论文报告的 O(N log M) 复杂度是针对该论文所提出的更快实现，并与 O(NM) 的基线相对比，其中 N 为序列长度、M 为合并次数；这不等于所有 BPE 实现都具备该复杂度。

第四，BPE 的适用边界。它最初是为压缩而设计的，被借用到自然语言处理的分词任务中；素材并未声称它在所有语言或所有模态上都优于其他分词方案，也未给出跨任务的横向对比结论。此外，词表规模与合并次数是需要人为设定的超参数，其取值会影响切分粒度，这一点属于方法本身的设定，而非论文给出的最优取值建议。

All Categories