BPE 的基本原理

大语言模型不直接处理文本，无论中文还是英文，输入都会先被转化为 token 序列，后续的计算都是基于 token 进行的。前段时间中文圈子里讨论过给 token 起中文名，后来有人叫它“词元”，还挺形象的。在大语言模型中，token 就是文本中最基本的单元。

把文本转化为 token 的过程叫 tokenize，是大语言模型的第一步。本文介绍一种 tokenize 的实现方法——Byte Pair Encoding（BPE）。目前主流的大语言模型基本都在用 BPE，下面讲讲它的原理，再用 Python 实现一个简化版。

什么是 Token？

大语言模型处理自然语言的基本单位不是汉字或单词，是 token。这也是为什么人们常说自己最近一个月消耗了多少 token，而不是多少字或多少单词。

训练模型之前，开发者先从海量文本中统计高频词语，建一张词表，每个条目是一个 token。假如构建了如下词表：

输入文本”众里寻他千百度”，拆成“众里”、“寻他”、“千”、“百度”，查词表得到 token 序列 [100, 201, 302, 403]，模型实际的输入就是这个序列。

模型输出也是编号序列，返回给用户之前要查词表还原成文字。比如输出 [302, 403]，查表对应 [“千”，“百度”]，转成文本“千百度”交给用户。

以上是 token 的基本概念和 tokenize 的大致思路。实际操作还有很多问题要解决：怎么找到这些词语？词表该多大？

Tokenize 的挑战

实际操作中，我们会面临以下几个挑战：

1. 如何分词？

中文每个字之间没有空格，可以把每个汉字当一个 token，但这样每个 token 携带的含义太少。要用词语作为 token，就得把文本切分成词。中文句子的断句涉及词语边界的识别和歧义处理，是个麻烦事。

2. 词表规模如何控制？

中文常用汉字几千个，词语却有几十万；英文单词加上各种变形，数量同样庞大。词表太大管理困难，太小又不够用。需要在词表大小和 token 信息量之间找平衡。

3. 如何处理未遇见过的词？

不管中文英文，都有很多不常见的词，甚至是新造的。如果只把常见词语放进词表，遇到没见过的词就处理不了。

BPE (Byte Pair Encoding) 算法

BPE 巧妙地解决了前文提出的几个挑战。目前主流的大语言模型基本都用 BPE 做 tokenize。核心思路：从字节开始，逐步合并频率最高的相邻单位，形成新 token，直到词表达到预设规模。下面结合例子来说。

人类语言由各种符号组成：字母、数字、汉字、标点。Unicode 是一套全球通用的字符编码标准，给世界上几乎所有字符分配唯一的数字编号（码点），这样在全球任何地方，同一个符号就有相同的编号，这彻底解决了因过去编码标准冲突而导致的乱码问题。比如 'A' 的编号是 65，'你' 的编号是 20320。

因为有些字符出现的频率比较高，而有些字符极少使用。因此在计算机中存储这些字符时，使用固定长度的编码会浪费空间。UTF-8 是一种可变长度的编码方式，它根据字符的码点范围使用不同数量的字节来表示，从而在保证兼容性的同时提高了存储效率。

下面是 UTF-8 编码的一般规则：

比如 'A' 的码点是 65，属于单字节范围，UTF-8 编码就是 0x41；“你” 的码点是 20320，属于三字节范围，编码为 0xE4 0xBD 0xA0。所以“你好”在内存里是 [0xE4, 0xBD, 0xA0, 0xE5, 0xA5, 0xBD] 这 6 个字节。

BPE 的做法：不管中文英文，一律按字节处理。一个字节有 256 种取值，每种取值就是一个基本符号，任意文本都能表示为这 256 个符号的序列。“你好”在 BPE 眼里就是 6 个符号。

256 个字节符号当词表当然不够。办法是把符号组合起来——就像几千个汉字能拼出几十万个词语一样。BPE 在字节序列里找高频出现的相邻组合，把它们合并成新 token，控制词表规模，比如保留频率最高的 50000 个。

