7.2.2 Tokenization

Why tokenization?

In Text Preprocessing, we cleaned the SMS messages and cut them into words at the spaces. That cutting step has a name, tokenization, and it deserves a bit more care than split(). A token is the unit a model sees: usually a word, sometimes a single character, and in modern language models often a piece of a word. Tokenization decides what those units are, and then gives each one a number, its token id.

Why does this matter so much? Because token ids are how text gets into a neural network. A message becomes a list of integers, such as [47, 12, 803], and a table of such lists, all the same length, becomes a tensor, just like the image tensors from the computer vision modules. And every pretrained language model you might meet in an IOAI task comes with its own tokenizer; the model only understands the ids that its own tokenizer produces. So in this module we will build the whole route by hand on the SMS data, one small step at a time: tokens, a vocabulary, ids, unknown words, padding and masks. At the end, we will see how subword tokens are learned with byte-pair encoding, the method behind GPT's tokenizer.

What you need to know

Here is what I would like you to take away from this module. Some of these will be new, and that is fine; we will meet each one below.

Learn it properly

Read the course section below first; it works through byte-pair encoding by hand. Then come back, and we will do the same steps in Python on the SMS data.

Pick one main course

Our pick: Speech and Language Processing, section 2.4

Read section 2.4, Subword Tokenization: Byte-Pair Encoding, of Chapter 2, Words and Tokens in Jurafsky and Martin's free textbook Speech and Language Processing. It explains why words, morphemes and characters each make awkward tokens, and how subwords solve the problem of unknown words. Then it runs the BPE training algorithm by hand on a tiny corpus, merge by merge, and shows how the learned merges split new text. If you read section 2.1 for Text Modality Basics, this is a little further on in the same chapter.

If you prefer something else

• A short overview: the Tokenizers section of the Hugging Face LLM Course compares word-based, character-based and subword tokenization, then shows how a pretrained tokenizer encodes and decodes text.
• BPE in code: the same course's Byte-Pair Encoding tokenization section trains BPE on a five-word corpus and then implements it in Python.
• A long video: Andrej Karpathy's Let's build the GPT Tokenizer (over two hours) builds GPT's byte-level BPE tokenizer from scratch and shows how many odd behaviours of language models come from tokenization. It is a great watch once you have finished this page, but not a replacement for it.

A quick tour

The rest of this page turns text into tensors of token ids, one step at a time, and then learns subword tokens. Go through your chosen course first, then open a notebook and run each cell as you read.

Splitting text into tokens

The first question is simply where to cut. Let us take a made-up message and split it in three different ways:

import re

message = "I'll call you at 5pm, ok? Can't wait!!"
print(message.split())
print(re.findall(r"\w+", message.lower()))
print(re.findall(r"\w+|[^\w\s]", message.lower()))

["I'll", 'call', 'you', 'at', '5pm,', 'ok?', "Can't", 'wait!!']
['i', 'll', 'call', 'you', 'at', '5pm', 'ok', 'can', 't', 'wait']
['i', "'", 'll', 'call', 'you', 'at', '5pm', ',', 'ok', '?', 'can', "'", 't', 'wait', '!', '!']

• split() cuts only at whitespace, so punctuation stays glued to words: 5pm, and ok? would be vocabulary entries of their own.
• \w matches one "word character": a letter, a digit or an underscore. So re.findall(r"\w+", ...) returns every run of word characters and drops everything else. Apostrophes split can't into can and t, which is a common, harmless compromise.
• The third pattern adds [^\w\s], "one character that is neither a word character nor whitespace", so each punctuation mark becomes a token of its own. Use it when punctuation matters, for example to keep the ! marks that Text Preprocessing found in half of all spam.

For the rest of this page, we will use the second version, lowercased, as our tokenizer. Let us wrap it in a small function so we can reuse it:

def tokenize(text):
    return re.findall(r"\w+", text.lower())

tokenize("WINNER!! Claim your prize")

['winner', 'claim', 'your', 'prize']

Word, character and subword tokens

So far our tokens have been words, but words are not the only choice. How different would characters be? Let us count both on the whole SMS corpus:

import pandas as pd
from collections import Counter

sms = pd.read_csv("sms.csv")

word_counts = Counter()
char_counts = Counter()
for text in sms["text"]:
    word_counts.update(tokenize(text))
    char_counts.update(text.lower())

print("distinct words:", len(word_counts))
print("distinct characters:", len(char_counts))

distinct words: 8753
distinct characters: 88

A Counter is a dictionary that counts: update adds 1 for every item of the list it is given. Passing a string to update counts its characters, because a string is a sequence of characters.

So we have 8,753 different words, but only 88 different characters. The two choices pull in opposite directions:

(The averages come from tokenize and str.len on the SMS messages.) Word tokens carry meaning, but they make a large vocabulary in which most entries are rare. Character tokens make a tiny vocabulary, but long sequences in which a single token means very little. Subword tokens, such as win + ner, sit in between: they keep common words whole and split rare ones into pieces. We will learn some at the end of this page. For most of Part 7, though, we stick with words, which work well for classic models on short texts like ours.

