Introduction

A tokenizer is a key tool in natural language processing. Its job is to split a text string into lexical units, or tokens. Tokenizers play a crucial role during text preprocessing, providing the foundation for downstream tasks such as text analysis, information retrieval, and machine translation.

Origins and Development

The history of tokenizers goes back to the early days of computational linguistics and information retrieval. As computer science matured, researchers realized that processing natural language text requires splitting a continuous sequence of characters into basic units that carry meaning (called morphemes in linguistics). Early tokenization methods were mainly rule- and dictionary-based, relying on predefined rules and word lists to identify word boundaries. With the rise of statistical NLP and machine learning, statistical models and data-driven approaches gradually replaced rule-based ones.

In recent years, advances in deep learning have pushed tokenization further. In particular, the introduction of pretrained language models such as BERT (Bidirectional Encoder Representations from Transformers) brought subword-level tokenization methods such as Byte Pair Encoding (BPE), WordPiece, and SentencePiece, which handle out-of-vocabulary words and linguistic diversity far better.

Motivation

To understand tokenizers, we first need to understand why we use them at all.

In NLP tasks, the data we work with is usually raw text.

Take the following sentence as an example:

Jim Henson was a puppeteer

Models, however, can only process numbers, so we need a way to turn raw text into numbers. That is exactly what a tokenizer does.

In short, the goal of a tokenizer is to convert text that humans understand into numbers that machines understand.

Next, we introduce the simplest and most intuitive tokenization method — the Word-based Tokenizer.

The Simplest and Most Intuitive Approach — Word-based Tokenizer

Part of this section draws on the Hugging Face NLP Course ¹

Picking up where we left off: how do we turn the text Jim Henson was a puppeteer into numbers?

One intuitive approach is to split the string on whitespace and assign each word a unique number as its index.

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

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

This way each word gets an ID, starting from 0 and running up to the size of the vocabulary. The model uses these IDs to identify each word.

If we wanted a word-based tokenizer to cover an entire language, we would have to assign a unique integer index to every word in that language, which produces an enormous number of indices. English, for example, has more than 500,000 words, so building a mapping from every word to an index would require a dictionary with 500,000 entries. And that is not the only drawback of word-based tokenization.

Furthermore, a word like “dog” is represented differently from a word like “dogs”, and the model has no way of knowing that “dog” and “dogs” are related: it treats them as two unrelated words. The same applies to other similar pairs, such as “run” and “running” — the model will not consider them similar.

We also need a special token to represent words that are not in our vocabulary. This is the “unknown” token, usually written as “[UNK]” or “<unk>”. If you see a tokenizer producing many of these tokens, it is generally a bad sign: it means the tokenizer could not retrieve an index for a word, so information is lost during tokenization — a fatal shortcoming.

To summarize, the word-based tokenizer has several major drawbacks:

1. Huge vocabulary: because the vocabulary of a language or application domain is very large, a word-based tokenizer needs a very large vocabulary. This not only increases storage and computation costs, but also degrades training and inference efficiency. In practice, many words are low-frequency, and including large numbers of rare words in the vocabulary leads to data sparsity problems.
2. Difficulty handling morphological variation: many languages have rich morphology (plurals and tenses in English, grammatical gender in French, and so on). A word-based tokenizer has to include every one of these surface forms, inflating the vocabulary even further. Worse, different forms of the same word are treated as distinct tokens, so the model cannot share semantic information across them.
3. Limited coverage, unable to handle out-of-vocabulary words: a word-based tokenizer requires a fixed vocabulary. New words or misspellings that are not in the vocabulary simply cannot be handled, which hurts generalization.

A Finer-grained Approach — Byte Pair Encoding (BPE)

As discussed above, word-based tokenizers suffer from large vocabularies, difficulty with morphological variation, and limited coverage. Is there a tokenization method that solves all three?

Notice that English words reuse a great many letter combinations. Take “happy”: many words are built on it as a root, such as “happily”, “happiness”, and “unhappy”. These derived words can be decomposed into reusable letter combinations — the sequence “happ”, for instance, appears in all three. Beyond that, combinations like “ily” and “un” occur frequently in other English words, and pairing them with other fragments can express new words.

Naturally, this suggests a question: could we design a tokenizer around the idea of finding frequently occurring letter combinations, covering every English word by reusing them?

If so, such a tokenizer would resolve all three drawbacks of the word-based tokenizer, because:

1. High reuse means a small vocabulary: since words are built from letter combinations that are heavily reused, only a small number of combinations are needed to cover most English words.
2. Easy handling of morphological variation: in the example above, our vocabulary contains tokens like “ily” and “un”, which also appear frequently in other inflected words, making the method well suited to morphological variation.
3. Broad word coverage: the method starts from individual letters and searches for letter combinations, so it can cover every English word.

This method is in fact Byte Pair Encoding (BPE).

