BPE 算法的由来

BPE算法（Byte Pair Encoding），其目的是「使用一些子词来编码数据」。该方法已经成为了BERT等模型标准的数据预处理处理方式。

在机器翻译领域，模型训练之前一个很重要的步骤就是「构建词表」。对于英文语料，一个很自然的想法就是用训练语料中出现过的「所有英语单词」来构建词表，但是这样的方法存在两个问题：

• 训练语料中出现过的单词数目很多，这样的构造方式会使得词表变得很大，从而降低训练速度；
• 在模型测试中，很难处理罕见词或者训练过程中没有见过的词（OOV问题）。

另外一种方式是使用单个「字符」来构建词表。英文字符的个数是有限的，基于字符的方式可以有效缓解词表数目过大以及OOV的问题，但由于其粒度太细，丢失了很多单词本身所具有的语意信息。

为了解决上述问题，基于**Subword（子词）**的算法被提出，其中的代表就是BPE算法，「BPE算法的分词粒度处于单词级别和字符级别之间」。比如说单词"looked"和"looking"会被划分为"look"，"ed”，"ing"，这样在降低词表大小的同时也能学到词的语意信息。

BPE 分词算法的流程

核心三部分：

• 词表构建
• 语料编码
• 语料解码

词表构建

词表构建是 BPE 的核心，其是「根据训练语料」来构建BPE算法的词表。算法的整体步骤如下所示：

1. 准备模型的训练语料
2. 确定「期望的词表大小」
3. 将训练语料中的所有单词拆分为字符序列，利用这些字符序列构建初始的词表
4. 统计训练语料中每一个连续字节对出现的频率，「选择出现频率最高的字节对合并成新的subword，并更新词表」
5. 重复第4步，直到词表大小达到我们设定的期望或者剩下的字节对出现频率最高为1

下面我们通过一个例子来搞懂BPE词表构建的过程。假设我们目前的训练语料中出现过的单词如下，我们构建初始词表：

值得注意的是，我们在每一个单词的后面都加入了一个新的字符<\w>来表示这个单词的结束。初始的词表大小为7，其为训练语料中所有出现过的字符。

我们之后发现lo这个字节对在训练语料中出现频率最高，为3次。我们更新词表，将lo作为新的子词加入词表，并删除在当前训练语料中不单独出现的字符l和o。

之后我们发现low这个字节对在训练语料中出现频率最高，为3次。我们继续组合，将low加入词表中，并删去lo。需要注意的是，由于字符w在单词newer中仍然存在，因此不予删除。

继续循环过程，在词表中加入er,并删除r

循环该过程，直到词表的大小打到我们设定的期望或者剩下的字节对出现频率最高为 1.
最终得到了基于训练样本构建好的词表。

语料编码

词表构建好之后需要对语料进行编码。编码方式如下：

• 首先「将词表中所有的子词按照长度从大到小进行排序」
• 对于每一个给定的单词，我们遍历排序好的词表，寻找词表中的子词是否是该单词的子字符串。如果正好「匹配」，则输出当前子词，并对单词剩下的字符串继续匹配
• 如果遍历完词表，单词中仍然有子字符串没有被匹配，那我们将其替换为一个特殊的子词，比如<unk>。

🌰

(“errrr</w>”, 
“tain</w>”, 
“moun”, 
“est</w>”, 
“high”, 
“the</w>”, 
“a</w>”)

对于给定的单词mountain</w>,其分词结果为[moun,tain</w>]

语料解码

语料解码就是将所有的输出子词拼接在一起，直到碰到结尾为</w>为止。
🌰
假设模型输出为：

["moun","tain</w>","high","the</w>"]

那么其解压的结果为：

["mountain</w>","highthe</w>"]

总结

该算法是利用子词来编码数据，已经成为目前机器翻译领域的标准的预处理方式。

参考文献

[1] Sennrich, Rico, Barry Haddow, and Alexandra Birch. "Neural machine translation of rare words with subword units." ACL 2016.

[2] https://zhuanlan.zhihu.com/p/198964217

[3] https://zhuanlan.zhihu.com/p/86965595

[4] https://www.cnblogs.com/huangyc/p/1