介绍

分词器 (Tokenizer) 是自然语言处理领域中一种关键的工具，其作用在于将文本字符串划分为词元也就是token。分词器在文本预处理阶段起着至关重要的作用，为后续的文本分析、信息检索、机器翻译等任务提供基础。

渊源与发展

分词器的历史可以追溯到计算语言学和信息检索的发展早期。随着计算机科学的发展，研究人员认识到在处理自然语言文本时，需要将连续的文本序列划分为具有语义意义的基本单位 (在语言学中称语素)。早期的分词方法主要基于规则和词典，依靠预定义的规则和词库来识别词语边界。随着统计自然语言处理和机器学习的兴起，统计模型和数据驱动的方法逐渐取代了基于规则的方法。

近年来，深度学习技术的发展进一步推动了分词技术的进步。特别是BERT (Bidirectional Encoder Representations from Transformers) 等预训练语言模型的引入，采用了子词级别的分词方法，如Byte Pair Encoding (BPE) 、WordPiece和SentencePiece等，这些方法能够更好地处理未登录词和语言多样性的问题。

Motivation

要理解Tokenizer，我们首先要理解使用Tokenizer的动机是什么。

在 NLP 任务中，通常处理的数据是原始文本。

以下文为例：

Jim Henson was a puppeteer

但是，模型只能处理数字，因此我们需要找到一种将原始文本转换为数字的方法。这正是Tokenizer所做的事。

概括来讲，Tokenizer的目标就是将人类能理解的文本转为机器所能理解的数字。

接下来，我们将介绍一种最简单和直观的分词方法——基于单词的分词器 (Word-based Tokenizer)

最简单和直观的分词方法——Word-based Tokenizer

本章部分内容参考自 huggingface NLP Course ¹

书接上文，那如何把文本Jim Henson was a puppeteer转为数字呢？

一个直观的方法就是以空格分割这段字符串，为每一个单词赋予一个唯一的数字作为索引。

tokenized_text = "Jim Henson was a puppeteer".split()
print(tokenized_text)

['Jim', 'Henson', 'was', 'a', 'puppeteer']

这样，每个单词都分配了一个 ID，从 0 开始一直到词汇表的大小。该模型使用这些 ID 来识别每个单词。

如果我们想用 Word-based Tokenizer 完全覆盖一种语言，就需要为语言中的每个单词都赋予一个唯一整数索引，这将生成大量的索引。例如，英语中有超过 500,000 个单词，因此要构建从每个单词到索引的映射，我们需要创建包含500,000个元素的字典。但这还不只是 Word-based Tokenizer 唯一的缺点。

此外，像 “dog” 这样的词与 “dogs” 这样的词的表示方式不同，模型无法知道"dog"和"dogs"是相似的：它会将这两个词识别为不相关。这同样适用于其他相似的词，例如"run"和"running"，模型不会认为它们是相似的。

此外，我们需要一个自定义token来表示不在我们词汇表中的单词，这被称为"未知"标记(token)，通常表示为"[UNK]“或”<unk>"。如果你看到Tokenizer产生了很多这样的Token，这通常是一个不好的迹象，因为它无法检索到一个词的索引，这就意味着在分词的过程中会产生信息缺失，这一缺点是极其致命的。

综上，我们总结了Word-based Tokenizer的几大缺点：

1. 词汇表规模大: 由于不同语言和应用场景中的词汇量非常庞大，Word-based Tokenizer需要一个非常大的词汇表。这不仅增加了存储和计算的开销，还会导致训练和推理效率下降。此外，在实际应用中，许多单词是低频词。如果词汇表中包含大量低频词，会导致稀疏数据问题。
2. 难以处理形态变化灵活的单词: 许多语言具有丰富的形态变化 (如英语的复数形式、时态变化，法语的性别变化等) 。Word-based Tokenizer需要包含所有这些形态变化形式，导致词汇表进一步膨胀。此外，不同形式的同一词语被视为不同的词元，导致模型无法有效共享这些词语的语义信息。
3. 词汇表覆盖范围有限，无法处理未登录词 (Out-of-Vocabulary Words): Word-based Tokenizer需要一个固定的词汇表。如果遇到词汇表中没有的新词或拼写错误的词，它们将无法处理。这导致Tokenizer无法处理这些未登录词，影响其泛化能力。