这么做还有个好处：能表示任意文本。常见单词整个作为一个 token，不常见的可以拆成更小的已知单元。比如 “university” 不在词表里，可以拆成 “uni” 和 “versity” 两个子词 token。

BPE 的训练过程

BPE 算法本身很简单：反复找出文本中出现频率最高的相邻字节对，合并成新 token，词表随之扩大。

以单词 “teacher” 为例。初始状态下，token 序列为 [t, e, a, c, h, e, r]。假设训练过程中依次执行以下合并：

最初 [t, e, a, c, h, e, r] 经过 6 次合并变成 [teacher]，过程中产生了 6 个新 token（ch, er, te, tea, cher, teacher）和 6 条合并规则。

训练完成后，手里有两样东西：一个词表，和一系列合并规则。

合并规则的顺序是很重要的，不能打乱顺序。因为在合并过程中，首先会合并最高频的字节序列。比如有两条合并规则:

1. [t, e] -> [te]
2. [e, r] -> [er]

对于 "term"，如果先应用 [t, e] -> [te]，term 会变成 [te, r, m]；但如果先应用 [e, r] -> [er]，term 会变成 [t, er, m]。

使用 BPE 来编码文本

编码（encode）就是把输入文本转成字节序列，再按规则列表的顺序逐条应用合并。

以 "researcher" 为例，初始 token 序列是 [r, e, s, e, a, r, c, h, e, r]。按训练时学到的规则依次合并：

最终得到 [r, e, s, e, a, r, cher]。"researcher" 不在词表里，但被拆成了已知 token 序列，其中 "cher" 包含了足够信息——模型可以通过它理解 "researcher" 大概率是个表示职业的词。

BPE 的代码实现

下面用 Python 写一个简化版的 BPE。先看训练过程：

def train_bpe(text, vocab_size):
    """训练 BPE 分词器，返回词表和合并规则"""

    # 将文本转化成字节序列
    ids = list(text.encode("utf-8"))

    # 词表：int -> bytes，初始 256 个字节各占一个 token
    vocab = {idx: bytes([idx]) for idx in range(256)}

    # 记录每次合并的 token pair 和新产生的 token
    merges = [] # (pair, new_token_id)

    # 不断合并频率最高的字节对，直到达到指定的词表大小
    for _ in range(vocab_size - 256):
        # 统计所有相邻 token 对的频次
        counts = Counter(zip(ids, ids[1:]))
        # 找出频率最高的 pair
        pair, _ = counts.most_common(1)[0]   # pair, freq

        # 将该 pair 合并为一个新 token，加入词表
        new_id = len(vocab)
        vocab[new_id] = vocab[pair[0]] + vocab[pair[1]]

        # 添加一条合并规则
        merges.append((pair, new_id))

        # 将 ids 中所有相邻的 pair 合并为 new_id
        ids = merge(ids, pair, new_id)

    return vocab, merges

merge 函数把序列中所有相邻的指定 pair 合并成新 token：

from collections import Counter

def merge(ids, pair, new_id):
    """将 ids 中所有相邻的 pair 合并为 new_id"""
    new_ids = []
    i = 0
    while i < len(ids):
        if i < len(ids) - 1 and (ids[i], ids[i + 1]) == pair:
            # 找到了匹配的 pair，合并成 new_id
            new_ids.append(new_id)
            i += 2
        else:
            # 没有匹配，保留原 token
            new_ids.append(ids[i])
            i += 1
    return new_ids

训练后会得到两样东西，一个是词表，还有一个是合并规则。有了词表和合并规则，就可以编码和解码了：

编码就是将用户输入的文本转成 token 的过程，实现逻辑如下：

def encode(text, vocab, merges):
    """按训练时学到的合并规则，将文本编码为 token id 序列"""
    
    # 将文本转化成字节序列
    ids = list(text.encode("utf-8"))
    
    # 依次应用合并规则
    for pair, new_id in merges:
        ids = merge(ids, pair, new_id)
    
    return ids

编码的实现逻辑很简单，就是先将文本转成字节序列，再对这些字节序列逐条应用合并规则。

