Tokenization Algorithm

1 BPE

Byte-Pair Encoding (BPE)，一种词表压缩算法，核心思想是合并频繁出现的字符对来创建新的词汇，逐步建立起一个子词的词表。

BPE算法的步骤：
- 将文本数据集中的词汇切分为基础字符（如字母、标点符号等），并为每个基础字符后加上终止符，以表示词的边界。
- 统计所有相邻字符对的频率，并找出出现次数最多的字符对。
- 将最频繁的字符对合并，创建一个新的符号，并且将文本中的这些字符对替换为这个新符号。
- 重复步骤3和步骤4，直到达到预定的词表大小或者没有可以合并的字符对为止。
应用场景：
- 通过字母级别的合并压缩，可以讲单词分割出前缀、后缀、时态、复数等常见的变化。这样，就能很好的压缩词汇表。最直观的例子就是 highest、lowest -> high、low、est，对比的是 high、highest、low、lowest
局限：
- 它过于关注频率最高的对，可能在语义边界上产生不合理的分割。
代码资源：

from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import Whitespace

# 创建一个基本的BPE模型
tokenizer = Tokenizer(BPE(unk_token="[UNK]"))

# 使用 Whitespace作为预处理器
tokenizer.pre_tokenizer = Whitespace()

# 创建一个 BPE trainer，设置vocab_size为5000
trainer = BpeTrainer(vocab_size=5000, special_tokens=["[UNK]", "[CLS]", "[SEP]", "[PAD]", "[MASK]"])

# 指定文件路径列表来训练tokenizer
files = ["your_text_file_1.txt", "your_text_file_2.txt"]
tokenizer.train(files, trainer)

# 保存tokenizer到文件
tokenizer.save("bpe.tokenizer.json")

1.1 Reference

自然语言处理之Subword子词算法 – 标点符
 ChatGPT 举例合并时态例子

2 BBPE

Chatgpt 2
字节级别的合并

BPE的算法最开始的基础词表也可能会很大，比如如果将所有的unicode 字符都放入基础词表，一开始的词表大小就有十几万了。在GPT-2论文中使用了bytes作为基础词表，因此它就可以表示任意单词，并且其基础词表只有256的大小，再加上一个特殊的结束符号，使用50000大小的merge，最终GPT-2的词表大小为50257.（GPT-2在merge的时候还有一些特殊规则，比如不将不同类型的bytes合并等）

由于所有的字符都可以转换成字节序列，所以BBPE的词表中可以包含所有可能的单字节符号，这样就确保了模型不会出现任何未登录词，同时也可以有效地控制词表的规模。

BBPE的主要优点在于，它可以实现真正的无UNK处理，同时也能较好地处理多语言文本。因为它基于字节，所以可以很好地处理任何UTF-8编码的文本，无论这些文本是哪种语言，都不需要做任何特殊处理。

2.1 Reference

子词分词器BPE和WordPiece理解_wordpeice-CSDN博客
 自然语言处理之Subword子词算法 – 标点符

3 WordPiece

Bert
初始化：每个单词最初通过在单词内的所有字符前添加前缀# 来分割例如：“word” 被分割为：

w ##o ##r ##d

合并的规则变化为：

s c o r e = \frac{f r e q o f p a i r}{f r e q o f f i r s t e l e m e n t \times f r e q o f s e c o n d e l e m e n t}

该规则认为合并后出现的频率越高，这个组合就越应该发生；这是合理的
但是为了形成常见后缀、前缀、复数等，添加了限时：那就是本身这种后缀、前缀、复数出现的概率，他们概率越高，说明不被合并的意义越高

4 Unigram Language Model (ULM)

Unigram Language Model是减量法,即先初始化一个大词表，根据评估准则不断丢弃词表，直到满足限定条件。

EM 算法计算子词组合为句子 s 的联合概率，选最大的
删除某个字词，计算所有句子 s 的联合概率 loss 变化了多少
变化不多的甚至更好的就可以删掉了

对于句子 $S$ ， $X = (x_{1}, x_{2}, \dots, x_{m})$ 为句子的一个分词结果，由 $m$ 个子词组成。所以，当前分词下句子 $S$ 的似然值可以表示为：

P (X) = \prod_{i = 1}^{m} P (x_{i})

对于句子 $S$ ，挑选似然值最大的作为分词结果，则可以表示为：

x^{*} = a r g m a x_{x \in U} P (X)

这里 $U (x)$ 包含了句子的所有分词结果。在实际应用中，词表大小有上万个，直接罗列所有可能的分词组合不具有操作性。针对这个问题，可通过维特比算法得到 $x *$ 。

每个字词的概率P(xi)用最大期望的方法计算，假设当前词表V，则M步最大化对象是如下似然函数：

L=∑s=1|D|log(P(X(s)))=∑s=1|D|log(∑x∈U(X(s))P(x))

其中，|D|是语料库中语料数量。上述公式的一个直观理解是，将语料库中所有句子的所有分词组合形成的概率相加。

5 SentencePiece

核心有点：unicode 实现跨越语言、多种字词算法的嵌入，端到端，不假设已经有了基本的字符集，

#待研究数据驱动-SmilesPE