Building a vocabulary

Next, every token needs a number. A vocabulary is simply a table that maps each token to an integer id. But should every word we have ever seen get one? Let us look at how often the words appear before deciding:

print(word_counts.most_common(8))
seen_once = [w for w, n in word_counts.items() if n == 1]
print(len(seen_once))

[('i', 2850), ('you', 2148), ('to', 2080), ('a', 1310), ('the', 1245), ('u', 1077), ('and', 930), ('in', 831)]
4801

The most common words are short ones like i, you and to, with SMS spelling (u for "you") already at number 6. At the other end, 4,801 of the 8,753 words, more than half, appear exactly once. Think about that from the model's point of view: it cannot learn anything reliable from a word it has seen only once. So a common rule is to keep only words that appear at least twice (or 5 times, for bigger corpora).

Before adding any words, we also reserve two special tokens at the start. You will see why we need both in a moment:

• <pad>, id 0, for padding (see Padding and truncation below);
• <unk>, id 1, the unknown token, for every word that is not in the vocabulary.

vocabulary = {"<pad>": 0, "<unk>": 1}
for word, count in word_counts.most_common():
    if count >= 2:
        vocabulary[word] = len(vocabulary)

print(len(vocabulary))
print(vocabulary["i"], vocabulary["you"], vocabulary["free"])

3954
2 3 56

Let us read that line by line. most_common() with no number lists every word from the most to the least frequent, so the most common words get the smallest ids. Each new word gets the next free id, which is len(vocabulary) at that moment. The result is 3,952 words plus our 2 special tokens.

One honest note: I built this vocabulary from all 5,171 messages, just to keep the example short. In a real model, you should build it from the training messages only, as Vector Embeddings of Simple Text Features does. Words that appear only in the test messages must be unknown to the model, exactly as new words will be once you submit.

Token ids, and the unknown token

Now we can turn text into ids. Encoding turns a text into a list of ids, and decoding turns ids back into tokens. The interesting case is a word that is not in our vocabulary. Python's dict.get(key, default) returns the default when the key is missing, which is exactly what the unknown token needs:

id_to_token = {i: token for token, i in vocabulary.items()}

def encode(text):
    unknown_id = vocabulary["<unk>"]
    return [vocabulary.get(token, unknown_id)
            for token in tokenize(text)]

def decode(ids):
    return [id_to_token[i] for i in ids]

ids = encode("Claim your FREE prize, Zorblax")
print(ids)
print(decode(ids))

[143, 15, 56, 161, 1]
['claim', 'your', 'free', 'prize', '<unk>']

The made-up name Zorblax is not in the vocabulary, so it becomes id 1, <unk>. Notice what that means: every unknown word looks exactly the same to the model, so whatever information it carried is lost. That is the main weakness of word tokens, and it is the reason subwords exist.

Padding and truncation

We have lists of ids now, but there is a catch. Messages have different numbers of tokens, while a tensor is a rectangle: every row must have the same length. The usual fix is simple. We pick a length, truncate (cut) longer sequences to it, and pad shorter ones by adding the <pad> id 0 at the end:

def pad_or_truncate(ids, max_length):
    ids = ids[:max_length]                  # truncate
    padding = [0] * (max_length - len(ids))
    return ids + padding                    # pad

examples = ["Call now", "Sorry, I'll call later",
            "URGENT! You have won a guaranteed cash prize"]
rows = [pad_or_truncate(encode(text), 6) for text in examples]
for row in rows:
    print(row)

[20, 26, 0, 0, 0, 0]
[108, 2, 58, 20, 137, 0]
[195, 3, 19, 166, 5, 288]

The first message gets four padding ids, and the third loses its last two tokens, cash prize. Now all the rows have the same length, so they can form a tensor. Comparing that tensor with 0 gives us the mask, which marks where the real tokens are:

import torch

batch = torch.tensor(rows)
mask = (batch != 0).long()
print(batch.shape)
print(mask)

torch.Size([3, 6])
tensor([[1, 1, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 0],
        [1, 1, 1, 1, 1, 1]])

You might wonder why the model needs a mask at all. The reason is that padding is not part of the message. If a model averaged the vectors of all six positions, the first message's average would be mostly padding. With the mask, it can average over the real tokens only, which is exactly what Vector Embeddings of Simple Text Features does. Pretrained models such as BERT take the same thing as an input, under the name attention_mask.

That leaves one decision: how long should the sequences be? Too short, and we cut off useful words; too long, and most of each tensor is padding, which wastes memory and time. Rather than guess, let us look at the real lengths:

token_lists = sms["text"].map(tokenize)
lengths = token_lists.map(len)       # tokens per message
print(lengths.quantile([0.5, 0.95, 0.99]).tolist())
print(round((lengths <= 40).mean(), 3))

[12.0, 33.0, 53.0]
0.98

