BPE分词器
BPE分词器
字节对编码（Byte Pair Encoder，BPE），又称 digram coding 双字母组合编码，是一种数据压缩算法，用来在固定大小的词表中实现可变⻓度的子词。该算法简单有效，因而目前它是最流行的方法。
BPE 首先将词分成单个字符，然后依次用另一个字符替换频率最高的一对字符 ，直到循环次数结束。
1 分词算法
（1）准备语料库，确定期望的 merge 词表大小等参数。
（2）统计每个单词出现的频率。
（3）将语料库中所有单词拆分为单个字符，用所有单个字符建立最初的词典，并统计每个字符的频率。挑出频次最高的符号对 ，将新字符加入词表，然后将语料中所有该字符对融合（merge）。
注：新字符依然可以参与后续的 merge，有点类似哈夫曼树，BPE 实际上就是一种贪心算法 。
（4）重复遍历 2 和 3 操作，直到词表中单词数达到设定量或下一个最高频数为 1 ，如果已经达到设定量，其余的词汇直接丢弃。
2 一个示例
比如我们想编码：
我们会发现这里的aa出现的词频最高（我们这里只看两个字符的频率），那么用这里没有的字符Z来替代aa：
此时，又发现ab出现的频率最高，那么同样的，Y来代替ab：
同样的，ZY出现的频率大，我们用X来替代ZY：
最后，连续两个字符的频率都为1了，算法也就结束了。
3 GPT2tokenizer
GPT2tokenizer同时也是gpt3的tokenizer，它的词汇表由256个单字节符号+50000个merge词+1个<|endoftext|>组成。
我们需要知道，词汇表是一个键为字节串值为token_id的字典，编码的过程和构造merge词表的过程相差无几，唯一的区别是结束的条件不同，而解码的过程则就是编码的反向过程。
尽管词汇表里面已经包含所有的merge词，但是GPT2tokenizer还是需要一个merges.txt来记录所有对merge词对，从下面算法流程就能明白原因了。
3.1 训练
训练的步骤与前面所提到的BPE原始步骤基本一致，除了一个在GPT2论文中提到的一个额外限制。由于dog有很多变体“dog.”、“dog!”出现的频率非常高，但是它对语言建模而言是次优的，因此官方制定了一条限制——不能跨符号类别进行merge操作。在加入这个限制的BPE算法下GPT2tokenizer诞生了。
3.2 编码
（1）把所有字符通过utf-8规则转换成字节串。
（2）扫描所有2-gram，检索merges.txt，选择优先级最高的词对（在merges.txt中位置越靠前优先级越高），进行merge操作。
（3）循环第2步，直到某一轮扫描，所有2-gram都不是merge词对为止。
（4）对这个经过merge操作的新串，使用词汇表映射到token_id。
3.3 解码
（1）对所有token_id列表，使用键值互换的反向词汇表映射到一个字节串列表。
（2）合并这个字节串列表为一个字节串。
（3）使用utf-8规则将字节串解码为人类可以理解的自然语言字符串。
下面举例说明一下，解码的步骤。
首先下面是utf-8从字节解码到字符的规则。
（1）0xxxxxxx(0-7) 单独成字符
（2）10xxxxxx(8-B) 作为后缀字节
（3）110xxxxx(C-D) 有一个后缀字节
（4）1110xxxx(E) 有两个后缀字节
（5）1111xxxx(F) 有三个后缀字节
下面演示了从输入token序列[4399, 2572, 3461]到字符串的完整过程。
（1）[4399, 2572, 3461]
（2）[[2325, 168], [201, 234], [102, 129]]
（3）[[[101, 104], 168], [201, 234], [102, 129]]
（4）[101, 104, 168, 201, 234, 102, 129]
（5）\xc2\xa1\x65\xe6\x93\x84\x42
（6）[\xc2\xa1, \x65, \xe6\x93\x84, \x42]
（7）你a他4
大概过程就是token返回到字节，再根据字节高四位来唯一编码，比如\xc2高四位是c，那后面就有一位字节和他一起编码到字符。
3.4 总结
词汇表中有大量的英文单词，但也有很多光看词汇表看不出来是哪国语言的奇异符号，其实把它们通过utf-8规则解码到字符串我们才能发现，词汇表是包括了一些汉字，日文假名和其他国的一些高频词汇的。至于不在词汇表的字词，只能通过词汇表上的字节或字节串来“碎片”地表示了，这也就是BPE分词器解决OOV问题的一种思路。至于为什么英文单词那么多，因为BPE算法训练tokenizer的语料库以英文语料库为主。
值得注意的是，词汇表中“cat”前有没有空格是不算作同一个token的。其中有空格代表一个英文单词或者是一个英文单词前缀，而没有空格则代表了cat作为英文单词的中间片段或者后缀。