Byte Pair Encoding (BPE)

分词算法的目的就是将输入的整个序列分割为 token 序列。对于英文来说，最简单的分词方法就是以空格来分割出每一个单词(token)。对于中文而言，虽然没有像英文那样天然的分隔符，但是也可以使用 jieba、hanlp 等分词工具来将输入序列转换成 token 序列。

Paper: https://arxiv.org/pdf/1508.07909.pdf

这有什么问题吗？

如果我们只训练某个小领域的神经网络模型的话，使用前面的分词方法构建词表也是可以的。但是，如果涉及多个领域的话，或一个通用领域的模型，这个词表就会变得非常大。英文词汇量一共有40到60万，常用的就达到了3到4万，我们想要把这3到4万的单词都进行很好的训练，得到一个较为通用的表征，这就需要极其庞大的语料，并且及时这样仍然可能会碰到一些模型没见过的单词，这些词我们可以叫做 oov(out of vocabulary)词, 这些词只能用 unk 这种特殊的 token 来表示。

另外，对于像 love loves loving 这些词，模型会当做 3 个不同的词来学习，学习不到这些词之间的关系。

简单而言，前面这种传统的方式会使得构建出的词表太大，会极大增加模型的训练难度，并且对于 oov 的适应性也不好。研究人员就希望能够有另外一种方法，在构建分词时，既能够表征更多的词、词表还要尽可能小、并且也能够适应 oov 词。

这时，我们可能会想到英文不就 26 个英文字母嘛，我们就以字符粒度来构建词表，任何词都可以表示了。但是这里也存在一个问题，这个粒度太小了，以至于单词和单词之间的关系，模型无法学习到。并且这种方式也会使得模型的输入非常长，导致建模困难。

所以，简单按空格方式粒度太粗，以字符粒度过于细，所以要在这两种极端方案之间寻找平衡的方案。

研究人员琢磨出了基于子词分割的算法，这种算法直观的特点就是分出来的 token 大部分看起来不像是一个独立的单词了，而是一个词的部分，例如：loving 这个词在词表中可能就变成了 lov 和 ing 两个 token. 很多单词都变成这种 “零件” 的形式，这样的话，大多的词都是使用多个 “零件” 来表示，即使碰到未登录词，也可以用词表中的 “零件” 来表示。

对于中文的话也是类似的思想，将某些中文词拆分为更小粒度的 token，复杂的词由这些更小粒度的词来构建表示。这样的方式，直观上，可以使用更小的词表表征更多的词，并且对 oov 词也有很好的适应性。

如何从输入的序列来提取这些子词，并构建词表？

我们这篇文章先以 BPE 字节对编码算法为例，来看看这种算法是如何构建词表的。该算法的基本思想就是先将原始文档切分成一个一个字符，然后通过一定的方法开始连续字符，直到达到指定词表大小。

假设：我们对输入的文档经过统计计算之后，得到下面的内容(数字表示该词在文档中出现的次数)：

{'low': 5, 'lower': 2, 'newest':6, 'widest':3}

上面的单词分割成字符级别，并在尾部增加一个特殊的标记 </w> 表示结束符，当然该结束符也可以设计为其他的表示。此时，我们的文档表示和初始的词表如下：

# 当前文档表示
{'l o w </w>' : 5, 'l o w e r </w>' : 2, 'n e w e s t </w>':6, 'w i d e s t </w>':3}

# 初始词表(11个token)：
{'l', 'r', 'n', 'd', 'o', 't', 's', 'e', 'i', '</w>', 'w'}

接下来，我们统计连续字节对出现的频率，例如：

1. lo 共出现 5 + 2 = 7 次
2. ow 共出现 5 + 2= 7 次
3. w</w> 共出现 5 次
4. we 共出现 2 + 6 = 8 次
5. er 共出现 2 次
6. es 共出现 6 + 3 = 9 次
7. … 以此类推，计算所有连续相邻 2 个字节对在语料中出现的次数

经过统计之后，我们发现 es 字节对出现的次数最高，我们就将其合并作为一个新的子词添加到词表中，此时，我们还得看看 e 和 s 是否作为单独词出现在文档，将不作为单独出现的 e 或者 s 或者两者同时从词表中删除。

此时，我们发现 e 仍然作为单独字节会出现在文档中，而 s 与 es 合并之后，就不再以独立的姿态存在，所以，我们将 es 加入到词表中时，并把 s 从词表中删除，如下：