Byte Pair Encoding (BPE) is a subword segmentation technique that originated in data compression and is now widely used in natural language processing. The core idea of BPE is to iteratively merge the most frequent byte pair, building up subword units step by step and thereby segmenting the text. The method was first proposed by Philip Gage in 1994² for file compression, and was later introduced into machine translation by Sennrich et al. in 2015³ to address oversized vocabularies and sparsity.

Many well-known LLMs use BPE for tokenization, including the GPT series, BERT, RoBERTa, and T5. It is fair to say that BPE is now one of the classic algorithms of natural language processing.

In the next section we will build a BPE tokenizer step by step, following Andrej Karpathy’s project minbpe.

It is worth mentioning that Karpathy has many well-known LLM projects, such as llm.c and llama2.c.

Code Practice: Implementing BPE from Scratch

In this section we build a BPE tokenizer step by step, following Andrej Karpathy’s project minbpe⁴.

The Base Class Tokenizer

We start with the base form of BPE, namely the definition of the Tokenizer class:

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

The Tokenizer class has four basic functions — init, train, encode, and decode — corresponding to initializing, training, encoding, and decoding. Among them, train, encode, and decode are virtual functions that will be overridden by the subclass.

The minbpe project also supports saving and loading tokenizer models. Since this is only loosely related to our topic, and for reasons of space, we will not go into it here; interested readers can consult the source⁵.

In the init function we define two variables, self.merges = {} and self.vocab. The former records, during tokenization, the mapping from the indices of two adjacent original tokens to the index of the new token they merge into, i.e. (int, int) -> int. The latter represents the vocabulary, recording the mapping from an index to a token, i.e. int -> bytes.

self.vocab is initialized inside init, where we map 256 integers used as indices (idx) to the 256 tokens in hexadecimal representation (bytes([idx])).

If we print vocab inside the _build_vocab function, we get:

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

BPE

Next, here is the definition of the BPE class:

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

The BPE class overrides train, encode, and decode, while init is inherited from the Tokenizer class.

Let us walk through the functions in the order train, encode, decode.

BPE.train

Inside train there are two helper functions, get_stats and merge.

def get_stats(ids): counts how often each pair of adjacent tokens occurs. For example, when ids = [1, 2, 3, 1, 2], the return value is {(1, 2): 2, (2, 3): 1, (3, 1): 1}⁶.

def merge(ids, pair, idx): merges every occurrence of pair in ids into idx and returns the new list of ids. For example, with ids=[1, 2, 3, 1, 2], pair=(1, 2), idx=4 -> [4, 3, 4], we replace the adjacent 1, 2 in ids with 4, yielding the new ids [4, 3, 4].

In train we first need to convert the characters of the string into indices, which we achieve with text_bytes = text.encode("utf-8") and ids = list(text_bytes) . For instance, when text = 'aaabbc', we get ids = [97, 97, 97, 98, 98, 99].

Next, inside the loop, get_stats first counts the frequency of each adjacent token pair in ids. The astute reader will already have guessed the purpose: it is to merge these high-frequency pairs into new tokens, and that is exactly what merge does. At this point the length of ids has been reduced. Finally, we record the mapping from token pair to index in merges and the mapping from index to new token in the vocabulary vocab.

This process repeats until the loop finishes.

So what is train actually doing?

In essence, train merges frequently co-occurring adjacent token pairs into a single new token. By adding only a small number of mappings to the vocabulary, we can substantially shorten the training text. Note that at the start the vocabulary contains only single letters. As training proceeds, frequent letter pairs are gradually added — first pairs of two letters, then longer letter sequences, and so on.

Taking the training text text = "happily happiness unhappy" as an example, the log produced by each of the three rounds is:

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

Notice that after three iterations, happ has appeared in the vocabulary. This means the frequent letter combination happ can now be used in subsequent decoding and encoding.

BPE.encode

In encode we again start by finding the frequently occurring token pairs in the text. We then look for the token pair with the smallest index in merges. The reason is that during training, a smaller index means a higher frequency in the training set, which is statistically sensible⁷. We then map that token pair to its new token according to the mapping in merges, producing a new token sequence. This process repeats until no token pair can be merged (reduced) any further.

BPE.decode

The decode function takes a list of integer indices ids, converts it into the corresponding byte sequence, and decodes that byte sequence into a UTF-8 string, returning the decoded version of the original text. This function is the inverse of encode.

Conclusion

To summarize, training a BPE amounts to finding the token combinations that occur frequently in the training set; encoding replaces mergeable tokens in the text with new tokens to produce a new token sequence; and decoding is the inverse of encoding.

We can now explain the three advantages of BPE mentioned earlier in this article.

1. High reuse means a small vocabulary: unlike a word-based tokenizer, BPE does not need a mapping for every single word — it only needs mappings for frequently occurring token sequences.
2. Easy handling of morphological variation: however a word varies, frequently occurring token sequences such as the past-tense ed or the adverbial ly are already in the vocabulary and can be used efficiently during encoding.
3. Broad word coverage: even if the current word contains a token sequence that is absent from the vocabulary, we can still represent it with the individual letters that are in the vocabulary. BPE can therefore cover every English word.