更精细的分词方法——Byte Pair Encoding (BPE)

在上文提到，Word-based Tokenizer存在词表大、难以处理灵活的单词形态、词表覆盖范围有限的问题。那么，是否有一种分词方法可以解决上述问题呢？

我们注意到，在英文单词中，存在大量复用的字母组合。以 “happy” 为例，以 “happy” 为词根的单词有很多，如 “happily”、“happiness”、“unhappy"等。我们注意到，这些衍生词可以拆分成字母组合并复用，如"happ"这一字母组合在三个单词中都有出现。此外， “ily”、“un” 字母组合在其他英语单词中高频出现，它们和其他单词的组合也可以用于表示新的单词。

自然而然的，我们想到，是否可以基于这种 “找高频出现的字母组合” 的方法设计出一种分词器，从而通过复用各种字母组合来覆盖所有英文单词呢？

如果可以，这种分词器会解决Word-based Tokenizer存在的三种缺点，这是因为：

1. 复用性高导致词表规模小：由于各种单词是由各种字母组合构成的，复用性高，因此只需要少量的字母组合就可以覆盖大多数的英语单词。
2. 易于处理灵活多变的单词形态：在本节的样例中，我们的词表中存在 “ily”、“un” 等token，这些token在其他经过形态变化的单词中也高频出现，因此适用于处理灵活多变的单词形态。
3. 单词覆盖范围广：该方法从单个字母开始，寻找各种字母组合，可以覆盖所有的英文单词。

事实上，这种方法就是字节对编码(Byte Pair Encoding, BPE)。

Byte Pair Encoding (BPE) 是一种源于数据压缩领域的子词分割技术，现已广泛应用于自然语言处理任务。BPE的核心思想是通过迭代地合并出现频率最高的字节对，逐步构建子词单元，从而实现文本的分段。该方法最早由Philip Gage在1994年提出²，用于文件压缩，随后被Sennrich等人在2015年引入到机器翻译中³，以应对词汇表过大和稀疏性问题。

在大模型时代，许多著名的大模型的分词器使用的正是BPE，如GPT系列、BERT、RoEBRTa、T5等。可以说，BPE已经是自然语言处理领域最经典的算法之一。

在下一章节，我们将根据Andrej的项目minbpe逐步构建一个BPE。

值得一提的是，Andrej有许多知名的大模型项目，如 llm.c 和 llama2.c等。

代码实践：手撕BPE

在本章节，我们将根据Andrej的项目minbpe逐步构建一个BPE⁴。

基类Tokenizer

首先，我们给出BPE的基类形态，即Tokenizer 类的定义：

class Tokenizer:
    """Base class for Tokenizers"""

    def __init__(self):
        # default: vocab size of 256 (all bytes), no merges, no patterns
        self.merges = {} # (int, int) -> int
        self.vocab = self._build_vocab() # int -> bytes

    def train(self, text, vocab_size, verbose=False):
        # Tokenizer can train a vocabulary of size vocab_size from text
        raise NotImplementedError

    def encode(self, text):
        # Tokenizer can encode a string into a list of integers
        raise NotImplementedError

    def decode(self, ids):
        # Tokenizer can decode a list of integers into a string
        raise NotImplementedError
    def _build_vocab(self):
        # vocab is simply and deterministically derived from merges
        vocab = {idx: bytes([idx]) for idx in range(256)}
        return vocab

在类Tokenizer中，存在四个基本函数分别是init、train、encode、decode 分别对应了分词器的初始化、训练、编码、解码过程，其中train、encode、decode 作为虚函数将被子类的同名函数覆盖。

此外，在项目minbpe中还有保存、加载分词器模型的功能，因与主题关系有限和篇幅限制在此不做赘述，有兴趣的读者可自行查阅⁵。