# 当前文档表示
{'l o w </w>' : 5, 'l o w e r </w>' : 2, 'n e w es t </w>':6, 'w i d es t </w>':3}

# 词表(11个token): 加入了 es，并删除了 s
{'l', 'r', 'n', 'd', 'o', 't', 'e', 'i', '</w>', 'w', 'es'}

以此类推，要不剩下的子词小于最小的合并频率，要不达到了指定数量的词表，此时就停止分词过程。接下来，我们基于 tokenizers 库，来构建下词表：

from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import Whitespace



def test():
    document = ['low'] * 5 + ['lower'] * 2 + ['newest'] * 5 + ['widest'] * 3
    print(document)

    # 指定分词器使用 BPE 算法模型，并设置特殊 UNK 标记
    tokenizer = Tokenizer(model=BPE())
    # 设置单词的分割方式
    tokenizer.pre_tokenizer = Whitespace()
    # 构建训练器
    trainer = BpeTrainer(min_frequency=1, vocab_size=100)
    # 开始训练
    tokenizer.train_from_iterator(document, trainer)
    # 保存分词器
    tokenizer.save('./tokenizer.json')


if __name__ == '__main__':
    test()

程序会在当前目录下输出 tokenizer.json 文件，该文件的内容如下：

{
  "version": "1.0",
  "truncation": null,
  "padding": null,
  "added_tokens": [],
  "normalizer": null,
  "pre_tokenizer": {
    "type": "Whitespace"
  },
  "post_processor": null,
  "decoder": null,
  "model": {
    "type": "BPE",
    "dropout": null,
    "unk_token": null,
    "continuing_subword_prefix": null,
    "end_of_word_suffix": "</w>",
    "fuse_unk": false,
    "vocab": {
      "d": 0,
      "e": 1,
      "i": 2,
      "l": 3,
      "n": 4,
      "o": 5,
      "r": 6,
      "s": 7,
      "t": 8,
      "w": 9,
      "w</w>": 10,
      "t</w>": 11,
      "r</w>": 12,
      "es": 13,
      "est</w>": 14,
      "lo": 15,
      "ew": 16,
      "new": 17,
      "low</w>": 18,
      "newest</w>": 19,
      "dest</w>": 20,
      "idest</w>": 21,
      "widest</w>": 22,
      "er</w>": 23,
      "wer</w>": 24,
      "lower</w>": 25
    },
    "merges": [
      "e s",
      "es t</w>",
      "l o",
      "e w",
      "n ew",
      "lo w</w>",
      "new est</w>",
      "d est</w>",
      "i dest</w>",
      "w idest</w>",
      "e r</w>",
      "w er</w>",
      "lo wer</w>"
    ]
  }
}

输出中，vocab 对应的内容就是我们的词表，merges 是合并过程，比如第一个将 es 合并了，第二次将 est 合并了 …. 以此类推。当然，实际在构建词表时，除了来源于文档的 token, 我们还得需要增加一些训练过程中需要的 token，例如：UNK、PAD、CLS、SEP、MASK 等特殊的标记。

我们发现 BPE 算法是基于词频率来进行分词，构建词表的。这样的分词算法，也有一定的缺点：

1. 基于统计的方法：BPE分词是基于统计的方法，因此可能会存在一些分词错误。例如，对于生僻词或专业术语，BPE分词可能无法正确地识别所有子词，从而导致分词错误。
2. 分词结果不唯一：BPE分词不是唯一的，即对于一个单词，可能存在多种分解方式。这使得在进行自然语言处理任务时需要处理多个分词结果，增加了计算和存储的复杂度。
3. 分词开销较大：BPE分词需要计算大量的字母和字符的出现频率，因此在处理大量文本时，BPE分词的计算开销可能会很大。
4. 不支持上下文信息：BPE分词是一种无上下文的分词方法，它只考虑单词内部的字母和字符，而不考虑上下文信息。因此，BPE分词可能无法正确地识别一些复杂的词汇，例如人名、地名等。

还有个问题，我们发现在中文分词场景下，我们很少使用 BPE，也就是说欧美国家的语料使用 BPE 较多，而中文则不适合，这是为什么呢？

对于英文单词而言，其可能包含前缀、后缀，通过 BPE 能够学习到单词前缀、后缀的一些含义，对于中文的字而言，不能再拆分了。所以，中文的话，要不使用 jieba 之类的分词软件分成一个一个具有某个具体意义的词，要不就分成单个字更合适一些。