LLM 大语言模型 Tokenization 分词方法原理：WordPiece、BPE 与 BBPE

1. 计算初始词表：通过训练语料获得或者最初的英文中 26 个字母加上各种符号以及常见中文字符，这些作为初始词表。
2. 计算合并分数：对训练语料拆分的多个子词单元通过合并规则计算合并分数。
3. 合并分数最高的子词对：选择分数最高的子词对，将它们合并成一个新的子词单元，并更新词表。
4. 重复合并步骤：不断重复步骤 2 和步骤 3，直到达到预定的词表大小、合并次数，或者直到不再有有意义的合并。
5. 分词：使用最终得到的词汇表对文本进行分词。

简单举例：

我们有以下的训练语料中的样例，括号中第 2 位为在训练语料中出现的频率：

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

我们对其进行拆分为带前缀的形式：

("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##g" "##s", 5)

所以这些样例的初始词表将会是：

["b", "h", "p", "##g", "##n", "##s", "##u"]

接下来重要的一步进行计算合并分数，也称作互信息（信息论中衡量两个变量之间的关联程度）。简单来说就是以下公式来计算：

score = (freq_of_pair) / (freq_of_first_element × freq_of_second_element)
分数 = 合并 pair 候选的频率 / (第一个元素的频率 × 第二个元素的频率)

对于上述样例中这个 pair("##u", "##g") 出现的频率是最高的 20 次，但是 "##u" 出现的频率是 36 次， "##g" 出现的频率是 20 次，所以这个 pair("##u", "##g") 的分数是 20/(3620) = 1/36。同理计算这个 pair("##g", "##s") 的分数为 5/(205) = 1/20，所以最先合并的 pair 是 ("##g", "##s") → ("##gs")。此时词表和拆分后的的频率将变成以下：

Vocabulary: ["b", "h", "p", "##g", "##n", "##s", "##u", "##gs"]
Corpus: ("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##gs", 5)

重复上述的操作，直到达到你想要的词表的大小。

代码实现：

用一些包含中英文的文本作为训练语料，因为英文有天然的分隔符，所以在这个例子中，中文已经进行了分词：

from collections import defaultdict

sentences = [
    "我",
    "喜欢",
    "吃",
    "苹果",
    "他",
    "不",
    "喜欢",
    "吃",
    "苹果派",
    "I like to eat apples",
    "She has a cute cat",
    "you are very cute",
    "give you a hug",
]

# 构建频率统计
def build_stats(sentences):
    stats = defaultdict(int)
    for sentence in sentences:
        symbols = sentence.split()
        for symbol in symbols:
            stats[symbol] += 1
    return stats

stats = build_stats(sentences)
print("stats:", stats)

alphabet = []
for word in stats.keys():
    if word[0] not in alphabet:
        alphabet.append(word[0])
    for letter in word[1:]:
        if f"##{letter}" not in alphabet:
            alphabet.append(f"##{letter}")

alphabet.sort()
# 初始词表
vocab = alphabet.copy()
print("alphabet:", alphabet)

根据初始词表拆分每个词：

splits = {
    word: [c if i == 0 else f"##{c}" for i, c in enumerate(word)]
    for word in stats.keys()
}
print("splits:", splits)

根据上述提到的计算互信息的分数公式进行计算：

def compute_pair_scores(splits):
    letter_freqs = defaultdict(int)
    pair_freqs = defaultdict(int)
    for word, freq in stats.items():
        split = splits[word]
        if len(split) == 1:
            letter_freqs[split[0]] += freq
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i + 1])
            letter_freqs[split[i]] += freq
            pair_freqs[pair] += freq
        letter_freqs[split[-1]] += freq

    scores = {
        pair: freq / (letter_freqs[pair[0]] * letter_freqs[pair[1]])
        for pair, freq in pair_freqs.items()
    }
    return scores

pair_scores = compute_pair_scores(splits)
for i, key in enumerate(pair_scores.keys()):
    print(f"{key}: {pair_scores[key]}")
    if i >= 5:
        break

我们需要的是将分数最高的进行合并然后开始循环迭代，看一看分数最高的 pair（子词对）：

best_pair = ""
max_score = None
for pair, score in pair_scores.items():
    if max_score is None or max_score < score:
        best_pair = pair
        max_score = score

print(best_pair, max_score)

结果为 ('S', '##h') 1.0，所以最先合成的就是 ('S', '##h') → '##Sh'，合并的函数如下：

def merge_pair(a, b, splits):
    for word in stats:
        split = splits[word]
        if len(split) == 1:
            continue
        i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                merge = a + b[2:] if b.startswith("##") else a + b
                split = split[:i] + [merge] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits

最后就是一直进行循环迭代，直到 vocab 达到了我们想要的数量：

vocab_size = 50
while len(vocab) < vocab_size:
    scores = compute_pair_scores(splits)
    best_pair, max_score = "", None
    for pair, score in scores.items():
        if max_score is None or max_score < score:
            best_pair = pair
            max_score = score
    splits = merge_pair(*best_pair, splits)
    new_token = (
        best_pair[0] + best_pair[1][2:]
        if best_pair[1].startswith("##")
        else best_pair[0] + best_pair[1]
    )
    vocab.append(new_token)

