NLP中的BPE（byte pair encoding）分词算法

一时失言乱红尘 2022-08-31 01:49 71阅读 0赞

本篇博客的算法来源的论文是*Neural Machine Translation of Rare Words with Subword Units*，感兴趣的读者可以自行在Google学术上搜索。

# 算法提出的问题背景 #

2016年左右（改论文发表于2016）Neural machine translation(NMT)中有着一个众所周知的问题——稀有词与未知词的翻译问题。一般来说，神经网络中的词表被限制在30000-50000个词汇，但是对于翻译来说，各种词汇都可能出现（比如英语中的复合词汇，网络新词等），这种限制无疑使问题解决得效果大打折扣。对于英语来说，一个单词可能有不同时态，进行时，过去时，一般现在时等，比如look, looking, looks, looked这些单词都表示的意思，但是传统处理手段就是在词表中为这些单词各开一个位置，这不仅造成了冗余，还削弱了它们之间的相关性。  
基于上述问题，论文中提出将一个单词用可变长度表示，也就是关注于更小的分词单元（subword unit）似乎更加有吸引力。对于word-level的NMT模型，在遇到新词以后往往需要借助查阅字典的手段（15年左右被提出的一种方法，它假设source和target中的词汇是一 一对应的），论文作者认为这种假设在很多情况不适用，事实上也的确如此。此外，这种模型没法翻译或者生成没见过的单词。一些学者提出将未知的单词直接从source language复制到target language的翻译中，这对于名字来说确实很合理，但是在其他情况也许就不适用了。

# 算法希望实现的目标 #

创建一个subword-level的NMT模型，对于稀有词和未知词的翻译能够自己结果，能够生成在训练时没有见过的新词，能够从subword representations中学习复合词和音译词。

# Byte Pair Encoding(BPE) #

BPE算法最初是在1994提出的一种简单的数据压缩技术，它会迭代多次，每一次迭代的时候将出现频率最高的字节对用一个单个的，没出现过的字节替代，这样就从两个字节变成了一个字节。论文中采用了这个算法来做单词切割。只不过合并的不是字节对，而是单词中的字符或者字符序列。  
首先，将每个单词用一个字符序列表示，然后在末尾增加一个单词结束符（比如look，就变成l o o k </w>）,然后利用这些字符序列来统计字符对的频率。（l o o k 这个序列可以看作**l o**, **o o**, **o k** , k </w>这几个字符对）。每一轮迭代的时候将出现频率最高的字符对合并。每次合并产生一个新的symbol,它代表了一个n-gram的字符。最终新的symbol 词典的大小等于最初的词典大小加上merge操作的数量。我们可以将这个操作施加到从一个文本中统计出的词频表上。

# 算法实现 #

首先，词频表的key需要是一个字符序列，且在末尾加上一个单词结束符，字符之间有空格方便后面拆分

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
    		 }

第二步，我们需要构建自己的symbol表，也就是一个个字符对

from collections import defaultdict
    #defaultdict会在查询的key missing时，给它一个默认值，比如我们下面的int类型的defaultdict
    #它的默认值就是0
    def get_stat(vocab_dict):
        result = defaultdict(int)
        for word,freq in vocab_dict.items():
            symbol = word.split()
            for i in range(len(symbol) - 1):
                result[symbol[i],symbol[i+1]] += freq
        return result

![在这里插入图片描述][2825efdc0f0ea17a69752ed023cc4667.png]  
第三步，我们需要实现一个merge方法，它的作用是传入一个频率最高的字符对，我们在原始的vocab\_dict中挨个检查每个sequence，如果包含这个字符对就将其合并。并增加这个字符对作为key  
这块涉及到了正则表达式里面的零宽断言，详细可以查看我的另一篇博文[https://blog.csdn.net/qq\_43152622/article/details/118967901?spm=1001.2014.3001.5501][https_blog.csdn.net_qq_43152622_article_details_118967901_spm_1001.2014.3001.5501]

re.compile('(?<!\S)' + bigram + '(?!\S)')

def Merge_vocab(pair,vocab_dict):
        """ pair:出现频率最高的字符对 vocab_dict:原始的词汇表 """
        v_out = dict()
        bigram = re.escape( ' '.join(pair))#将一些特殊符号转移，返回待会正则匹配的时候出幺蛾子
        p = re.compile('(?<!\S)' + bigram + '(?!\S)')
        for word in vocab_dict:
            w_out = p.sub(''.join(pair),word)
            v_out[w_out] = vocab_dict[word]
        return v_out

![在这里插入图片描述][7a6f3f6a90735c8dfbdb6adcddacff06.png]

num_merges = 12
    vocab_dict = { '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,"f a s t e r </w>":5}
    for i in range(num_merges):
        pairs = get_stat(vocab_dict)
        best =max(pairs, key=pairs.get)
        vocab_dict = Merge_vocab(best, vocab_dict)
        print(best)

![在这里插入图片描述][05505103d3d85746b89721292570f34d.png]  
![在这里插入图片描述][7527c89f5492ff9f22f3a48ad585cd5f.png]  
可以看到最后的结果中一些出现次数最多的subword已经被合并了。

[2825efdc0f0ea17a69752ed023cc4667.png]: /images/20220829/76c50783971f4fd1b74d7258bcaf388e.png
[https_blog.csdn.net_qq_43152622_article_details_118967901_spm_1001.2014.3001.5501]: https://blog.csdn.net/qq_43152622/article/details/118967901?spm=1001.2014.3001.5501
[7a6f3f6a90735c8dfbdb6adcddacff06.png]: /images/20220829/89a69fc32f18447fad66425eeb062945.png
[05505103d3d85746b89721292570f34d.png]: /images/20220829/3a6a44230b024fe2816893a4535d10ce.png
[7527c89f5492ff9f22f3a48ad585cd5f.png]: /images/20220829/3843e197b0bd43c187b425e5ac481920.png