Byte Pair Encoding (BPE) 分词算法详解与代码实现

2.2 应用阶段：分词

在应用阶段，BPE 使用训练好的词汇表将新输入的文本进行分词。具体步骤如下：

1. 单词拆分为字符：
   • 对于输入单词（如 'lowest'），先将其拆分为字符序列并添加词尾标记：l o w e s t </w>。
2. 贪心合并：
   • 根据训练阶段生成的词汇表，依次尝试合并字符对，优先选择词汇表中最长的子词单元。例如：
     • 检查 l o，发现 lo 在词汇表中，合并为 lo w e s t </w>。
     • 检查 lo w，发现 low 在词汇表中，合并为 low e s t </w>。
     • 检查 e s，不在词汇表中，继续检查 e s t，不在词汇表中，最终结果可能是 low e s t </w>。
3. 输出子词序列：
   • 最终输出分词结果：[low, e, s, t]，作为模型的输入 token。

三、BPE 的数学与统计基础

BPE 的核心是基于频率的贪心算法，但其背后蕴含了一些统计学和信息论的原理：

• 信息压缩：通过合并高频字符对，BPE 减少了表示文本所需的 token 数量，从而降低了模型的计算复杂度和内存需求。
• 最大似然估计：合并频率最高的字符对可以看作是对语料库中子词分布的一种近似估计，试图找到最常见的模式。
• 子词粒度平衡：BPE 通过控制词汇表大小，平衡了字符级别（粒度太细）和单词级别（粒度太粗）之间的折中。

假设语料库大小为 N 个单词，初始字符集合为 C，每次合并会减少 token 数量，最终词汇表大小 V 是超参数。合并次数 K=V−|C| 决定了算法的复杂度，通常为 O(N·K)。

四、BPE 的优点与局限性

4.1 优点

1. 解决 OOV 问题：
   • 通过子词单元，BPE 可以表示任何新词。例如，'unseen' 如果不在词汇表中，可以分解为 un 和 seen，甚至进一步分解为字符。
2. 语言无关性：
   • BPE 不依赖特定语言的词典，适用于多语言场景，尤其在低资源语言中表现出色。
3. 灵活性：
   • 通过调整词汇表大小，可以控制分词的粒度，适应不同任务需求。
4. 高效性：
   • 训练和分词过程计算开销较低，适合大规模语料库。

4.2 局限性

1. 缺乏语义信息：
   • BPE 完全基于频率统计，不考虑词的语义或语法。例如，'playing' 可能被拆为 play 和 ing，但对模型理解词性无直接帮助。
2. 不可逆性：
   • 分词后的子词序列无法完美还原原始文本（除非保留额外信息），可能影响生成任务。
3. 过度拆分或合并：
   • 词汇表大小选择不当可能导致问题：过小则常见词被拆散，过大则新词处理能力下降。

五、在深度学习中的应用

BPE 在现代深度学习模型中广泛应用，尤其是在 Transformer 架构的语言模型中：

1. 神经机器翻译：
   • Sennrich 等人在 NMT 中首次使用 BPE，通过子词表示提高了翻译质量，尤其是在处理形态丰富的语言（如德语、俄语）时。
2. 预训练语言模型：
   • GPT 系列使用 BPE 构建词汇表，词汇表大小通常在 50,000 左右。BERT 使用 WordPiece（BPE 的变种），而 RoBERTa 等也依赖类似技术。
3. 多语言模型：
   • XLM-R 和 mBART 使用 BPE 在多语言语料上训练统一的词汇表，支持跨语言迁移学习。

例如，在 GPT 中，输入文本 'The quick brown fox' 可能被 BPE 分词为：

[The, qu, ick, br, own, f, ox]

这些子词被映射为 token ID，输入到模型中。

六、BPE 的变种与改进

BPE 衍生出了一些改进版本，解决了部分局限性：

1. WordPiece：
   • 用于 BERT，基于最大化似然概率而非纯频率选择子词。
2. Unigram Language Model：
   • 用于 SentencePiece，结合语言模型概率进行子词选择，支持无空格语言（如中文、日文）。
3. BPE-Dropout：
   • 在训练时随机丢弃某些合并操作，增强模型对分词变体的鲁棒性。

七、总结

Byte Pair Encoding (BPE) 是一种简单而强大的分词算法，通过迭代合并高频字符对，从字符级别逐步构建子词词汇表。它在深度学习中解决了开放词汇问题，提高了模型对新词和多语言的支持能力。尽管存在语义缺失等局限性，其高效性和灵活性使其成为 NLP 领域的标配工具。对于深度学习研究者而言，理解 BPE 的原理和实现细节，不仅有助于优化分词策略，还能启发对预处理和模型设计的深入思考。