在init函数中，我们定义两个变量，分别是self.merges = {}和self.vocab。前者用于记录在分词器过程中，两个相邻原始token的索引可被合并为的新的token的索引的映射关系，即(int, int) -> int；后者用于表示词表，词表记录了索引到token的映射关系，即int -> bytes。

其中， self.vocab 在init函数中被初始化，在这里，我们使用256个整数作为索引 (idx) 映射到十六进制表示的256个token (bytes([idx]))。

如果我们在_build_vocab函数中打印 vocab 会得到：

{0: b'\x00', 1: b'\x01', 2: b'\x02', 3: b'\x03', ..., 254: b'\xfe', 255: b'\xff'}

BPE

接下来，我们给出BPE类的定义：

class BPE(Tokenizer):

    def __init__(self):
        super().__init__()

    def train(self, text, vocab_size, verbose=False):
        def get_stats(ids, counts=None):
            """
            Given a list of integers, return a dictionary of counts of consecutive pairs
            Example: [1, 2, 3, 1, 2] -> {(1, 2): 2, (2, 3): 1, (3, 1): 1}
            Optionally allows to update an existing dictionary of counts
            """
            counts = {} if counts is None else counts
            for pair in zip(ids, ids[1:]): # iterate consecutive elements
                counts[pair] = counts.get(pair, 0) + 1
            return counts
        
        def merge(ids, pair, idx):
            """
            In the list of integers (ids), replace all consecutive occurrences
            of pair with the new integer token idx
            Example: ids=[1, 2, 3, 1, 2], pair=(1, 2), idx=4 -> [4, 3, 4]
            """
            newids = []
            i = 0
            while i < len(ids):
                # if not at the very last position AND the pair matches, replace it
                if ids[i] == pair[0] and i < len(ids) - 1 and ids[i+1] == pair[1]:
                    newids.append(idx)
                    i += 2
                else:
                    newids.append(ids[i])
                    i += 1
            return newids
        
        assert vocab_size >= 256
        num_merges = vocab_size - 256
        # input text preprocessing
        text_bytes = text.encode("utf-8") # raw bytes
        ids = list(text_bytes) # list of integers in range 0..255
        # iteratively merge the most common pairs to create new tokens
        merges = {} # (int, int) -> int
        vocab = {idx: bytes([idx]) for idx in range(256)} # int -> bytes
        for i in range(num_merges):
            # count up the number of times every consecutive pair appears
            stats = get_stats(ids)
            # find the pair with the highest count
            pair = max(stats, key=stats.get)
            print(pair)
            # mint a new token: assign it the next available id
            idx = 256 + i
            # replace all occurrences of pair in ids with idx
            ids = merge(ids, pair, idx)
            # save the merge
            merges[pair] = idx
            vocab[idx] = vocab[pair[0]] + vocab[pair[1]]
            if verbose:
                print(f"merge {i+1}/{num_merges}: {pair} -> {idx} ({vocab[idx]}) had {stats[pair]} occurrences")
        # save class variables
        self.merges = merges # used in encode()
        self.vocab = vocab   # used in decode()

    def decode(self, ids):
        # given ids (list of integers), return Python string
        text_bytes = b"".join(self.vocab[idx] for idx in ids)
        text = text_bytes.decode("utf-8", errors="replace")
        return text

    def encode(self, text):
        # given a string text, return the token ids
        text_bytes = text.encode("utf-8") # raw bytes
        ids = list(text_bytes) # list of integers in range 0..255
        while len(ids) >= 2:
            # find the pair with the lowest merge index
            stats = get_stats(ids)
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))
            # subtle: if there are no more merges available, the key will
            # result in an inf for every single pair, and the min will be
            # just the first pair in the list, arbitrarily
            # we can detect this terminating case by a membership check
            if pair not in self.merges:
                break # nothing else can be merged anymore
            # otherwise let's merge the best pair (lowest merge index)
            idx = self.merges[pair]
            ids = merge(ids, pair, idx)
        return ids

