说起Tokenizer，不得不先介绍一下Subword
目前常见的Subword算法包括BPE、WordPiece、Unigram、SentencePiece及相关变体

BPE

BPE —— Byte-Pair Encoding 是一种压缩算法，BPE算法按如下步骤生成词表:

  • 将语料按字符切分，并在单词末尾加以</w>标记。
  • 确定期望的词表大小
  • 统计每两个subword的共现频率，选择共现频率最大的一对subword合并生成新的subword
  • 重复上一步知道subword个数满足期望的词表大小或共线频率最大为1时停止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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)

Byte-level BPE

在Unicode中，初始字符集过大，该算法以一个Byte定义一个subword，再使用BPE来进行迭代

WordPiece

WordPiece算法和BPE基本一致，唯一不同的是选择合并的条件不同，因为BPE按频率选择时，往往频率最大的选择并不唯一，导致一句话变成截然不同的几种分法。所以WordPiece选择极大似然合并后subword的概率比两个分开的subword的概率。

SentencePiece

与WordPiece一致，只是从Word级别变为Sentence级别，因为很多语言的切分并不一定按字符或空格来切分，往往多语言模型采用该算法搭配ULM

ULM

ULM —— Unigram Language Model，与前面的算法不同，ULM按照Unigram初始化词表，然后迭代删除subword直到期望的词表大小。删除的依据是选择删除后对当前LM影响最小的subword，实际使用时通常删除影响最小的一批来提高速度。Loss公式为：
$$
\text { Loss }=-\sum_{i=1}^N \log \left(\sum_{x \in S\left(x_i\right)} p(x)\right)
$$
其中$S$表示词表，$p(x)$为subword x的概率，该算法通常用于SentencePiece