BPE分词

Byte Pair Encoding (BPE) 是一种简单的数据压缩算法，在1994年提出。后由论文Neural Machine Translation of Rare Words with Subword Units引入机器翻译，旨在解决未登录词（out-of-vocabulary）的翻译问题。

动机

为何会提出基于bpe的子词翻译方法？

1. 先前的解决方法，对于未登录词，需要去查稀有词汇词表。但是因为一个词可能对应于多个意思，因此在实际场景中，并不知道该用哪个。
2. 对于翻译人员来说，有些词即使没见过，也可以通过已知的子词翻译出来，这些词包括named entities（命名实体），cognates and loanwords（同源词和外来词），morphologically complex words（形态复杂的单词）等。bpe分词通过不断合并出现次数最多的字符对来捕获这种可识别的子词。

方法

论文给出的代码示例：

import re
import sys
import collections


def get_stats(vocab):
    pairs = collections.defaultdict(int)
    for word, freq in vocab.items():
        symbols = word.split()
        for i in range(len(symbols) - 1):
            pairs[symbols[i], symbols[i + 1]] += freq
    return pairs


def merge_vocab(pair, v_in):
    v_out = {}
    bigram_pattern = re.escape(' '.join(pair))
    p = re.compile(r'(?<!\S)' + bigram_pattern + r'(?!\S)')
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out


vocab = {'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}
num_merges = 15
for i in range(num_merges):
    pairs = get_stats(vocab)
    try:
        best = max(pairs, key=pairs.get)
    except ValueError:
        break
    if pairs[best] < 2:
        sys.stderr.write('no pair has frequency > 1. Stopping\n')
        break
    vocab = merge_vocab(best, vocab)
    print(best)

代码给出了一个简单样例，通过上述代码理解一下bpe学习的流程.

第一步：遍历训练语料，分词，统计每个词出现的频次（上述代码未给出）

假设语料比较小，只有以下几个词

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

第二步：将每个词分割成字母，并加上结束符号

注意结束符</w>与最后一个字母之间没有空格，被看成是一个字符

vocab = {'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}

第三步：统计所有字母对出现的频次（函数get_stats）

pairs =[(('e', 's'), 9), (('s', 't</w>'), 9), (('w', 'e'), 8), (('l', 'o'), 7), (('e', 'w'), 6), (('n', 'e'), 6), (('o', 'w</w>'), 5), (('d', 'e'), 3), (('i', 'd'), 3), (('w', 'i'), 3), (('o', 'w'), 2), (('e', 'r</w>'), 2)]
# 排序后

第四步：合并pairs 中频次最高的字母对，作为一个字符，并更新得到新的vocab （函数merge_vocab）

合并e s 为 es 得到：

vocab = {'l o w</w>': 5, 'l o w e r</w>': 2, 'w i d es t</w>': 3, 'n e w es t</w>': 6}

重复第三，四步

 pairs =[(('es', 't</w>'), 9), (('l', 'o'), 7), (('n', 'e'), 6), (('e', 'w'), 6), (('w', 'es'), 6), (('o', 'w</w>'), 5), (('d', 'es'), 3), (('i', 'd'), 3), (('w', 'i'), 3), (('w', 'e'), 2), (('o', 'w'), 2), (('e', 'r</w>'), 2)]

合并频次最高的字母对es t</w> 为 est</w>得到，

vocab = {'w i d est</w>': 3, 'l o w</w>': 5, 'l o w e r</w>': 2, 'n e w est</w>': 6}

重复第三，四步

pairs =  [(('l', 'o'), 7), (('w', 'est</w>'), 6), (('e', 'w'), 6), (('n', 'e'), 6), (('o', 'w</w>'), 5), (('d', 'est</w>'), 3), (('w', 'i'), 3), (('i', 'd'), 3), (('w', 'e'), 2), (('e', 'r</w>'), 2), (('o', 'w'), 2)]

合并频次最高的字母对l o 为 lo得到，

vocab ={'w i d est</w>': 3, 'lo w</w>': 5, 'n e w est</w>': 6, 'lo w e r</w>': 2}

重复第三，四步

 pairs =[(('w', 'est</w>'), 6), (('e', 'w'), 6), (('n', 'e'), 6), (('lo', 'w</w>'), 5), (('d', 'est</w>'), 3), (('w', 'i'), 3), (('i', 'd'), 3), (('e', 'r</w>'), 2), (('lo', 'w'), 2), (('w', 'e'), 2)]

合并频次最高的字母对w est</w> 为west</w>得到

vocab ={'w i d est</w>': 3, 'lo w</w>': 5, 'n e west</w>': 6, 'lo w e r</w>': 2}

直到num_merges循环结束，或者统计最高频次低于设定的阈值，结束

第五步：每次记录合并的频次最高的字母对，存入词表

最终词表的大小小于等于代码中所设定的num_merges 的值。
这里得到的词表可能不唯一，原因是因为选择最大的频次时，可能有多个相同频次的字母对

('e', 's')
('es', 't</w>')
('l', 'o')
('w', 'est</w>')
('e', 'west</w>')
('n', 'ewest</w>')
('lo', 'w</w>')
('d', 'est</w>')
('i', 'dest</w>')
('w', 'idest</w>')
('lo', 'w')
('e', 'r</w>')
('low', 'er</w>')

对于词表中未出现得词lowest，可以通过第五步得到的词表进行分词：

1. 加上结束符号l o w e s t\w
2. 根据词表首先合并e s 得到 l o w es t\w
3. 合并es t\w 得到 l o w est\w
4. 合并l o 得到 lo w est\w
5. 合并w est 得到 lo west\w
6. lo和west\w不能合并，因此lowest最终被分为lo west

使用方法

在机器翻译中，有两种使用bpe的方法，一种是学习两种独立的bpe编码，分别用于源语言和目标语言。另一种是学习源语言和目标语言的联合编码。前者的优点是在文本和词汇量上更紧凑，更能保证每个子词单元都出现在各自语言的训练文本中。后者则提高了源语言与目标语言分割的一致性

上述简单代码效率比较低，在实际的数据集上可使用官方源码 。其中，learn_bpe.py 用于从训练集中统计bpe词表，apply_bpe.py 用于bpe分词。另外，如果用于中文，需要先分词，然后再进行上面的流程，每次合并出现频次最大的字对。bpe不会跨词语进行合并。