Tokenization

对于中文和英文而言，由于语言差异导致算法也有差异。对于中文，存在字粒度和词粒度。对于英文，存在三个级别的粒度，character level，subword level，word level。下面主要阐述中文的词粒度和英文的subword level。

一、中文

1.1 原理

https://zhuanlan.zhihu.com/p/146792308

1.2 常见中文分词工具

# #####stanfordcorenlp
from timeit import default_timer as timer
from stanfordcorenlp import StanfordCoreNLP
tic = timer()
path="XXXXX"
nlp_zh = StanfordCoreNLP(path,lang='zh')#模型文件路径
sentence = "搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来"
tic = timer()
print ('Tokenize:', nlp_zh.word_tokenize(sentence))
toc = timer()
print(toc - tic) # 输出的时间，秒为单位
#########thulac
import thulac
thu1 = thulac.thulac(seg_only=True)  #默认模式
tic = timer()
text = thu1.cut("搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来", text=True).split(" ")  #进行一句话分词
toc = timer()
print(text)
print(toc - tic)
####jieba
import jieba
tic = timer()
print(jieba.lcut(str("搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来")))
toc = timer()
print(toc - tic)

Tokenize: ['搜索', '引擎', '会', '通过', '日志', '文件', '把', '用户', '每次', '检索', '使用', '的', '所有', '检索', '串都', '记录', '下来']
运行时间：22.68650701455772
['搜索引擎会', '通过', '日志', '文件', '把', '用户', '每', '次', '检索', '使用', '的', '所有', '检索', '串', '都', '记录', '下', '来']
运行时间：0.0016864966601133347
['搜索引擎', '会', '通过', '日志', '文件', '把', '用户', '每次', '检索', '使用', '的', '所有', '检索', '串', '都', '记录下来']
运行时间：0.9094752036035061

观察结果，可以看出thulac分词效率最高，jieba分词的精度和效率比较平衡，stanfordcorenlp分词粒度很细，但是速度慢

二、英文

SubWord算法如今已成为一个重要的NLP模型的提升算法。其主要优势如下：

1.word level存在OOV问题，一旦碰到就是back off to a dictionary，无法很好地处理未知和罕见词汇
2.Character level可以解决OOV，但是相比于 word-level , Character-level 的输入句子变长，使得数据变得稀疏，而且对于远距离的依赖难以学到，训练速度降低。
常见的SubWord算法有：BPE，WordPiece，Unigram Language Model等

2.1 BPE

全称为Byte Pair Encoding，算法来自paper《Neural Machine Translation of Rare Words with Subword Units》。

2.1.1 构建BPE subword词表

原理

1. 准备足够大的训练语料
2. 确定期望的subword词表大小
3. 将单词拆分为字符序列并在末尾添加后缀“ </ w>”并且统计单词频率。停止符”</w>”的意义在于表示subword是词后缀。具体来说，不加”</w>”可以出现在词首，加了”</w>”只能位于词尾。例如，“ low”的频率为5，那么我们将其改写为“ l o w </ w>”：5
4. 统计每一个连续字节对的出现频率，选择最高频者合并成新的subword
5. 重复第4步直到达到第2步设定的subword词表大小或下一个最高频的字节对出现频率为1

注意，每次合并后词表可能出现3种变化：

• +1，表明加入合并后的新字词，同时原来的2个子词还保留（2个字词都不是完全随着另一个字词的出现而紧跟着出现）
• +0，表明加入合并后的新字词，同时原来的2个子词中一个保留，一个被消解（只有一个字词完全随着另一个字词的出现而紧跟着出现）
• -1，表明加入合并后的新字词，同时原来的2个子词都被消解（2个字词同时连续出现）

例子：

训练语料为：

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

Iter 1, 最高频连续字节对”e”和”s”出现了6+3=9次，合并成”es”，输出：

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

Iter 2, 最高频连续字节对”es”和”t”出现了6+3=9次, 合并成”est”，输出：

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

Iter 3, 以此类推，最高频连续字节对为”est”和”</w>” ，合并后输出：

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

……

Iter n, 继续迭代直到达到预设的subword词表大小或下一个最高频的字节对出现频率为1。

代码

import re, 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 = re.escape(' '.join(pair))
    p = re.compile(r'(?<!\S)' + bigram + 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 = 10
for i in range(num_merges):
    pairs = get_stats(vocab)
    best = max(pairs, key=pairs.get)
    vocab = merge_vocab(best, vocab)
    print(best)

('e', 's')
('es', 't')
('est', '</w>')
('l', 'o')
('lo', 'w')
('n', 'e')
('ne', 'w')
('new', 'est</w>')
('low', '</w>')
('w', 'i')

2.1.2 编解码

编码

1.将subword词表按照子词长度由大到小排序。

2.对于每个单词，遍历排好序的subword词表，寻找是否有token是当前单词的子字符串。最终，我们将迭代所有token，并将所有子字符串替换为token。

3.如果仍然有子字符串没被替换但所有token都已迭代完毕，则将剩余的子字符串替换为特殊token，如。

例子：

# 给定单词序列
[“the</w>”, “highest</w>”, “mountain</w>”]

# 假设已有排好序的subword词表
[“errrr</w>”, “tain</w>”, “moun”, “est</w>”, “high”, “the</w>”, “a</w>”]

# 迭代结果
"the</w>" -> ["the</w>"]
"highest</w>" -> ["high", "est</w>"]
"mountain</w>" -> ["moun", "tain</w>"]

编码的计算量很大。对于已知数据，我们可以pre-tokenize所有单词，并在词典中保存单词和tokenize的结果。如果存在字典中不存在的未知单词，可以应用上述编码方法对单词进行tokenize，然后将新单词以及tokenize的结果添加到字典中备用。

解码

将所有的subword拼在一起。

例子：

# 编码序列
[[“the</w>”], [“high”, “est</w>”], [“moun”, “tain</w>”]]

# 解码序列
[“the</w>”, “highest</w>”, “mountain</w>”]

2.1.3 和embedding结合

1.构建词表，假设有subword词表：[“errrr</w>”, “tain</w>”, “moun”, “est</w>”, “high”, “the</w>”, “a</w>”]

2.编码，词语”highest”编码成[“high”, “est</w>”]

3.向量表示，$[E_{high},\ E_{est(/w)}]$]

https://www.cnblogs.com/d0main/p/10447853.html

2.2 WordPiece

算法来自于《Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation》

WordPiece算法可以看作是BPE的变种。不同点在于，WordPiece基于概率生成新的subword而不是下一最高频字节对。

2.2.1 原理

1. 准备足够大的训练语料
2. 确定期望的subword词表大小
3. 将单词拆分成字符序列
4. 基于第3步数据训练语言模型
5. 从所有可能的subword单元中选择加入语言模型后能最大程度地增加训练数据概率的单元作为新的单元
6. 重复第5步直到达到第2步设定的subword词表大小或概率增量低于某一阈值

2.3 ULM

2.4 char n-gram

https://arxiv.org/abs/1607.04606

2.5 Byte-Level BPE

《Neural Machine Translation with Byte-Level Subwords》

3.总结

我们在进行中文NLP任务的时候，目前基本都是字粒度；英文的话大多数是使用subword的wordpiece。

参考

https://zhuanlan.zhihu.com/p/112444056

https://arxiv.org/pdf/1508.07909.pdf

https://zhuanlan.zhihu.com/p/38130825

https://zhuanlan.zhihu.com/p/86965595

https://blog.csdn.net/zhangxiaolinxin/article/details/107052054?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.base&spm=1001.2101.3001.4242

https://www.cnblogs.com/mj-selina/p/13687291.html