在BPE类中，对 train、encode、decode 函数进行了复写，而 init 函数继承自Tokenizer类。

我们按照 train、encode、decode 的顺序对函数逐个介绍：

BPE.train

在train函数中，存在两个函数，分别是 get_stats 和 merge 。

def get_stats(ids) : 该函数用于统计每两个相邻token出现的频率。举例来讲，当 ids = [1, 2, 3, 1, 2] 那么其返回值为 {(1, 2): 2, (2, 3): 1, (3, 1): 1} ⁶。

def merge(ids, pair, idx) : 该函数用于将ids中存在的pair合并为idx，返回新的ids列表。举例来讲，当 ids=[1, 2, 3, 1, 2], pair=(1, 2), idx=4 -> [4, 3, 4] ，我们会将ids中相邻的1, 2用 4替换，获得新的ids [4, 3, 4]。

在 train 函数中，我们首先需要将字符串中的字符转为索引，通过 text_bytes = text.encode("utf-8") 和 ids = list(text_bytes) 我们可以达到这个目的。例如，当 text = 'aaabbc' 时，ids = [97, 97, 97, 98, 98, 99]。

接下来，在循环中，首先在 get_stats 中统计 ids 中各个相邻token的出现频率。聪明的读者读到这里已经猜到这样做的目的是什么了，这样做的目的正是为了将这些出现频率高的token合并为新的token，而这个过程正是 merge。此时，ids的长度已经缩短了。最后，在merge和词表vocab中分别记录token对与索引的映射关系和索引和新token的映射关系。

重复上述过程，直至循环结束。

那么，我们来思考一下，train 的过程是在做一件什么事呢？

事实上，train 的过程就是将高频出现的两个相邻token对合并为一个新的token。这样，只需要在词表中增加少量的映射关系，就可以大幅减少训练文本的长度。需要注意的是，一开始，词表中只有单个字母。随着训练的进行，词表中会逐渐增加高频出现的字母对，从两个字母构成的字母对到多个字母构成的字母序列，以此类推。

以训练文本text = "happily happiness unhappy"为例，三轮循环中，每轮输出的日志如下：

merge 1/3: (104, 97) -> 256 (b'ha') had 3 occurrences
merge 2/3: (256, 112) -> 257 (b'hap') had 3 occurrences
merge 3/3: (257, 112) -> 258 (b'happ') had 3 occurrences

我们注意到，在三次循环结束后，happ 出现在了词表中。这就表示 happ 这一高频出现的字母组合可被应用于后续的解码和编码过程中。

BPE.encode

在 encode 函数中，我们还是先检索文本中高频出现的token对。接着，我们查找在merge函数中索引数最小的token对。这是因为，在训练过程中，索引数越小，在训练集中出现的频率越高，从统计学的角度来讲是合理的⁷。接着，将token对按照 merge 中的映射关系，映射为新的token，从而获得新的token序列。重复此过程，直至没有token对可被合并 (化简) 。

BPE.decode

decode 函数接受一个整数的索引列表 ids，将其转换为对应的字节序列，并将该字节序列解码为 UTF-8 编码的字符串。最终返回原始字符串的解码版本。该函数是 encoder 的逆过程。

总结

总结来讲，BPE的训练是在寻找训练集中高频出现的token组合；解码过程是将文本中出现的可合并的token用新的token替换从而生成新的token序列；解码过程则是解码的逆过程。

此时，我们给出我们在文章中提到的BPE的三个优点的原因。

1. 复用性高导致词表规模小：相比于Word-based Tokenizer，BPE无需为每一个单词都建立一个映射关系，而只需要对高频出现的token序列建立映射关系即可。
2. 易于处理灵活多变的单词形态：无论单词如何变化，那些高频出现的token序列如过去式ed、副词 ly已被包含在词表中，在编码过程中可被高效利用。
3. 单词覆盖范围广：即使当前单词中存在词表中不存在的token序列，我们也可以可以用词表中存在的单个字母来表示。因此，BPE可以覆盖所有的英文单词。