EUniversityLab· about 60 min· server sandbox

Lab: byte-pair encoding from scratch

Train a BPE tokenizer on a small corpus, tokenize new text with the learned merges and see the trade-off between vocabulary size and sequence length.

Teaches: Byte-pair encoding

Requires: TokenisationPython — lists, loops and dictionaries

Theory

Start with characters. Count all adjacent pairs, merge the most frequent into a new symbol, repeat N times. Tokenizing new text applies the merges in the same order.

Sub-tasks

pair statistics — pair_counts(words) where words is a dict {tuple-of-symbols: count} → dict {(a,b): count}.
merge — merge(words, pair) merges the pair in all words.
train and tokenize — train(text, n_merges) returns the list of merges; encode(text, merges) returns tokens.

Passes when: tokens_per_char <= 0.6

The starter code

runs in an isolated sandbox on the server

from collections import Counter


def words_from(text):
    """Ord → tuple av tecken med slutmarkör, med frekvens."""
    c = Counter(text.split())
    return {tuple(w) + ("</w>",): n for w, n in c.items()}


def pair_counts(words):
    # TODO: räkna intilliggande symbolpar viktade med ordets frekvens
    ...


def merge(words, pair):
    # TODO: ersätt varje förekomst av pair (a, b) med "ab" i alla ord
    ...


def train(text, n_merges=50):
    words = words_from(text)
    merges = []
    for _ in range(n_merges):
        # TODO: hitta vanligaste paret, slå ihop, spara
        ...
    return merges


def encode(text, merges):
    # TODO: för varje ord: börja med tecken + </w>, tillämpa merges i ordning
    ...

You write the code; tests you cannot see decide whether it holds up. Create a free account to run the lab.

Try the diagnostic Create a free account

Expected results

After 50 merges on the corpus: tokens per character ≤ 0.6 on new text, common words become one token.

Common mistakes

Merges more than one pair per iteration.
Applies merges in the wrong order when encoding.
End-of-word marker (</w>) missing → 'is' in 'this' and 'is' get mixed up.