BPE (Byte-Pair Encoding)

字节对编码（BPE）最初是作为一种压缩文本的算法开发的，最早是由 Philip Gage 于 1994 年在《A New Algorithm for Data Compression》一文中提出

后来被 OpenAI 在预训练 GPT 模型时用于分词器（Tokenizer），它被许多 Transformer 模型使用，包括 GPT、GPT-2、RoBERTa、BART 和 DeBERTa

本文尝试用最直观的语言和示例来解释 BPE 算法

本文的分词是在英文（拉丁语系）状态下进行的，中文状态下的分词会在后续的文章中讨论

直觉式理解

假设我们有一份语料，其中包含以下单词：

faster</ w>: 8, higher</ w>: 6, stronger</ w>: 7

其中，数字表示单词出现的次数

</ w> 表示单词的结束，使用 “w” 是因为它是 “word” 的首字母，这是一种常见的命名约定。然而，具体的标记 token 可能会根据不同的实现或者不同的分词方法有所不同

首先，我们将其中的每个字符作为一个 token，得到的 token 如下：

f a s t e r</ w>: 8, h i g h e r</ w>: 6, s t r o n g e r</ w>: 7

对应的字典如下：

'a', 'e', 'f', 'g', 'h', 'i', 'n', 'o', 'r', 's', 't', 'r</ w>'

第二步，我们统计每两个 token 相邻出现的次数，得到如下结果：

'fa':8,'as':8,'st':15,'te':8,'er</ w>':21,'hi':6,'ig':6,'gh':6,'he':6,'tr':7,'ro':7,'on':7,'ng':7,'ge':7

8+8+15+8+21+6+6+6+6+7+7+7+7+7=115

我们将出现次数最多的字符’e’和’r</ w>‘对合并’er</ w>‘（这就是 byte pair 字节对的名称由来），token 变为：

f a s t er</ w>: 8, h i g h er</ w>: 6, s t r o n g er</ w>: 7

对应的字典变化为：

'a', 'f', 'g', 'h', 'i', 'n', 'o', 's','r', 't', 'er</ w>'

注意：此时的’e’和’r</ w>‘被’er</ w>‘消融了，因为在 token 中除了’er</ w>‘中有’e’和’r</ w>‘其他地方都没有

第三步，现在’er</ w>‘已经是一个 token 了，我们继续统计相邻 token 出现的次数，得到如下结果：

'fa':8,'as':8,'st':15,'ter</ w>':8,'hi':6,'ig':6,'gh':6,'her</ w>':6,'tr':7,'ro':7,'on':7,'ng':7,'ger</ w>':7

我们将出现次数最多的字符’t’和’er</ w>‘对合并’ter</ w>‘，token 变为：

f a s ter</ w>: 8, h i g h er</ w>: 6, s t r o n g er</ w>: 7

对应的字典变化为：

'a', 'f', 'g', 'h', 'i', 'n', 'o', 's','r', 't', 'er</ w>', 'ter</ w>'

注意：此时的’er</ w>‘和’t’都没有被’ter</ w>‘消融了，因为在 token 中除了’ter</ w>‘中有’er</ w>‘，其他地方也有’er</ w>‘和’t’

重复上述步骤，直到达到预设的 token 数量或者达到预设的迭代次数

这两个就是 BPE 算法的超参数，可以根据实际情况调整

BBPE 是一种基于 BPE 的分词器，它是 BPE 的一种变种，是由 Google Brain 团队提出的。BBPE 的全称是 Byte-level BPE，是一种基于字节级别的 BPE 分词器

BBPE 的核心思想是将文本中的字符对（UTF-8 编码中是字节对）进行合并，以形成常见的词汇或字符模式，直到达到预定的词汇表大小或者无法继续合并为止

它和 BPE 的区别在于，BPE 是基于字符级别 character 的，而 BBPE 是基于字节 byte 级别的

BBPE 具有如下的优点：