Tries and hash maps to BPE tokenization

The tokenizer is not a mysterious first layer of the model - it is three data structures you already know, chained back to back to turn a string into the integers an LLM actually runs on.

A transformer never sees your text. Between the letters you type and the vectors attention mixes together sits a small, unglamorous pipeline, and every piece of it is a data structure from the DSA path. A trie walks your characters and finds the longest token it recognises. A hash map turns that token string into an integer id in one hop. And that id is nothing but an array index into the embedding table, fetching a row in constant time. Same three structures, wired into the front door of every large language model.

Walk the trie, keep the longest word

The one algorithmic idea that ties BPE tokenization to a plain trie is greedy longest-match. Standing at some position in the string, you walk down the trie following one character per edge. Every time you pass through a node that is marked end-of-token, you remember it. You keep walking until the trie has no edge for the next character - then you emit the deepest end-of-token you saw, jump your cursor past it, and start again from there.

This is why a good tokenizer prefers low over lo over l: all three may be real tokens sharing one corridor, but the walk keeps the longest one that still ends on a valid token. Because every character in the vocabulary is itself a fallback token, the walk can never get stuck - worst case it emits a single character, so nothing is ever unrepresentable (the no-OOV guarantee from BPE). The merge rules BPE learned are exactly what decides which multi-character tokens exist in the trie in the first place.

See the pipeline fire

Type a word (or pick one) and press Run pipeline. Watch the trie light up character by character to find the longest token, watch that token get hashed to its integer id, and watch the id index straight into a row of the embedding matrix. Text becomes vectors, in front of you, one token at a time.

The pipeline, in a dozen lines

Written out, the greedy encoder is just the trie walk feeding a dict lookup feeding an array index - the three structures in three lines of the loop:

def encode(text, trie, vocab, E):        # trie: prefix tree · vocab: {token: id} · E: V×d array
    ids, i = [], 0
    while i < len(text):
        tok = longest_match(trie, text, i)  # walk edges, keep deepest end-node   → O(L)
        i  += len(tok)                       # jump the cursor past the matched token
        ids.append(vocab[tok])              # hash map: string → integer id       → O(1)
    return ids

vectors = [E[t] for t in ids]              # array index: id → embedding row     → O(1)
# text  --trie-->  tokens  --hash-->  ids  --E[id]-->  vectors, then on to attention

Check yourself