tokenization

This unit was inspired by Andrej Karpathy's video on tokenization：https://www.youtube.com/watch?v=zduSFxRajkE

• 原始文本通常是Unicode strings
• 语言模型会对 token 序列（通常用整数索引表示）赋予一个概率分布
• 所以我们需要一个程序 将字符串编码成token，再将他们解码回字符串
• 词汇表大小就是一个 token值（通常是一个整数索引）的数量

例子：https://tiktokenizer.vercel.app/?encoder=gpt2

观察结果：

1. 空格也会被考虑进去作为一个token

2. 位于句首的单词和位于句中的单词表示方式不同（例如，world world）

3. 数字会被拆分为每几位一组进行标记化处理

4. tokenization 是可逆的

基于字符分词

Unicode字符串是Unicode字符的序列。

每个字符都可以转换成一个整数，称为码点。

你可以定义一个分词器将每个字符映射到一个码点。

但是这样做有什么问题吗？

1. 词汇表非常大

2. 许多字符非常罕见（例如🌍），这是对词汇表的低效使用。

基于字节分词

Unicode字符串可以用字节序列来表示，因为每个字符串都可以直接转换成字节。

这样转换成字节后，所有的索引值现在都会在0到255之间，因为根据定义，一个字节总共有256个可能的值。

基于字节的分词解决了基于字符分析的缺点

但是基于字节的编码处理长序列有什么问题？

1. 它的压缩比是 1byte per token，这会导致序列非常长，而注意力机制在序列长度上是二次方复杂度，所以效率会很糟糕

基于单词分词

存在的问题：

1. 词汇数量庞大（例如对于 Unicode 字符而言）

2. 许多词汇出现频率极低，模型难以从中学习到有效信息。

3. 这种方式显然无法提供固定的词汇表规模，因为对于一个新的输入，你可能会得到一个你以前从未见过的片段

4. 我们在训练过程中未曾见过的新词会被赋予一个特殊的 UNK 标记（"Unknown"（未知）的缩写），这种处理方式不够理想，还可能干扰困惑度（perplexity）的计算。

基于字节对（BPE）分词

首先将字符串转换成字节序列，然后不断合并出现频率最高的相邻标记对。

一、训练阶段：构建 BPE 分词词典

Step 1：初始化词汇表

将语料中所有文本拆分为最小单元，并统计每个最小单元的出现频率

Step 2：统计所有字符对的频率

遍历初始化后的所有词序列，统计相邻字符对的出现次数。

Step 3：合并频率最高的字符对

从所有字符对中选择频率最高的一对，将其合并为一个新的子词，并将该子词加入词汇表。

Step 4：更新词汇表和字符对统计

合并后，需要重新遍历所有词序列，将其中原字符对替换为新子词，并重新统计所有相邻字符对的频率（包括 “新子词与其他单元” 的新字符对）。

Step 5：重复合并直到满足停止条件

重复执行 Step 2~Step 4，每次合并当前频率最高的字符对，直到达到以下任一停止条件：

1. 词汇表大小达到预设阈值（如预设词汇表包含 30000 个子词，合并到该规模为止）；
2. 合并次数达到预设上限（如固定执行 10000 次合并）；
3. 最高字符对的频率低于预设阈值（当高频对已合并完，低频对无需再合并）。

Step 6：输出 BPE 词典和合并规则

训练结束后，输出两个核心文件：

1. BPE 词汇表：包含所有初始字符和合并生成的子词，以及它们的总频率；
2. 合并规则列表：按合并顺序记录每次合并的字符对（如(l,o)→lo、(lo,w)→low等），用于推理阶段的分词。

二、推理阶段：对新文本执行分词

Step1：初始化新文本

将新文本拆分为单个词，每个词按 “字符 +</w>” 拆分为最小单元序列（如 “newer” 拆分为n e w e r </w>）。

Step2：按合并规则尝试合并

遍历训练阶段生成的 “合并规则列表”（按合并顺序，从早到晚），对当前词的字符序列中，检查是否存在规则中的字符对：

• 若存在，则将该字符对合并为对应的子词；
• 若不存在，则跳过该规则。

Step3：输出最终子词序列

当所有合并规则遍历完毕，当前词的序列即为最终的子词分词结果。

• 例：对新词 “newer”，若合并规则包含(n,e)→ne、(ne,w)→new、(w,e)→we、(we,r)→wer，则最终分词结果可能为new er </w>或newer </w>（取决于规则是否包含(new,er)→newer）。