算法工程师面试之BPE算法_bpe算法实现

前言

• 文章来源：说文科技
• 如果需要快速掌握，请跳至 3.实例 部分

---

1. 简介

BPE是Byte-Pair Encoding的缩写。在NLP中的应用，主要就是为了词分割，即将一个单词tokenize 的过程。我们都知道在处理NLP问题时，有时候模型碰到的词没有出现在词表中，这就是常说的OOV 问题，那么该怎么解决这种问题呢？于是伟大的先行者们就尝试使用subword （就是将一个单词分割成多个段）的方式来解决这个问题。本文要介绍到的BPE算法就属于一种 subword 方法。

2. 思想

主要思想就是：
挑选语料库中出现频率最高的两个字符串对（byte-pair），用二者的组合不断地替换原来空格分割的两个字符串，更新该word。循环这个步骤k次，得到一个目标词表（使用这个目标词表处理后面遇到的数据）。
这里详细讲解一下BPE算法的实现过程。
先看一下该算法的输入：

初读上面这句话，一直不理解，其实上面这句话的意思说的是：

BPE算法通常运行在词内部（不合并跨词的边界），所以输入语料首先是一个空格分割的一组字符串【比如上面的l o w _】，每组字符都对应一个词，加上词尾标志_，以及这个单词出现的次数。

根据上面这句话，我们结合上面这个示例给出一个解释：

• step 1. 依次统计相邻两个字符的出现的频率，并将出现字符频率最高的两个字符串替换成某个字符串，并将得到的字符串放入到vocabulary 中
• step 2.重复执行上一步，直到循环k次
• step 3.根据迭代得到的vocabulary，将单词替换掉

3.示例

下面就以：

为例，逐步分析BPE算法运行的过程，其中vocabulary = l o w e s t n r i d _

• iterate = 1: e r 连续出现的次数最高，为6+3=9次，所以就将二者替换成er，并将er放入到 vocabulary 中
  那么得到的结果就是:

vocabulary = l o w e s t n r i d _ er

• iterate = 2：接着发现er _ 出现的次数最高，替换，并将 er_放入到词表中，得到vocabulary = l o w e s t n r i d _ er er_

• iterate = 3：接着发现n e 连续出现的频率最高，再次替换，更新vocabulary = l o w e s t n r i d _ er er_ ne

• iterate = 4：接着发现 ne w 出现的次数最高，再次替换，更新vocabulary = l o w e s t n r i d _ er er_ ne new

• iterate = 5: 接着发现 l o 出现的次数最高，再次替换，更新vocabulary = l o w e s t n r i d _ er er_ ne new lo

• iterate = 6: 接着发现lo w的频率最高，替换，更新vocabulary = l o w e s t n r i d _ er er_ ne new lo low

• iterate = 7: 接着发现new er_的频率最高【出现了6次】，替换，更新vocabulary = l o w e s t n r i d _ er er_ ne new lo low newer_

• iterate = 8: 接着发现low _的频率最高，替换，更新vocabulary = l o w e s t n r i d _ er er_ ne new lo low newer_ low_

…
迭代指定的次数k（即算法的超参数），算法结束。

下面我们使用得到的vocabulary处理 newer_这个单词，首先需要将newer_ => n e w e r _。然后发现vocabulary中依次出现er er_ ne new newer_ 那么最后tokenize得到的结果就是 newer_ ；同理处理lower_ => l o w e r _。根据vocabulary 中的er er_ lo low ，那么最后得到的结果就是： low er_

4.参考资料

• 讲解BPE算法的资料，这个资料是斯坦福大学的Speech and Language Processing：https://web.stanford.edu/~jurafsky/slp3/2.pdf