BPE 算法原理

BPE 把一个 1994 年的数据压缩技巧搬进 NLP：用语料自身的共现频率归纳出一组有序 merge 规则，让词表在「字符太碎」与「整词太稀」之间自动找到落点。理解 BPE 的关键不是词表，而是 merge 的顺序。

从压缩算法到子词切分

Byte Pair Encoding 原本是 Philip Gage 提出的压缩方法：反复把出现最频繁的相邻字节对替换成一个未使用的新字节，用一张替换表换取更短的码流。Sennrich 等人在 2016 年的 NMT 工作中做了一次关键改写——不再追求还原压缩，而是保留那张替换表本身作为词表。新符号不回填，而是层层叠加成子词单元。

这次迁移解决的是翻译系统的 OOV 问题。固定词表遇到未登录词只能吐 <unk>，而 BPE 的底座是全部单字符，任何字符串都能被切开，同时高频词仍然保持整词粒度。这个「字符兜底 + 高频合并」的骨架，成为后续所有子词方案的共同起点，参见 Tokenizer 概述对整条编解码管线的定位。

训练：merge 规则的贪心归纳

训练输入是语料折叠后的 word → frequency 字典，而非原始文本流；每个词初始切成字符序列，并附一个词尾标记（</w> 或 ▁）以区分 est 出现在词中还是词尾。

循环直到词表达到目标大小：

统计所有相邻 symbol pair 的加权频次（权重为所在词的词频）
取频次最高的 pair，频次相同时按确定性规则打破平局（首次出现顺序或字典序）
把该 pair 记入 merge 列表，在所有词中就地替换为合并后的新 symbol

产物是两样东西：词表（字符底座 + 所有合并产物）和有序 merge 列表。后者是编码阶段的唯一依据，顺序即优先级。

手推示例

语料 low×5, lower×2, newest×6, widest×3：

轮次	最高频 pair	频次	新 symbol
1	(e, s)	9	`es`
2	(es, t)	9	`est`
3	(est, `</w>`)	9	`est</w>`
4	(l, o)	7	`lo`
5	(lo, w)	7	`low`

第 3 轮把词尾标记吸收进 est</w>，于是「作为词尾后缀的 est」与「词内的 est」分化成两个 token——这正是词尾标记存在的意义。五轮之后 newest 的表示从 7 个字符降到 n e w est</w> 共 4 个 symbol。

参考实现

from collections import Counter
 
def train_bpe(word_freq: dict[str, int], num_merges: int):
    # 每个词切成字符元组，末尾追加词尾标记
    corpus = {tuple(w) + ("</w>",): f for w, f in word_freq.items()}
    merges = []
    for _ in range(num_merges):
        pairs = Counter()
        for symbols, freq in corpus.items():
            for pair in zip(symbols, symbols[1:]):
                pairs[pair] += freq          # 按词频加权，而非按出现次数
        if not pairs:
            break
        best = max(pairs, key=pairs.get)  # Counter 保插入序，平局取首次出现的 pair
        merges.append(best)
        corpus = {_apply(s, best): f for s, f in corpus.items()}
    return merges
 
def _apply(symbols: tuple, pair: tuple) -> tuple:
    out, i = [], 0
    while i < len(symbols):
        # 命中目标 pair 则合并并跳过两个位置，否则原样保留
        if i < len(symbols) - 1 and (symbols[i], symbols[i + 1]) == pair:
            out.append(symbols[i] + symbols[i + 1])
            i += 2
        else:
            out.append(symbols[i])
            i += 1
    return tuple(out)

编码：按 rank 重放，而非最长匹配

最常见的误解是「BPE 编码 = 在词表里做贪心最长匹配」。真正的 BPE 编码是重放训练时的 merge 顺序：把词切成字符，反复找出当前序列中 rank 最小（即训练中最早学到）的可用 pair 并合并，直到无 pair 可合。

def encode(word: str, merges: list[tuple]) -> list[str]:
    rank = {p: i for i, p in enumerate(merges)}
    symbols = list(word) + ["</w>"]
    while len(symbols) > 1:
        # 在所有相邻 pair 中选 rank 最小者——顺序决定结果
        cand = min(zip(symbols, symbols[1:]), key=lambda p: rank.get(p, float("inf")))
        if cand not in rank:
            break
        symbols = list(_apply(tuple(symbols), cand))
    return symbols

用上表的 merge 列表编码 lowest：(e,s)→es、(es,t)→est、(est,</w>)→est</w>、(l,o)→lo、(lo,w)→low，输出 low | est</w>。训练中未见的词也能切开，因为字符底座永远兜得住。

两种策略何时分叉：若词表同时含 ab、abc，而 (a,b) 的 rank 早于生成 abc 的那条规则，输入 abc 会先合出 ab，随后因缺少 (ab,c) 规则而停在 ab | c；最长匹配则直接输出 abc。最长匹配是 WordPiece 与 Unigram LM 中 WordPiece 的做法，二者不可混用——用错策略等于换了一个 tokenizer，embedding 查表全盘错位。

复杂度

阶段	朴素实现	工程实现
训练	每轮全量统计 pair， $V$ 轮共 $O (N \cdot V)$	pair 位置倒排索引 + 最大堆，每次 merge 只更新受影响的词，摊还接近 $O (W lo g W)$ （ $W$ 为唯一词数）
编码	每步扫 $O (n)$ 个 pair 取最小 rank，最多 $n - 1$ 步， $O (n^{2})$	双向链表 + 优先队列降到 $O (n lo g n)$ ；更实用的是 pre-tokenization 把 $n$ 压到单词长度，再加结果缓存

GPT-2 的 bpe() 至今是 $O (n^{2})$ 实现，靠正则预切分与 LRU cache 把实际开销掩盖掉；Tiktoken 则用 Rust 重写核心循环，常数级优化带来数量级吞吐提升。

边界与局限

词尾标记方案决定行为差异：subword-nmt 用后缀 </w>，SentencePiece 用前缀 ▁ 并把空格当普通字符，可无损还原原文
pre-tokenization 依赖：经典 BPE 先按空白切词，这让它在中日韩等无空格语言上退化，需要正则或语言无关方案接管
字符底座仍会 OOV：Unicode 罕见字符若未进入训练语料就无处可切，BBPE 字节级分词改用 256 个字节作底座彻底消除这一漏洞
纯频率驱动缺少概率解释：merge 是局部贪心，无全局似然目标，也无法为同一字符串给出多种切分的概率分布
词表大小是超参：merge 轮数直接等于新增 token 数，取值权衡见词表设计与裁剪

知识花园

探索