tokenization算法大致经历了从word/char到subword的进化，这一章首先介绍不同的分词粒度，然后对主流的三大subword分词算法进行介绍，配合代码和实例，希望可以对subword算法有一个比较全面的梳理。
分词的目的是将输入文本分成一个个词元，保证 各个词元拥有相对完整和独立的语义 ，以供后续任务（比如学习embedding或者作为高级模型的输入）使用。
首先，最自然的粒度当然是词粒度。词，作为语言最自然的基本单元，在英文等语言中有着天然的空格分隔，但是对于中文等语言可能需要额外的分词算法来进行处理（比如中文的jieba分词）。不过，我们总归是有办法获得各种各样的词的，这并不是一个致命的问题。真正影响词粒度分词算法应用问题主要有：1）词粒度的词表由于长尾效应可能会非常大，包含很多的稀有词，存储和训练的成本都很高，并且稀有词往往很难学好；2）OOV问题，对于词表之外的词无能为力；3）无法处理单词的形态关系和词缀关系：同一个词的不同形态，语义相近，完全当做不同的单词不仅增加了训练成本，而且无法很好的捕捉这些单词之间的关系；同时，也无法学习词缀在不同单词之间的泛化。
那么，一个很自然的想法就是使用字符粒度的词表，这样OOV问题迎刃而解了，但是字符粒度太细了，会造成新的问题：1）无法承载丰富的语义；2）序列长度增长，带来计算成本的增长。
所以，如何结合word和char粒度各自的优势呢？subword分词应运而生，顾名思义，粒度介于char和Word之间， 基本思想为常用词应该保持原状，生僻词应该拆分成子词以共享token压缩空间 ，所以可以较好的平衡词表大小与语义表达能力，比如OOV问题可以通过subword的组合来解决。
目前有三种主流的Subword分词算法，分别是Byte Pair Encoding (BPE), WordPiece和Unigram Language Model。
总结一下，文本的分词粒度：
word：
优点：词的边界和含义得到保留；
缺点：1）词表大，稀有词学不好；2）OOV；3）无法处理单词形态关系和词缀关系
char：
优点：词表极小，比如26个英文字母几乎可以组合出所有词，5000多个中文常用字基本也能组合出足够的词汇；
缺点：1）无法承载丰富的语义；2）序列长度大幅增长；
subword：
可以较好的平衡词表大小与语义表达能力；
核心思想：
从一个基础小词表开始，通过不断合并最高频的连续token对来产生新的token。
具体做法：
输入：训练语料；词表大小V
1.准备基础词表：比如英文中26个字母加上各种符号；
2.基于基础词表将语料拆分为最小单元；
3.在语料上统计单词内相邻单元对的频率，选择频率最高的单元对进行合并；
4.重复第3步直到达到预先设定的subword词表大小或下一个最高频率为1；
输出：BPE算法得到的subword词表
将BPE的思想从字符级别扩展到子节级别 。
优势与劣势：
优势：1）效果与BPE相当，但词表大为减小；2）可以在多语言之间通过字节级别的子词实现更好的共享；3）即使字符集不重叠，也可以通过子节层面的共享来实现良好的迁移。
劣势：1）编码序列时，长度可能会略长于BPE，计算成本更高；2）由byte解码时可能会遇到歧义，需要通过上下文信息和动态规划来进行解码。
典型模型：GPT-2
核心思想：
与BPE类似，也是从一个基础小词表出发，通过不断合并来产生最终的词表。主要的差别在于，BPE按频率来选择合并的token对，而wordpiece按token间的互信息来进行合并。注：互信息，在分词领域有时也被称为凝固度、内聚度，可以反映一个词内部的两个部分结合的紧密程度。
优势与劣势：
优势：可以较好的平衡词表大小和OOV问题；
劣势：可能会产生一些不太合理的子词或者说错误的切分；对拼写错误非常敏感；对前缀的支持不够好；
典型模型：
BERT/DistilBERT/Electra
具体做法：
输入：训练语料；词表大小V
1.准备基础词表：初始化一个很大的词表，比如所有字符+高频ngram，也可以通过BPE算法初始化；
2.针对当前词表，用EM算法估计每个子词在语料上的概率；
3.计算删除每个subword后对总loss的影响，作为该subword的loss；
4.将子词按照loss大小进行排序，保留前x%的子词；注意，单字符不能被丢弃，以免OOV；
5.重复步骤2到4，直到词表大小减少到设定值；
输出：ULM算法得到的subword词表
可见，ULM会倾向于保留那些以较高频率出现在很多句子的分词结果中的子词，因为这些子词如果被删除，其损失会很大。
优势与劣势：
优势：1)使用的训练算法可以利用所有可能的分词结果，这是通过data sampling算法实现的；2）提出一种基于语言模型的分词算法，这种语言模型可以给多种分词结果赋予概率，从而可以学到其中的噪声；3）使用时也可以给出带概率的多个分词结果。
劣势：1）效果与初始词表息息相关，初始的大词表要足够好，比如可以通过BPE来初始化；2）略显复杂。
典型模型：
注意：Unigram is not used directly for any of the models in the transformers, but it’s used in conjunction with SentencePiece.
XLNet/ALBERT/Marian/T5.
SentencePiece，有些文章将其看作一种分词方法，有的地方将其视为一个分词工具包。个人更倾向于后者，但是将其看作一种分词算法也未尝不可（因为不仅是分词算法的集成，还做了很多优化）
多分词粒度：支持BPE、ULM子词算法，也支持char, word分词；
多语言：以unicode方式编码字符 ，将所有的输入（英文、中文等不同语言）都转化为unicode字符，解决了多语言编码方式不同的问题；
编解码的可逆性 ：之前几种分词算法对空格的处理略显粗暴，有时是无法还原的。Sentencepiece显式地将空白作为基本标记来处理，用一个元符号 “▁”（ U+2581 ）转义空白，这样就可以实现简单且可逆的编解码；
无须Pre-tokenization：Sentencepiece可以直接从raw text/setences进行训练，无须Pre-tokenization；
Fast and lightweight；