解码则是将 token 序列转换为文本的过程。解码的实现很简单，就是用 token 在词表中找到对应的字节序列，将所有字节序列拼接起来，而后转化为文本。其实现代码如下：

def decode(ids, vocab):
    """将 token id 序列解码回文本"""

    # 使用词表，将 token 转为字节序列，然后将字节序列解码为 UTF-8 编码的文本
    return b"".join(vocab[idx] for idx in ids).decode("utf-8")

可以使用以下代码验证以上函数：

text = open('./bpe.md', 'r', encoding='utf-8').read()
vocab, merges = train_bpe(text, 400)

tokens = encode(text, vocab, merges)
print("Encoded:", tokens)

decoded = decode(tokens, vocab)
print("Decoded:", decoded)

assert text == decoded, "解码结果与原文本不一致！"

Tokenizer 的实现

上面我已经讲了 BPE 算法的原理，而 BPE 只是 tokenize 中的一个环节。一个完整的 tokenizer 还需要处理文本的预处理、文本的预切分、增加特殊 token 等等细节。每一个大模型发布的时候，都会附带一个 tokenizer.json 的配置文件，里面会详细描述 tokenize 的实现细节。

下面是一个典型的 tokenizer 配置文件的示例：

{
  "version": "1.0",
  "truncation": null,
  "padding": null,
  "added_tokens": [
    {
      "id": 248044,
      "content": "<|endoftext|>",
      "single_word": false,
      "lstrip": false,
      "rstrip": false,
      "normalized": false,
      "special": true
    },
    {
      "id": 248045,
      "content": "<|im_start|>",
      "single_word": false,
      "lstrip": false,
      "rstrip": false,
      "normalized": false,
      "special": true
    },
    {
      "id": 248046,
      "content": "<|im_end|>",
      "single_word": false,
      "lstrip": false,
      "rstrip": false,
      "normalized": false,
      "special": true
    },
    // ... (more added tokens)
  ],
  "normalizer": {
    "type": "NFC"
  },
  "pre_tokenizer": {
    "type": "Sequence",
    "pretokenizers": [
      {
        "type": "Split",
        "pattern": {
          "Regex": "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\\r\\n\\p{L}\\p{N}]?[\\p{L}\\p{M}]+|\\p{N}| ?[^\\s\\p{L}\\p{M}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"
        },
        "behavior": "Isolated",
        "invert": false
      },
      {
        "type": "ByteLevel",
        "add_prefix_space": false,
        "trim_offsets": false,
        "use_regex": false
      }
    ]
  },
  "post_processor": {
    "type": "ByteLevel",
    "add_prefix_space": false,
    "trim_offsets": false,
    "use_regex": false
  },
  "decoder": {
    "type": "ByteLevel",
    "add_prefix_space": false,
    "trim_offsets": false,
    "use_regex": false
  },
  "model": {
    "type": "BPE",
    "dropout": null,
    "unk_token": null,
    "continuing_subword_prefix": "",
    "end_of_word_suffix": "",
    "fuse_unk": false,
    "byte_fallback": false,
    "ignore_merges": false,
    "vocab": {
      "!": 0,
      "\"": 1,
      "#": 2,
      "$": 3,
      "%": 4,
      "&": 5,
      "'": 6,
      "(": 7,
      ")": 8,
      "*": 9,
      "+": 10,
      ",": 11,
      "-": 12,
      ".": 13,
      "/": 14,
      "0": 15,
      "1": 16,
      "2": 17,
      "3": 18,
      // ... (more vocab items)
    },
    "merges": [
      "Ġ Ġ",
      "ĠĠ ĠĠ",
      "i n",
      "Ġ t",
      "ĠĠĠĠ ĠĠĠĠ",
      "e r",
      "ĠĠ Ġ",
      "o n",
      "Ġ a",
      "r e",
      "a t",
      "s t",
      "e n",
      "o r",
      "Ġt h",
      "Ċ Ċ",
      "Ġ c",
      "l e",
      "Ġ s",
      "i t",
      "a n",
      "a r",
      "a l",
      "Ġth e",
      // ... (more merges)
    ]
  }
}

对于用户输入的文本，tokenize 的过程大致如下：

