Tokenizor简介一(BPE原理及python实现)

简介

随着大模型的崛起，分词(Tokenizor)技术正在向着更加通用、更加细粒度的方向发展，这里介绍一些主流的Tokenizor方法，着重于中文处理方向及目前大模型所涉及的分词器。本文从传统分词算法谈起，重点介绍subwords算法中的BPE算法，并使用python实现(这里没有对实现速度上进行优化)。

传统分词方法

在非深度学习时期，对文本的建模能力较弱，文本处理中需要将词作为最小单元。做NLP任务的第一步，往往是对文本进行分词。这个时期出现了很多的中文分词器，比较常用的有哈工大的LTP、开源的jieba分词等。
最容易想到的分词方法是查字典。这里的方法有前向最长匹配、后向最长匹配等。先构建一个字典(这个字典中包含尽可能多的词及词组，对于未出现在字典中的词我们一般称为未登录词)。
前向最长匹配算法是将句子从左到右在字典中进行最长匹配，遇到词表中没有的就分为独立的单字。如下面的示例:

原句: 我去北京大学学英语
分词: 我/去/北京大学/学/英语

但这种方法有较大的局限性, 在中文的复杂语义环境不能解决的情况有很多。
如: '欢迎新老师生前来就餐’如果使用前向最长匹配会出现如下分词结果

欢迎/新老师/生前/来/就餐

显然是一个错误的分词结果，有人将统计的知识用在了分词中，得到了跨越式的进步。
这些分词器大都是基于统计语言模型，具体的实现方式可以参考我的这篇文章:分词-Jieba分词DAG方法
分词作为一个在传统NLP中已经基本解决的问题，在大模型时代又有了新的挑战与发展:

由于大语言模型往往不是处理单语种的问题，如果构建一个全语系的字典，会带来非常大的内存消耗，如果选择词典过小又会带来大量的OOV问题。
词粒度太细又会导致单个token包含过多的语义信息，也会导致在解码时效率过低。如: 英文使用单字母粒度，中文使用单字粒度。
在英文语系中，有词根、前缀、后缀等形式，通过传统分词的方式无法学习到这些信息。例如: 无法通过old, older, oldest 之间的关系学到smart, smarter, smartest 之间的关系。

Subword分词方法

作为一种折中方案，Subword方法在大模型时代成为了主流的Tokenizor方法，下面介绍几种常见大模型的Subword算法。

BPE（Byte Pair Encoder）字节对编码

GPT, GPT-2, RoBERTa, BART, DeBERTa、Baichuan1等模型均采用BPE方法构建subword vector。这种方法的目的是通过一个有限的词表 来解决所有单词的分词问题，同时尽可能将结果中 token 的数目降到最低。
举例来说，[‘old’, ‘older’, ‘oldest’] 这三个单词。都是代表"老"的意思，但是如果我们以词为单位，会将每个词都加入词表中，导致分词粒度过大，尤其在英语中这种情况非常多(中文使用bpe分词时优势没有英文明显)。导致词表过大，训练的效果变差。
BPE算法通过训练，能够把上面的3个单词拆分成[“old”,“er”,“est”]三部分，可以把词的本身的意思和比较级分开，在不损失语义的基础上，有效减少词表数量。
先来看代码调用(google的SentencePiece库)，然后详细介绍其原理，并使用python简单实现。

直接调用SentencePiece库

这里直接调用Transformer包中的SentencePiece函数对自定义语料进行分词。我们这里使用《天龙八部》小说进行举例:

import sentencepiece as sp

sp.SentencePieceTrainer.train(input="tlbb.txt",  # 支持txt和tsv格式
                              model_prefix="tlbb", # 保存模型文件名的前缀
                              vocab_size=5000, 
                              model_type='bpe')

这样就可以直接调用bpe构建一个自定义语料的词表及分词模型了，可以简单看下最终的词表:

0
0
0
:“ -0
。” -1
段誉 -2
说道 -3
萧峰 -4
慕容 -5
虚竹 -6

可以看到段誉、萧峰、虚竹等都被分了出来。前几个是特殊字符的id，可以通过指定bos_id, eos_id等改变特殊字符的id。更详细的用法可以参考官方主页
从上述的调用可以看出，需要两个重要参数:

