一、前言

学习huggingface tokenizers 库。首先介绍三大类分词算法：词级、字符级、子词级算法；然后介绍五种常用的子词级（subword ）算法：BPE、BBPE、WordPiece、Unigram、SentencePiece。

二、常用分词算法大类：词级、字符级、子词级

词表通常在模型预训练语料库上训练而成，包括不同的分词方式，例如对 “Don’t you love 🤗 Transformers? We sure do.” 进行分词。

• 词级
  • 直接按空格分：[“Don’t”, “you”, “love”, “🤗”, “Transformers?”, “We”, “sure”, “do.”]，缺点有些词根标点被分到一起了，比如 “Transformers?”
  • 空格+标点（基于规则，比如 spaCy 和 Moses ）：[“Do”, “n’t”, “you”, “love”, “🤗”, “Transformers”, “?”, “We”, “sure”, “do”, “.”]，缺点是词表会巨大，比如Transformer XL用的这种分词方式，词表大小达到了267735，导致embedding矩阵贼大，一般大模型词表没太有超过5w词的。
• 字符级
  • 直接一个字母或者一个汉字作为一个词。缺点是模型更难学习出意义的表示。
• 子词级（结合了字符级+词级的优点）
  • 总直觉：高频词不应被分成子词，低频词应该被进一步拆分，比如dog不拆分，dogs拆分成 dog 和 s。优点是既能降低词汇量，又能根据前后缀学习到语义。
    
  • 不同模型用的subword tokenizer也不同，如图。比如用bert给“Tokenization”分词，会转成小写然后分成“token”和“##ization”俩子词，中午直接变成 ‘[UNK]’；用xlnet就会区分大小写，而且空格也会表示成 “▁”。
    
    BERT分词举例：
    XLNet分词举例：

三、五个子词级分词算法（subword tokenization）

接下来是几个常见的子词级 subword tokenization 算法：BPE、BBPE、WordPiece、Unigram、SentencePiece。

• Byte-Pair Encoding (BPE)：从字母开始，不断找词频最高、且连续的两个token合并（有点霍夫曼树内味儿了），直到达到目标词数。

  • 先用简单或高级的算法比如用空格把句子拆成（单词，词频）的形式，这叫 “pre-tokenization”，比如pre-tokenize之后，得到 ("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5) ；并得到初始词表（base vocabulary） ["b", "g", "h", "n", "p", "s", "u"]，
  • 初始化（单词，词频）序列是 ("h" "u" "g", 10), ("p" "u" "g", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "u" "g" "s", 5)
  • 第一轮计算，发现 u 后面接 g 的次数最多（10+5+5=20次），所以ug合并后加入词表，得到("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)；
  • 第二轮计算，发现 u 后面接 n 的次数最多（12+4=16次），所以un合并后加入词表，得到("h" "ug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("h" "ug" "s", 5)；
  • 第三轮计算，发现 h 后面接 ug 的次数最多（10+5=15次），所以 hug 合并后加入词表，得到("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)；
  • 迭代停止。如果此时对“bug”分词，就得到 “b 和 ug”，对“mug”分词，就得到 “<unk> 和 ug”因为m没在词表里。

  所以，BPE算法得到的最终词表数 = base vocabulary原始词数 + 合并后的词数（可调参数）。比如GPT有 478 base characters 和 训练后的 40000 merges tokens，总词数就是 40478 个。

• Byte-level BPE（BBPE）：utf-8编码中，一个字符就是4bytes，unicode字符就13.8w个，这个算法就是合并的Byte编码

• WordPiece：2012年提出的，BERT、DistilBERT 和 Electra都用的这个。跟BPE差不多，也是初始化字符词表，逐步学习给定数量的合并规则。区别是合并时，计算合并后的语言模型似然有没有增加。

  • 其中，句子 $S=(w_1,w_2,...,w_n)$ 由n个独立子词 $t_i$ 组成，则改句子语言模型似然为 $logP(S)=\sum logP(t_i)$
  • 把x和y两个词合并成z，那么该句似然值变化为：
    $logP(t_z)-(logP(t_x)+logP(t_y))=\frac{log(P(t_z))}{P(t_x)P(t_y)}$。也就是说，WordPiece合并时不光考虑“得”，还考虑“失”。

• Unigram：跟BPE相反，Unigram是从大到小的过程，先初始化一个大词表，然后逐步精简掉使loss损失最小的词。一般跟sentencepiece结合起来用。

• SentencePiece：上面这些算法都假设以空格分割单词，但中文日文等并不是。为了解决这个问题，SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (Kudo et al., 2018) 将所有语言一视同仁，把空格也包含到字符集里，再用BPE或Unigram构造词表。

  • 比如XLNetTokenizer在编码时就包含 “▁”，解码时再还原成空格。
  • 库中所有用 SentencePiece 的模型都与 unigram 结合来用。比如 ALBERT、XLNet、Marian 和 T5。

官方文档：https://huggingface.co/docs/transformers/tokenizer_summary#wordpiece