print("vocab:", vocab)

上述就是 WordPiece 分词方法的代码实现。一般来说最后会在词表中加上一些特殊词汇，以及英文中 26 个字母加上各种符号以及常见中文字符。只需要添加特殊词汇：

all_vocab = vocab + ["[PAD]", "[UNK]", "[CLS]", "[SEP]", "[MASK]"] + other_alphabet

在大语言模型时代，最常用的分词方法是 Byte-Pair Encoding (BPE) 和 Byte-level BPE(BBPE)。Byte-Pair Encoding (BPE) 最初是一种文本压缩算法在 15 年被引入到 NLP 用于分词，在训练 GPT 时被 OpenAI 用于 tokenization，后续好多模型 GPT、RoBERTa 等都采用了这种分词方法。Byte-level BPE(BBPE) 是于 19 年在 BPE 的基础上提出以 Byte-level(字节) 为粒度的分词方法，目前 GPT2、BLOOM、Llama、Falcon 等采用的是该分词方法。

3.2 Byte-Pair Encoding (BPE)

Byte-Pair Encoding (BPE) 核心思想是逐步合并出现频率最高的子词对而不是像 Wordpiece 计算合并分数，从而构建出一个词汇表。以下是核心步骤：

• 计算初始词表：通过训练语料获得或者最初的英文中 26 个字母加上各种符号以及常见中文字符，这些作为初始词表。
• 构建频率统计：统计所有子词单元对（两个连续的子词）在文本中的出现频率。
• 合并频率最高的子词对：选择出现频率最高的子词对，将它们合并成一个新的子词单元，并更新词汇表。
• 重复合并步骤：不断重复步骤 2 和步骤 3，直到达到预定的词汇表大小、合并次数，或者直到不再有有意义的合并。
• 分词：使用最终得到的词汇表对文本进行分词。

简单的代码实现：

用一些包含中英文的文本作为训练语料：

sentences = [
    "我",
    "喜欢",
    "吃",
    "苹果",
    "他",
    "不",
    "喜欢",
    "吃",
    "苹果派",
    "I like to eat apples",
    "She has a cute cat",
    "you are very cute",
    "give you a hug",
]

# 构建频率统计
def build_stats(sentences):
    stats = defaultdict(int)
    for sentence in sentences:
        symbols = sentence.split()
        for symbol in symbols:
            stats[symbol] += 1
    return stats

stats = build_stats(sentences)
print("stats:", stats)

alphabet = []
for word in stats.keys():
    for letter in word:
        if letter not in alphabet:
            alphabet.append(letter)
alphabet.sort()

# 初始词表
vocab = alphabet.copy()
print("alphabet:", alphabet)

根据初始词表拆分每个词，计算左右 pair(子词对) 出现的频率：

splits = {word: [c for c in word] for word in stats.keys()}
print("splits:", splits)

def compute_pair_freqs(splits):
    pair_freqs = defaultdict(int)
    for word, freq in stats.items():
        split = splits[word]
        if len(split) == 1:
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i + 1])
            pair_freqs[pair] += freq
    return pair_freqs

pair_freqs = compute_pair_freqs(splits)

for i, key in enumerate(pair_freqs.keys()):
    print(f"{key}: {pair_freqs[key]}")
    if i >= 5:
        break

然后开始循环迭代找到出现频率最高的 pair(子词对)：

best_pair = ""
max_freq = None
for pair, freq in pair_freqs.items():
    if max_freq is None or max_freq < freq:
        best_pair = pair
        max_freq = freq

print(best_pair, max_freq)

结果为 [('喜', '欢') 2]，所以最先合成的就是 ('喜', '欢') → '喜欢'，然后合并的函数如下：

def merge_pair(a, b, splits):
    for word in stats:
        split = splits[word]
        if len(split) == 1:
            continue

        i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                split = split[:i] + [a + b] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits

最后就是一直进行循环直到 vocab 达到了我们想要的数量：

merges = {}
vocab_size = 50

while len(vocab) < vocab_size:
    pair_freqs = compute_pair_freqs(splits)
    best_pair = ""
    max_freq = None
    for pair, freq in pair_freqs.items():
        if max_freq is None or max_freq < freq:
            best_pair = pair
            max_freq = freq
    splits = merge_pair(*best_pair, splits)
    merges[best_pair] = best_pair[0] + best_pair[1]
    vocab.append(best_pair[0] + best_pair[1])

print("merges:", merges)
print("vocab:", vocab)

再加上一些特殊词汇和其他词汇：

all_vocab = vocab + ["[PAD]", "[UNK]", "[BOS]", "[EOS]"] + other_alphabet

上述就是 BPE 的代码实现。BPE 理论上还是会出现 OOV 的，当词汇表的大小受限时，一些较少频繁出现的子词和没有在训练过程中见过的子词，就会无法进入词汇表出现 OOV。

3.3 Byte-level BPE(BBPE)