Half of the messages have 12 tokens or fewer, and 98% have at most 40. So a maximum length of 40 keeps nearly every message whole while the tensor stays small. The longest message has 190 tokens and loses most of its text, but that is a fair price for one message in five thousand. One small surprise: two messages, :) and :-) :-), have no word characters at all, so they become 40 padding ids. A mask with no 1s in it can cause a division by zero later.

Subword tokens with byte-pair encoding

Remember Zorblax, the word that turned into <unk>? Subword tokens fix that, and byte-pair encoding (BPE) is the usual way to learn them. We start with single characters and repeat one step: merge the pair of neighbouring tokens that occurs most often into a new token. Frequent words end up as single tokens, and rare words split into pieces we know. The list of merges, in order, is the tokenizer.

Let us try it on five made-up words and their counts, with two small helpers: one counts neighbouring pairs, and one merges a pair wherever it occurs in a word:

corpus_counts = {"win": 5, "wins": 2, "winner": 3,
                 "dinner": 2, "new": 4}
splits = {word: list(word) for word in corpus_counts}

def count_pairs(splits, corpus_counts):
    pairs = Counter()
    for word, tokens in splits.items():
        for left, right in zip(tokens, tokens[1:]):
            pairs[(left, right)] += corpus_counts[word]
    return pairs

def merge_pair(tokens, pair):
    merged = []
    i = 0
    while i < len(tokens):
        is_pair = (i + 1 < len(tokens)
                   and (tokens[i], tokens[i + 1]) == pair)
        if is_pair:
            merged.append(tokens[i] + tokens[i + 1])
            i += 2              # skip both halves of the pair
        else:
            merged.append(tokens[i])
            i += 1
    return merged

splits starts each word as a list of characters. In count_pairs, zip(tokens, tokens[1:]) pairs each token with the next one, and a pair inside win counts 5 times because win appears 5 times. Training is then a loop: count, merge the most frequent pair, remember it, repeat. We do six merges:

merges = []
for step in range(1, 7):
    pairs = count_pairs(splits, corpus_counts)
    best = max(pairs, key=pairs.get)    # the most frequent pair
    merges.append(best)
    for word in splits:
        splits[word] = merge_pair(splits[word], best)
    print(step, best, pairs[best])

splits

1 ('i', 'n') 12
2 ('w', 'in') 10
3 ('n', 'e') 9
4 ('ne', 'r') 5
5 ('ne', 'w') 4
6 ('win', 'ner') 3
{'win': ['win'], 'wins': ['win', 's'], 'winner': ['winner'], 'dinner': ['d', 'in', 'ner'], 'new': ['new']}

The first merge is i + n, which appears 5 + 2 + 3 + 2 = 12 times across win, wins, winner and dinner. (max(pairs, key=pairs.get) returns the pair with the largest count.) Step through the merges to watch the words change:

Frequent words (win, winner, new) are now single tokens, and the rarer dinner is three pieces. Here is the part that makes it worthwhile: to encode a word we have never seen, we split it into characters and apply the merges in order:

def bpe_encode(word, merges):
    tokens = list(word)
    for pair in merges:
        tokens = merge_pair(tokens, pair)
    return tokens

for word in ["winners", "news", "dinners", "inner"]:
    print(word, bpe_encode(word, merges))

winners ['winner', 's']
news ['new', 's']
dinners ['d', 'in', 'ner', 's']
inner ['in', 'ner']

None of these words was in the training corpus, yet none needs <unk>: each is built from known pieces. A character the trainer never saw would still be stuck, which is why GPT-style tokenizers start from the 256 possible bytes of UTF-8 (see Text Modality Basics) instead of characters. Real tokenizers learn tens of thousands of merges from gigabytes of text, but the algorithm is the one you just ran.

from transformers import AutoTokenizer

gpt2_tokenizer = AutoTokenizer.from_pretrained("gpt2")
for text in ["winners", "spinner", "Call now", "£500"]:
    print(text, gpt2_tokenizer.tokenize(text))

winners ['win', 'ners']
spinner ['sp', 'inner']
Call now ['Call', 'Ġnow']
£500 ['£', '500']

Common mistakes

How to practise

The best practice is to play with the SMS data yourself. Open a notebook, run the code from this page, and try these:

• Tokenize the messages with the third pattern, which keeps punctuation as tokens. How many distinct tokens do you get now, and which punctuation marks are most common in spam?
• Rebuild the SMS vocabulary with a minimum count of 1, 2, 5 and 10. How many words does each keep, and what fraction of all the tokens in the corpus become <unk>?
• Run the BPE trainer for 20 merges on the tokens of 200 SMS messages. Which merges come first? Do they look like English word pieces?
• Add "</w>" as an extra last symbol of every word before training BPE, as the original BPE for translation did. Which merges change, and why does it help to know where a word ends?

Check yourself

What comes next

You can now take any message and turn it into a row of a tensor: tokens, ids, padding and a mask. You have also seen how subword tokenizers avoid <unk>. Next, we put these tokens to work:

• Bag of Words: count the tokens of each message to get a fixed-length vector, and train the first spam classifier.
• Vector Embeddings of Simple Text Features: feed the padded token ids and masks from this page to a small PyTorch model that learns a vector for every word.