tokenize分类
内容参考了huggingface关于tokenize的文档。
tokenize算法主要有三种粒度，word，subword，character。
word粒度下，文本被划分为单独的词汇，常见的分词方法有空格分隔和基于词典的分词。易于理解，能够保留词汇的完整语义。词汇量大，难以处理未登录词(OOV)和词形变化，可能会导致词汇量爆炸的问题，且可能没办法学习词和词缀之间的关系(如词语的比较级)。例子："This is an example." -> ["This", "is", "an", "example"]。
subword粒度下，将词进一步划分为更小的单元，如词干、前缀、后缀或其他常见的字符序列。常见方法包括BPE，BBPE和WordPiece。能够有效处理未登录词，词汇量较小，适合处理词形变化和复合词。但可能会生成较多的子词，导致tokenizer处理后的序列长度增加，如词“unhappiness”可能被拆分为“un”, “happi”, “ness”三个子词，可能会加剧模型的长距离依赖问题。
character粒度，按英文来说就是英文字母加标点符号等特殊符号。最细粒度的分词方法，不存在未登录词OOV的问题，词汇量最小(对于英文来说)。但序列长度大大增加，可能导致计算复杂性增加，语义信息较为分散。
word粒度有OOV和词表过大的问题，character粒度可以解决这两个问题，但过细也会导致tokenize后的序列过长。所以subword粒度成为现在的主流。
subword还有一个好处，如今模型的词表中有许多国家的语言，词表越来越大，但一些国家使用的符号(如拉丁字母语言)是相同的，subword有许多重合(比如词缀)，能够一定程度上减少词表的大小。
下面介绍几种比较重要的分词算法。
BPE
BPE原本是数据压缩的一种算法，后被用来进行构建词表和tokenize。
首先根据空格划分成word，并在每个词后添加结束符。然后统计所有词的词频。
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}接下来将每个word拆分为character并计算它们的出现次数。初始token将是所有字符和“”标记的集合。
l:7
o:7
w:16
e:17
r:2
n:6
s:9
t:9
i:3
d:3
</w>:16然后寻找最频繁的字符对，合并它们，并一次又一次地执行相同的迭代，直到达到词表大小限制或迭代次数限制。首先是e与s，共同出现了9次。于是变更词表。将e和s的次数减去9，添加新的token es，频率为9。
l:7
o:7
w:16
e:8
r:2
n:6
es:9
t:9
i:3
d:3
</w>:16然后是es与t，也一共出现了9次。
l:7
o:7
w:16
e:8
r:2
n:6
est:9
i:3
d:3
</w>:16之后是est与，也一共出现了9次。
l:7
o:7
w:16
e:8
r:2
n:6
est</w>:9
i:3
d:3
</w>:7为什么需要将结束符也进行合并？这是因为有些后词缀也可能正常出现在单词内部而非结束位置，如estimate中也含有est，但显然不newest中最高级的含义，所以est和est需要单独处理。
随后先合并l和o，共同出现了7次，再合并lo与w，也共同出现了7次。然后合并出现了6次的new，最后合并low与结束符。(过程不再详细描述)
low</w>:5
low:2
w:3
e:2
r:2
new:6
est</w>:9
i:3
d:3
</w>:2最后合并wid与er。
low</w>:5
low:2
wid:3
er</w>:2
new:6
est</w>:9词表构建结束。
BBPE与BPE的区别在于BPE的最小单位是character，而在Unicode流行的现在，BBPE使用字节作为最小处理单位，这使得BBPE可以处理任何语言，包括那些使用多字节字符的语言，如中文、日文和韩文。一般汉字由两个字节组成，所以汉字在预分词中会被分为两个字节的Unicode。
WordPiece
WordPiece是另一种subword方法。每个单词最初是通过将该前缀添加到单词内的所有字符来拆分的。如hug会被拆分为:h,##u,##g。##代表前缀。
WordPiece首先通过训练语料获得或者最初的英文中26个字母加上各种符号以及常见中文字符，这些作为初始词表。通过计算subword的分数来不断合并subword pair。
下面是一个例子。括号中代表单词和词频。
("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)对语料进行拆分。
("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##g" "##s", 5)所以最初的词汇将是
["b", "h", "p", "##g", "##n", "##s", "##u"]。最频繁的pair是##u和##g，共出现20次，若是BPE算法，我们此时应该将u与g合并成一个subword。我们计算pair的分数：
\[
score(p,q)=\frac{count(p,q)}{count(p)·count(q)}
\]
得到分数为1/36，但实际上分数最高的是##g与##s。这是因为u单独出现了非常多次，拉低了分数。所以我们将##gs加入到词表。
Vocabulary: ["b", "h", "p", "##g", "##n", "##s", "##u", "##gs"]
Corpus: ("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##gs", 5)之后根据规则重复。可以看到WordPiece不一定会合并出现频率高的subword pair，而是优先合并关联比较强的词汇，所以一些罕见的词汇很有可能会被完全加入词表，因为词中的序列单独出现的概率很低。而一些常用词缀会被保留下来。
Unigram
和上面两种从基本词汇开始扩大词汇表的方法不同。Unigram从一个较大的词汇表开始，然后从中删除词汇，直到达到所需的词汇表大小。Unigram假设所有词汇都是独立的。
对于词汇表中的每个符号,算法计算如果删除该符号,整体损失会增加多少,并寻找增加最少的符号。这说明如果删除这个词汇，对整体影响很小。
下面是例子。
("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)
Vocab:["h", "u", "g", "hu", "ug", "p", "pu", "n", "un", "b", "bu", "s", "hug", "gs", "ugs"]可以看到词汇表是当前语料库中的所有子串。我们统计他们的频率：
("h", 15) ("u", 36) ("g", 20) ("hu", 15) ("ug", 20) ("p", 17) ("pu", 17) ("n", 16)
("un", 16) ("b", 4) ("bu", 4) ("s", 5) ("hug", 15) ("gs", 5) ("ugs", 5)Unigram使用Viterbi算法来寻找最佳分数。
Character 0 (u): "u" (score 0.171429)
Character 1 (n): "un" (score 0.076191)
Character 2 (h): "un" "h" (score 0.005442)
Character 3 (u): "un" "hu" (score 0.005442)
Character 4 (g): "un" "hug" (score 0.005442)可以看到un与h的概率断崖式下跌，所以unhug应该被分为un和hug。损失函数就是所有概率的负对数和。
"hug": ["hug"] (score 0.071428)
"pug": ["pu", "g"] (score 0.007710)
"pun": ["pu", "n"] (score 0.006168)
"bun": ["bu", "n"] (score 0.001451)
"hugs": ["hug", "s"] (score 0.001701)
------
loss = 10 * (-log(0.071428)) + 5 * (-log(0.007710)) + 12 * (-log(0.006168)) + 4 * (-log(0.001451)) + 5 * (-log(0.001701)) = 169.8计算删除某词汇后整体的损失，来决定是否要删除该词汇。