文章目录
BPE简介Vocabulary构建Encoding and DecodingBPE简介
BPE是一种数据压缩算法的简单形式，数据中最常见的连续字节对被替换成该数据中不存在的字节。BPE的主要目标就是使用最少的token数目来表示一个corpus
在 A New Algorithm for Data Compression中首次提出
样例：
假如我们有数据aaabdaaabac需要 encoded（compressed）字节对aa是最长出现的，因为我们用Z来代替，Z=aa现在我们得到数据ZabdZabac这时候，最常出现的字节对是ab，我们用Y=ab来代替得到ZYdZYac现在，最常见的字节对是ZY, 我们用X=ZY来进行代替最后我们得到XdXac，这不能够再被压缩了，因为没有字节对出现多于一次
我们按照逆向的方式进行解压
Vocabulary构建
BPE保证最常见的词在词典中以 single token 进行表示，罕见的词被拆分成 subword tokens，这与subword-based tokenization是相同的
假定我们有个 corpus 包含下面这些词（基于空格做了pre-tokenization之后的）：
{“old”: 7, “older”: 3, “finest”: 9, “lowest”: 4}
我们为每个词的后面加上 token</w>
{“old”: 7, “older”: 3, “finest”: 9, “lowest”: 4}
</w>为词加上边界，算法才知道词是在哪里结束的这帮助算法查看每个字符，找到出现频率最高的字节对
下一步，我们将每个词拆分成字符，并计算他们的出现次数，初始结果如下：
BPE算法就是要找出出现最频繁的对，然后合并它们，依次循环，直到达到了循环限制或者token限制。
这里我们将字符看作是字节
Iterations：
Iteration 1：我们从第二频繁的字母e开始（因为第一个是</w>），与e共同出现最多的是s（9 + 4 = 13次），因此我们合并成es并添加到词汇表中，同时更新单独的e和s的出现次数
Iteration 2：现在，最常出现的是es和t，一共出现了 13 次。因此我们合并成est，添加到词汇表中，并更新es和t的出现次数
**Iteration 3：**现在，最常出现的是est和</w>，一共出现了 13 次。因此我们合并成est</w>
合并停止符</w>是很重要的。这帮助算法理解highest和estimate的区别，他们两个的est一个出现在开头，一个出现在结尾，合并上</w>，这两种est才会做不同的处理
**Iteration 4：**现在，出现次数最多的是o和l，一共出现 10 次，我们合并成ol
**Iteration 5：**现在，出现次数最多的是ol和d，一共出现 10 次，我们合并成old
从上表中，我们可以看到f,i,n的出现次数都是 9，但是这三个字母都只在一个单词中出现了，所以我们不再进行合并，我们停止 Iteration
最后我们的词汇表中共有 11 项，比之前的 12 项只小一点。这是一个很小的 corpus，在实际中尺寸会减小很多这 11 个 token 组成我们的词汇表
在实际中，词汇表中的 token 随着 iteration 会先增加再减少，停止 Iteration 的准则可以是 tokens 的个数或者 Iteration 的次数
Encoding and Decoding
对 decode 来说，简单将所有 token 何在一起就好了
encoded sequence：[“the”, “high”, “est”, “range”, “in”, “Seattle”]
decoded：[“the”, “highest”, “range”, “in”, “Seattle”]
而不是[“the”, “high”, “estrange”, “in”, “Seattle”]，因为有</w>
对于 encode 新的数据，也很简单，但是计算量比较大
sequence：[“the”, “highest”, “range”, “in”, “Seattle”]我们会遍历 corpus 中发现的所有 tokens（遍历已经获得的 token list），尝试去替换 substring。如果剩下了一些 substring，就替换成 unknow tokens
通常情况下，词汇表很大，但是也有一些没见过的词。实践中，我们将 pre-tokenize 后的词存在字典中。我们应用上述编码方法对 unknown words进行tokenization，并将新单词的tokenization添加到我们的字典中以供将来使用
参考：Byte-Pair Encoding: Subword-based tokenization | Towards Data Science