基础知识：

• Unicode：Unicode 是一种字符集，旨在涵盖地球上几乎所有的书写系统和字符。它为每个字符分配了一个唯一的代码点（code point）用于标识字符。
• UTF-8：UTF-8（Unicode Transformation Format-8）是一种变长的字符编码方案，它将 Unicode 中的代码点转换为字节序列。UTF-8 的一个重要特点是它是向后兼容 ASCII 的。
• Byte(字节)：计算机存储和数据处理时，字节是最小的单位。一个字节包含 8 个(Bit) 二进制位，每位的不同排列和组合可以表示不同的数据，所以一个字节能表示的范围是 256 个。

BBPE 原理：

Byte-level BPE(BBPE) 和 Byte-Pair Encoding (BPE) 区别就是 BPE 是最小词汇是字符级别，而 BBPE 是字节级别的，通过 UTF-8 的编码方式这一个字节的 256 的范围，理论上可以表示这个世界上的所有字符。

所以实现的步骤和 BPE 就是实现的粒度不一样，其他的都是一样的：

• 初始词表：构建初始词表，包含一个字节的所有表示 (256)。
• 构建频率统计：统计所有子词单元对（两个连续的子词）在文本中的出现频率。
• 合并频率最高的子词对：选择出现频率最高的子词对，将它们合并成一个新的子词单元，并更新词汇表。
• 重复合并步骤：不断重复步骤 2 和步骤 3，直到达到预定的词汇表大小、合并次数，或者直到不再有有意义的合并。
• 分词：使用最终得到的词汇表对文本进行分词。

简单代码实现：

from collections import defaultdict

sentences = [
    "我",
    "喜欢",
    "吃",
    "苹果",
    "他",
    "不",
    "喜欢",
    "吃",
    "苹果派",
    "I like to eat apples",
    "She has a cute cat",
    "you are very cute",
    "give you a hug",
]

# 构建初始词汇表，包含一个字节的 256 个表示
initial_vocab = [bytes([byte]) for byte in range(256)]
vocab = initial_vocab.copy()
print("initial_vocab:", initial_vocab)

# 构建频率统计
def build_stats(sentences):
    stats = defaultdict(int)
    for sentence in sentences:
        symbols = sentence.split()
        for symbol in symbols:
            stats[symbol.encode("utf-8")] += 1
    return stats

stats = build_stats(sentences)

splits = {word: [byte for byte in word] for word in stats.keys()}

def compute_pair_freqs(splits):
    pair_freqs = defaultdict(int)
    for word, freq in stats.items():
        split = splits[word]
        if len(split) == 1:
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i + 1])
            pair_freqs[pair] += freq
    return pair_freqs

pair_freqs = compute_pair_freqs(splits)

def merge_pair(pair, splits):
    merged_byte = bytes(pair)
    for word in stats:
        split = splits[word]
        if len(split) == 1:
            continue
        i = 0
        while i < len(split) - 1:
            if split[i:i+2] == pair:  # 检查分割中是否有这对字节
                split = split[:i] + [merged_byte] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits

vocab_size = 50
while len(vocab) < vocab_size:
    pair_freqs = compute_pair_freqs(splits)
    best_pair = ()
    max_freq = None
    for pair, freq in pair_freqs.items():
        if max_freq is None or max_freq < freq:
            best_pair = pair
            max_freq = freq
    splits = merge_pair(best_pair, splits)
    merged_byte = bytes(best_pair)

print("vocab:", vocab)

为什么 BBPE 不会出现 OOV 问题：

初始的词表里有 256 个表示，涵盖了所有可能的字节值。通过上述的方式其实是在一直根据训练语料循环迭代合成子词或者词，最后形成词表。比如'苹果'通过 UTF-8 进行编码后为 \xe8\x8b\xb9\xe6\x9e\x9c，如果词表里面有，那'苹果'就通过词表映射成了 1 个表示，准确来说是 1 个 token；如果词表里没有，那就用 256 中的字节序列来表示'苹果'这个词，那就是 6 个 token。在先前的各种分词方法中，如果词典里没有'苹果'这个词，也没有'苹'，'果'这样的子词的话，那就变成了 [UNK]。所以在现在的大模型中，以 Byte-level BPE(BBPE) 这种方式进行分词是不会出现 OOV，但词表中如果没有 word 级别的词的话，一些中英文就会分词分的很细碎，比如 Llama 在中文上就会把一些词分成多个 token 其实就是 UTF-8 后的中文编码，对编码效率以及语义会有影响，于是出现了一些扩充 Llama 中文词表的工作。

三种分词方法对比总结：

工程实践：

上述分词算法在工程上实现一般使用 SentencePiece 工具包，谷歌在这个包中实现了上述的一系列算法。在实际开发中，通常直接使用 HuggingFace Transformers 库提供的 Tokenizer 类，它们底层封装了这些算法的实现细节，开发者只需关注配置参数如 vocab_size、bos_token、eos_token 等即可。后续也可以在此基础上进行自定义词表的扩充工作以适应特定领域的需求。