未来，随着语言模型的发展，BPE 可能会进一步与语义信息结合，或被更智能的分词方法取代。但在当下，它仍是连接原始文本与神经网络的重要桥梁。

代码实现

提供使用 Python 实现的 BPE 训练和应用代码，并详细解释每个部分的功能。代码将包括注释以便深度学习研究者理解其工作原理。

BPE 训练和应用代码

以下是完整的实现，分为训练阶段和应用阶段：

# 导入所需库
from collections import defaultdict, Counter
import re

# BPE 训练函数
def train_bpe(corpus, vocab_size=1000):
    """
    训练 BPE 模型，生成词汇表
    :param corpus: 输入语料库（单词列表）
    :param vocab_size: 目标词汇表大小
    :return: 词汇表（子词集合）
    """
    # 步骤 1：初始化单词为字符序列，添加词尾标记 </w>
    word_freq = Counter(corpus)
    vocab = set()
    word_splits = {}
    for word in word_freq:
        chars = list(word) + ['</w>']
        word_splits[word] = chars
        vocab.update(chars)

    # 步骤 2：迭代合并频率最高的字符对
    while len(vocab) < vocab_size:
        pair_freq = defaultdict(int)
        for word, freq in word_freq.items():
            chars = word_splits[word]
            for i in range(len(chars)-1):
                pair = (chars[i], chars[i+1])
                pair_freq[pair] += freq

        if not pair_freq:
            break

        # 找到频率最高的字符对
        best_pair = max(pair_freq, key=pair_freq.get)
        new_token = ''.join(best_pair)

        # 步骤 3：更新所有单词的分割，合并 best_pair
        for word in word_freq:
            chars = word_splits[word]
            i = 0
            new_chars = []
            while i < len(chars):
                if i < len(chars)-1 and (chars[i], chars[i+1]) == best_pair:
                    new_chars.append(new_token)
                    i += 2
                else:
                    new_chars.append(chars[i])
                    i += 1
            word_splits[word] = new_chars

        vocab.add(new_token)
    return vocab

# BPE 分词函数
def apply_bpe(word, vocab):
    """
    对单个单词应用 BPE 分词
    :param word: 输入单词
    :param vocab: 训练好的词汇表
    :return: 分词后的子词列表
    """
    # 步骤 1：初始化为字符序列并添加词尾标记
    if not word:
        return []
    chars = list(word) + ['</w>']

    # 步骤 2：贪心合并，直到无法合并为止
    while True:
        pairs = [(chars[i], chars[i+1]) for i in range(len(chars)-1)]
        mergeable = [''.join(pair) for pair in pairs if ''.join(pair) in vocab]
        if not mergeable:
            break
        best_merge = mergeable[0]
        new_chars = []
        i = 0
        while i < len(chars):
            if i < len(chars)-1 and ''.join(chars[i:i+2]) == best_merge:
                new_chars.append(best_merge)
                i += 2
            else:
                new_chars.append(chars[i])
                i += 1
        chars = new_chars
    return chars

# 测试代码
def main():
    corpus = ["low","low","lower","lowest","new","newer"]
    print("原始语料库:", corpus)
    vocab_size = 10
    vocab = train_bpe(corpus, vocab_size)
    print("训练得到的词汇表:", sorted(vocab))
    test_words = ["low","lowest","newest"]
    for word in test_words:
        tokens = apply_bpe(word, vocab)
        print(f"单词 '{word}' 分词结果：{tokens}")

if __name__ == "__main__":
    main()

详细解释

1. 训练阶段 (train_bpe 函数)

输入：

• corpus：一个单词列表，表示训练语料库。
• vocab_size：目标词汇表大小，控制子词数量。

步骤：

1. 初始化：
   • 使用 Counter 统计每个单词的频率。
   • 将每个单词拆分为字符序列并添加词尾标记 </w>，存储在 word_splits 字典中。
   • 初始化词汇表 vocab，包含所有单个字符和词尾标记。
   • 示例："low" → ['l', 'o', 'w', '</w>']。
2. 统计字符对频率：
   • 遍历每个单词的当前分割状态，统计所有相邻字符对的频率。
   • 使用 defaultdict 累加频率，考虑单词本身的出现次数。
3. 合并频率最高的字符对：
   • 使用 max 找到频率最高的字符对，合并为新子词。
   • 更新所有单词的分割状态，将该字符对替换为新子词。