1. 预处理：对输入文本进行一些基本的清洗和规范化，比如大小写转换、去除多余空格、统一标点符号、去除 café 里的重音符号等等。
2. 预切分：把文本切分成更小的单元，比如按空格切分，或使用正则表达式匹配目标单元。典型的例子就是英文文本按空格切分成单词，中文文本逐字切分成汉字。
3. BPE 编码：根据训练好的 BPE 模型，把预切分后的文本转化为 token 序列。
4. 后处理：在 token 序列里增加一些特殊 token，比如 Bert 使用的 [CLS]、[SEP]、[PAD] 等等。

关于 tokenizer.json 文件里各个字段的含义，可以参考 HuggingFace 的文档 Tokenizers，不过我认为对大多数人而言，不需要关注太多细节。

前文的 Python 实现中，BPE 作用于整个输入文本，但实际工程实现中，BPE 是作用于切分后的单词上的。主流的实现中，会把空格保留在单词的前面，作为单词的一部分。比如句子 "I say hello"，会被切分成 ["I", " say", " hello"]。对于 " hello"，BPE 可能会把它切分成 " he" 和 "llo" 两个 token。" he" 前面有一个空格，这意味着它是一个单词的开始，而 "llo" 没有空格，表示它是某个单词的后半部分。所以把空格保留在单词前面，可以给模型提供单词的边界信息，帮助模型更好地理解文本结构。

特殊符号 Ġ

观察前面 JSON 中的 vocab 和 merges 部分，其中常常出现 Ġ 这个特殊符号。它是 ByteLevel PreTokenizer 的一个特征，表示空格。比如 "Ġt" 表示 " t"，"Ġthe" 表示 " the"。这里的原因是因为词表需要存储在 JSON 文件里，而 JSON 只能存储字符串。

BPE 的词表是一个 JSON 文件，每个 token 都是字符串形式：

{
  "vocab": {
    "Ġthe": 262,
    "Ġhello": 24288,
    "Ġ ": 220,
    ...
  }
}

问题在于：不是所有字节都能安全地存为字符串。

所以 GPT-2 做了一个映射：

• 可打印字节 (0x21-0x7E, 0xA1-0xAC, 0xAE-0xFF)： 保持不变，映射到自己
• 不可打印字节 (其余 133 个)： 增加一个偏移量 256，映射到 U+0100 到 U+017F 的 Unicode 字符

按照这个映射，空格就被映射成了 U+0100（Ġ），而其他不可打印字节也都有了合法的 Unicode 替身。

这样所有 256 个字节都变成了合法、可打印、无歧义的 Unicode 字符，可以安全存入 JSON。在 BPE 的视角中，不存在 到 Ġ 的映射，这里映射只发生在往 JSON 存储的过程中。

在词表中会看到下面这样的 token：

{
    "åĴĮé«ĺ": 111420,
    "äºĭåħĪ": 111421,
    "åĪĨæīĭ": 111422,
    "åĪĨ辨çİĩ": 111423,
    "æİĮæݧ": 111424,
    "å°ıæŶåĨħ": 111425,
}

因为我们知道，比如说一个汉字，它可以是由三个字节表示的。比如“你”这个字，在 UTF-8 中是 0xE4 0xBD 0xA0，按照 GPT-2 的映射，这三个字节分别被映射成了 U+00E4（ä）、U+00BD（½） 和 U+00A0（ł）。所以“你”在 JOSN 文件中就被表示为 ä½ł。在后续从 JSON 文件中读取词表时，可以再将 Ġ 这类字符映射回对应的字节。

简单来想，因为 JSON 中没办法直接存储字节序列，人们想要在 JSON 中存储二进制数据时，经常会使用 Base64 编码，这里的这种映射也可以看作类似的一种编码方法，它把不可打印的字节映射成了可打印的 Unicode 字符，从而可以安全地存储在 JSON 中。

总结

以上就是 BPE 的基本原理，其核心思路就是这样：从字节出发，不断合并高频对，直到词表够用。在大语言模型中，对输入文本进行 tokenize 的过程还有很多细节，包括文本的预处理、文本的预切分等等。