上一节中我们说了三个tokenize不同粒度：word/subword/char，现在最常用的是subword字词的模式，今天就和大家分享下字词的三个经典的算法：WordPiece、BPE/BBPE和unigram。
subword字词的本质是在既不要word那么多，也不要char那么细，所以基本是在char基础上做合并，但是不要合并到word的程度。
1. BPE/BBPE
Byte Pair Encoding (BPE) 是一种用于文本数据压缩和子词分割的算法。BPE最初在数据压缩中被提出，但在自然语言处理（NLP）领域中也被广泛应用，特别是在神经机器翻译和预训练语言模型中。
BPE 的基本思想是反复地找到文本中频率最高的相邻符号对（byte pair），然后将这些符号对合并成一个新的符号。这个过程会重复进行，直到达到预设的合并次数或者再没有可以合并的符号对。
算法步骤
- 初始化：将输入文本按字符级别进行分割，每个字符（包括空格）视为一个独立的符号。
- 统计频率：统计所有相邻符号对的出现频率。
- 合并频繁对：找到出现频率最高的相邻符号对，并将其合并为一个新符号。
- 迭代：重复步骤2和3，直到达到预设的合并次数或者再没有可以合并的符号对。
优点
- 降低词汇表大小：通过合并高频相邻字符对，BPE可以有效减少词汇表的大小。
- 处理未登录词：由于BPE使用子词级别，因此可以更好地处理未登录词（OOV）。
- 提高训练效率：较小的词汇表和子词级别的建模可以提高模型的训练效率和性能。
假设我们有一段英文文本：“high higher highest”。我们希望通过BPE进行处理，以下是具体步骤：
Step 1: 初始化
将文本按字符级别进行分割：
h i g h h i g h e r h i g h e s t
Step 2: 统计频率
'h i': 3, 'i g': 3, 'g h': 3, 'h e': 2, 'e r': 1, 'e s': 1, 's t': 1
Step 3: 合并频率最高的相邻符号对
合并 'h i'：
hi g h hi g h e r hi g h e s t
Step 4: 重复步骤2和3
继续统计剩余的频率：
'hi g': 3, 'g h': 3, 'h e': 2, 'e r': 1, 'e s': 1, 's t': 1
合并 'hi g'：
hig h hig h e r hig h e s t
继续：
'high': 3, 'h e': 2, 'e r': 1, 'e s': 1, 's t': 1
合并 'hig h'：
high high e r high e s t
最终词汇表：
{ 'h', 'i', 'g', 'e', 'r', 's', 't', 'hi', 'hig', 'high' }
再来看下中文的示例，我们有一段中文文本：“学习 学习 学习进步”。我们希望通过BPE进行处理，以下是具体步骤：
Step 1: 初始化
将文本按字符级别进行分割：
学 习 学 习 学 习 进 步
Step 2: 统计频率
'学 习': 3, '习 进': 1, '进 步': 1
Step 3: 合并频率最高的相邻符号对
合并 '学 习'：
学习 学习 学习 进 步
Step 4: 重复步骤2和3
继续统计剩余的频率：
'学习': 3, '习 进': 1, '进 步': 1
合并 '学习'：
学习 学习 学习进 步
继续：
'学习进': 1, '进 步': 1
合并 '学习进'：
学习 学习 学习进步
最终词汇表：
{ '学', '习', '进', '步', '学习', '学习进', '学习进步' }
而BBPE（Byte-Level Byte Pair Encoding）是一种改进的 BPE 算法，主要特点是它在字节级别进行操作，而不是在字符级别。这种方法特别适合处理多语言文本和非标准字符集，因为它直接在字节序列上进行操作，从而避免了字符编码问题。
BBPE 的基本思想与传统 BPE 类似，但操作单位是字节而不是字符。BBPE 通过反复合并高频字节对来构建词汇表。
Byte-Level Byte Pair Encoding (BBPE) 和 Byte Pair Encoding (BPE) 都是用于子词分割和词汇表构建的算法，但它们在处理文本的细粒度上有所不同。BBPE 在字节级别进行操作，而BPE在字符级别进行操作。下面是BBPE相对于BPE的一些主要优势：
1. 处理多语言文本和特殊字符
BBPE: 由于在字节级别进行操作，BBPE 不依赖于特定的字符编码。这使得它能够更好地处理包含多种语言和特殊字符的混合文本。例如，一些语言中的字符可能会占用多个字节，BBPE 可以统一处理这些字符。
BPE: 由于在字符级别进行操作，BPE 需要处理不同字符编码的问题，特别是在处理多语言文本时。例如，在UTF-8编码下，某些字符可能占用1到4个字节，这可能会导致复杂性上升。
2. 避免字符编码问题
BBPE: 直接在字节序列上操作，完全避免了字符编码和解码的问题。这对于处理非标准字符集或编码格式非常有用。
BPE: 需要处理字符编码和解码的问题，并且在处理非标准字符集时可能会遇到挑战。
3. 更精细的子词建模
BBPE: 由于在字节级别操作，BBPE 可以实现更细粒度的子词分割。这对于需要非常精细的文本处理任务，如细粒度的文本生成和翻译，非常有用。
BPE: 在字符级别操作，子词分割的粒度相对较粗，可能不适用于需要非常精细的文本处理任务。
4. 统一处理不同语言的字符
BBPE: 可以统一处理不同语言的字符。无论是拉丁字母、中文字符还是其他语言字符，都可以作为字节序列进行处理。
BPE: 在处理不同语言字符时，需要考虑不同字符集的编码方式，这增加了处理复杂性。
现在很多大语言模型都采用BBPE分词，如GPT，qwen2等
2. WordPiece
WordPiece 是另外一种常见的子词分割方法，特别是在自然语言处理（NLP）任务中用于词汇表构建和处理未登录词（OOV）。它被广泛应用于许多预训练语言模型中，如 BERT/DistilBERT/Electra。
WordPiece 的基本思想与 BPE 类似，但在合并策略上有所不同。WordPiece 通过最大化语言模型的似然（likelihood）来确定最优的子词分割方式。它通过逐步合并频繁的子词对来构建词汇表。
它每次合并的两个字符串A和B，应该具有最大的P(AB)/P(A)P(B)值。合并AB之后，所有原来切成A+B两个tokens的就只保留AB一个token，整个训练集上最大似然变化量与P(AB)/P(A)P(B) 成正比。
实际计算中P(AB)=AB合并token出现的频次，P(A)则A出现的频次，P(B)则B出现的频次
3. Unigram
与BPE或者WordPiece不同，Unigram的算法思想是从一个巨大的词汇表出发，再逐渐删除其中对总体损失最小的词汇，直到size满足预定义。
以下是一个详细的例子，用于说明Unigram分词算法中词典的生成过程，并包括概率的计算：
1. 初始化阶段
假设我们有以下的小型语料库，并给出每个单词的出现频次：
- hug: 10次
- pug: 5次
- pun: 12次
- bun: 4次
hugs: 5次
首先，我们列出所有可能的子词（或称为tokens），构建初始词汇表。这个列表可能包括单个字符以及更长的子串。例如：
h, u, g, hu, ug, p, pu, n, un, b, bu, s, hug, gs, ugs 等
2. 估计阶段
接下来，我们计算每个子词的概率。概率是子词在语料库中出现的频次除以语料库中所有单词的总字符数。以"ug"为例，它出现了20次（在"hug"、"pug"、"hugs"和"ugs"中各出现一次，但注意"ugs"中的"ug"只计算一次），如果语料库总字符数为210，则：
P(ug) = 20 / 210
类似地，我们可以计算其他子词的概率，如：
P(h) = 15 / 210（在"hug"、"hugs"中出现）
- P(u) = 36 / 210（在多个单词中出现）
- ...以此类推
3. 优化阶段
在优化阶段，Unigram算法会尝试移除那些对语料库整体概率贡献最小的子词。这通常意味着移除那些出现频次低、概率小的子词。
例如，假设经过计算，"ugs"这个子词的概率非常低，因为它只在少数几个单词中出现，且总频次很低。算法可能会选择移除"ugs"，因为它对整体概率的贡献很小。
移除子词后，算法会重新计算剩余子词的概率，并继续寻找可以移除的子词，直到达到预定的词汇表大小或满足其他停止条件。
4. 结束阶段
最终，经过多轮迭代和优化，我们会得到一个精简且高效的词汇表，其中包含了对语料库整体概率贡献最大的子词。
请注意，上述例子是为了说明Unigram分词算法的原理而简化的。在实际应用中，语料库通常更加庞大和复杂，而且算法的实现也会涉及更多的细节和优化。
另外，值得注意的是，Unigram分词算法在实际应用中可能不会直接移除概率最低的子词，而是会考虑移除后对整个语料库概率分布的影响，这通常通过计算移除某个子词后语料库损失的变化来实现。损失函数的设计是Unigram分词算法中的一个关键部分，它决定了哪些子词应该被保留在词汇表中。
4.总结
- WordPiece、BPE/BBPE最小字词进行合并最终字词，BPE/BBPE直接采用词频判断合并规则而WordPiece采用最大似然的方式
- unigram采用从最大的字词集合里移除那些对语料库整体概率贡献最小的子词