4. 迭代：
   • 重复统计和合并，直到词汇表达到 vocab_size 或无可合并的字符对。
   • 每次迭代将新子词加入 vocab。

输出：

• 一个包含字符和子词的词汇表。

复杂度：

• 时间复杂度约为 O(N·K)，其中 N 是语料库单词总数，K 是合并次数。

2. 应用阶段 (apply_bpe 函数)

输入：

• word：待分词的单词。
• vocab：训练好的词汇表。

步骤：

1. 初始化：
   • 将单词拆分为字符序列并添加词尾标记。
2. 贪心合并：
   • 遍历当前字符序列，找出所有相邻字符对。
   • 检查哪些字符对的合并结果存在于 vocab 中。
   • 选择第一个可合并的子词（贪心策略），进行合并。
   • 重复此过程，直到无法再合并。
3. 输出：
   • 返回最终的子词列表。

复杂度：

• 时间复杂度为 O(L²)，其中 L 是单词长度。

3. 测试代码 (main 函数)

• 语料库：一个简单的单词列表 ["low", "low", "lower", "lowest", "new", "newer"]。
• 训练：设置 vocab_size=10，生成词汇表。
• 应用：对测试单词 ["low", "lowest", "newest"] 进行分词。

输出示例：

原始语料库：['low', 'low', 'lower', 'lowest', 'new', 'newer']
训练得到的词汇表：['</w>', 'e', 'er', 'l', 'lo', 'low', 'n', 'o', 's', 'w']
单词 'low' 分词结果：['low']
单词 'lowest' 分词结果：['low', 'e', 's', 't']
单词 'newest' 分词结果：['n', 'e', 'w', 'e', 's', 't']

注意事项与优化建议

1. 效率优化：
   • 当前实现使用列表操作，实际中可以用字符串索引或 Trie 结构加速合并。
   • 对于大语料库，可以并行统计字符对频率。
2. 词汇表大小：
   • vocab_size 需要根据任务调整。过小会导致常见词被拆散，过大则失去子词优势。
3. 语言支持：
   • 当前代码假设输入是英文单词。对于中文等无空格语言，可以直接输入字符序列，或结合其他预分词方法。
4. 生产环境：
   • 在实际应用中（如 Transformer 模型），通常使用 SentencePiece 或 Hugging Face 的 tokenizers 库，它们是 BPE 的优化实现。

这个实现展示了 BPE 的核心逻辑，适合研究者理解其原理并进行实验。

defaultdict 函数解释

在代码实现中，使用了 defaultdict 来统计字符对频率。以下是对该函数的说明。

什么是 defaultdict？

defaultdict 是 Python 标准库 collections 模块中的一个类，它是普通字典（dict）的一个子类。它的特别之处在于：当你访问一个不存在的键时，defaultdict 会自动为这个键提供一个默认值，而不是抛出 KeyError 异常。这个默认值由你指定的工厂函数（factory function）决定。

在代码中，defaultdict(int) 表示创建一个 defaultdict，其默认值由 int() 提供。调用 int() 不带参数时返回 0，因此 defaultdict(int) 的默认值是 0。

在这段代码中的作用

在这段 BPE 训练代码中，pair_freq 是一个用于统计字符对频率的字典。它的键是字符对（例如 ('l', 'o')），值是该字符对在语料库中的出现频率。使用 defaultdict(int) 的好处在于：

1. 初始化简便：无需手动检查键是否存在。
2. 代码简洁：消除了显式的初始化步骤，使代码更简洁、可读性更高。

使用 defaultdict(int)，当访问一个不存在的键时，它会自动初始化为 0，因此可以直接写：

pair_freq[pair] += freq

如果 pair 是新键，pair_freq[pair] 默认返回 0，然后加上 freq。

如果使用普通字典 dict，当你第一次遇到一个新的字符对时，需要手动检查它是否存在并初始化为 0。

为什么不用普通字典？

如果用普通字典 dict，代码需要改成：

pair_freq = {}
for word, freq in word_freq.items():
    chars = word_splits[word]
    for i in range(len(chars)-1):
        pair = (chars[i], chars[i+1])
        if pair not in pair_freq:
            pair_freq[pair] = 0
        pair_freq[pair] += freq

多了一行 if pair not in pair_freq: 的检查。虽然功能相同，但代码更冗长。

总结

在这段代码中，defaultdict(int) 是一个高效、简洁的工具，用于统计字符对的频率。它通过自动为新键提供默认值 0，避免了手动初始化的麻烦，使代码更优雅。