训练语料
指定词表的长度

BPE 首先将词分成单个字符，然后依次用另一个字符替换频率最高的一对字符 ，直到循环次数结束。
算法的整体步骤如下所示：

准备模型的训练语料
确定期望的词表大小
将训练语料按字构建初始的词表
统计训练语料中每一个连续字对出现的频率，选择出现频率最高的字对，合并成新的subword，并更新词表
重复第4步，直到词表大小达到我们设定的期望或下一个最高频的字对频率为1

这里使用一个中文分词的示例来对算法进行详细讲解:还是使用《天龙八部》作为训练语料。
迭代步骤如下:

首先查看语料库中每个词组的频率(为简单起见，把非中文符号及中文标点全部作为分隔符，类似英文单词之间的空格)，添加特殊符号, 表示该字为结尾字。

import re
from collections import Counter
def get_ori_vocab():
    """构建初始词表，把非中文符号及中文标点全部作为分隔符"""
    vocab_all = []
    with open(corpus_path) as fin:
        for line in fin:
            line = re.sub("^\u4e00-\u9fa5", " ", line)
            line = re.sub("[《》“”，。？！（）\-=+：]", " ", line)
            vocab_all.extend([" ".join(list(word)) + "</w>" for word in line.split()])
    word_freqs = Counter(vocab_all)
    splits = {word: [c for c in word.split()] for word in word_freqs.keys()}
    return word_freqs, splits

未分割前的词频top-20如下:
说 道</w> 1550
道</w> 664
段 誉 道</w> 427
是</w> 301
叫 道</w> 291
心 想</w> 269
虚 竹 道</w> 221
问 道</w> 217
阿 紫 道</w> 194
阿 朱 道</w> 168

构建初始词表(词表中包含每个字)

def get_vocab(word_freqs):
    """初始单个字的词表"""
    alphabet = []
    for word in word_freqs.keys():
        for letter in word.split():
            if letter not in alphabet:
                alphabet.append(letter)
    return alphabet
alphabet = get_vocab(word_freqs)
alphabet.sort()
vocab = ["</w>"] + alphabet.copy()
# print(f"单字粒度 {alphabet[:10]}")
# 单字粒度 ['天', '龙', '八', '部</w>', '释', '名</w>', '这', '名', '词', '出']

统计训练语料中每一个连续字对出现的频率，找到出现频率最高的字对

def compute_pair_freqs():
    """计算单个字的频率"""
    pair_freqs = defaultdict(int)
    for word, freq in word_freqs.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
    
    for i, key in enumerate(pair_freqs.keys()):
        print(f"{key}: {pair_freqs[key]}")
        if i >= 5:
            break
    return pair_freqs

def find_max(pair_freqs):
    """查找频率最大的组合"""
    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(f"best pair is {best_pair} and max_freq is {max_freq}")
    return best_pair
pair_freqs = compute_pair_freqs()
best_pair = find_max(pair_freqs)

将频率最高的字对合并成新的subword，并更新词表

def merge_pair(best_pair, word_freqs, splits):
    """合并"""
    a, b = best_pair[0], best_pair[1]
    for word in word_freqs:
        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
splits = merge_pair(best_pair, word_freqs, splits)

循环得到最终词表

merges = {}
vocab_count = {}
def get_final():
    """get_final"""
    while len(vocab) < 15:
        best_pair = find_max(compute_pair_freqs())
        merge_pair(best_pair)
        print("splits", splits)
        print("frequence", get_tokens())
        merges[best_pair] = best_pair[0] + best_pair[1]
        vocab.append(best_pair[0] + best_pair[1])
    return vocab

解码

使用前向最长匹配方式进行解码。

def tokenize(text):
    """解码"""
    pre_tokenized_text = text.split()
    splits = [[l for l in word] for word in pre_tokenized_text]
    for pair, merge in merges.items():
        for idx, split in enumerate(splits):
            i = 0
            while i < len(split) - 1:
                if split[i] == pair[0] and split[i + 1] == pair[1]:
                    split = split[:i] + [merge] + split[i + 2 :]
                else:
                    i += 1
            splits[idx] = split

    return sum(splits, [])