This page is for students who want to implement tokenisers themselves. The visualiser shows what each method produces; here we cover how each one works — the pseudocode, and interactive demos.
Most tokenisers go through the same four stages:
# 1. NORMALISE raw text -> cleaned text # lowercase, strip accents, unicode, remove space # 2. PRE-TOKENISE cleaned -> chunks (usually "words" + whitespace) # split on spaces/punctuation # 3. MODEL chunks -> tokens (BPE / WordPiece / Unigram / ...) # the actual tokenisation algorithm # 4. POST-PROCESS tokens -> ids (look up each token in the vocab) # add special tokens like [CLS], [SEP], <s>, </s>
Note that pre-tokenisation matters: BPE and WordPiece first split a sentence into words so that a merge could not span a space, whereas SentencePiece intentionally skips this step and treats the space as just another character.
Word, character and sentence tokenisation need no training — they are rules.
Every character is a token. Tiny, fixed vocabulary; very long sequences.
function char_tokenise(text): return list(text) # split into characters
Split on whitespace and (usually) peel punctuation off as its own token.
function word_tokenise(text): # one or more letters/digits OR a single punctuation char return regex_findall(r"[A-Za-z0-9]+|[^\sA-Za-z0-9]", text)
Break on . ! ? — but not apply to abbreviations (Dr.,
e.g.) that contain a full stop without ending a sentence.
function sentence_tokenise(text): sentences = [] buffer = "" for word in split_keeping_spaces(text): buffer += word if ends_with(buffer, [".", "!", "?"]) and last_word(buffer) not in ABBREVIATIONS: sentences.append(trim(buffer)) buffer = "" if trim(buffer): sentences.append(trim(buffer)) return sentences
Represent each word as a sequence of characters plus an end-of-word marker (here </w>).
function bpe_train(corpus, num_merges): # word -> frequency, each word as a sequence of symbols vocab = count_words(corpus) # {("l","o","w","</w>"): 5, ...} merges = [] # a list of learned rules repeat num_merges times: pairs = count_adjacent_pairs(vocab) # {("e","s"): 9, ("s","t"): 7, ...} if pairs is empty: break best = argmax(pairs) # most frequent pair vocab = merge_pair(best, vocab) # replace every "e","s" with "es" merges.append(best) return merges function count_adjacent_pairs(vocab): counts = {} for word, freq in vocab: for (a, b) in consecutive_pairs(word): counts[(a, b)] += freq # sum up the frequencies of adjacent symbols if they appear in multiple words return counts
To tokenise new text, split each word into characters and apply the learned merges in the order they were learned — more frequent merges apply first.
function bpe_encode(word, merges): symbols = list(word) + ["</w>"] for (a, b) in merges: # learned order is essential symbols = merge_pair_in((a, b), symbols) return symbols
Learning to compress the word lowest, given these were the top pairs found in the corpus:
A rare word like "lowestest" would simply stop merging earlier and come out as
low + est + est — this is how BPE handles out-of-vocabulary words.
Edit the corpus, then press Step to apply one merge at a time. The middle panel shows the live adjacent-pair counts; watch the word table rebuild and the merge list grow.
O(merges × pairs)
For a candidate pair (a, b), BPE asks "how often does ab appear?". WordPiece instead
asks "how much does ab appear significantly?" using the score below. The score tells how far they co-occur more than by chance (see Pointwise Mutual Information).
# pick the pair maximising this likelihood score(a, b) = freq(a, b) / ( freq(a) × freq(b) ) function wordpiece_train(corpus, vocab_size): vocab = init_with_characters(corpus) # {"p", "l", "a", "y", "i", ...} while size(vocab) < vocab_size: pairs = count_adjacent_pairs(corpus, vocab) best = argmax(pairs, key = score) # likelihood, not frequency if best is none: break vocab.add(merge(best)) return vocab # a set of pieces
This is where WordPiece differs most from BPE. There is no merge list available; instead you scan each word
left-to-right and take the longest piece in the vocabulary that fits.
The ## prefix is added to any subword that doesn't start a word.
function wordpiece_encode(word, vocab): tokens = [] start = 0 while start < len(word): end = len(word) piece = none while start < end: # reduce the window size from the right sub = word[start:end] if start > 0: sub = "##" + sub # mark any subword that doesn't start a word if sub in vocab: piece = sub; break end -= 1 if piece is none: return ["[UNK]"] # whole word unmatchable tokens.append(piece) start = end return tokens
Encoding playing using a vocabulary containing play and ##ing:
Set a word and a vocabulary, then Step to reduce the window size one character at a time.
WordPiece takes the longest vocab piece that fits; ## marks a
word continuation.
Start from a BPE-based vocabulary, then segment a word with BPE, count how often each wordpiece appears, estimate its probability, and remove rare pieces.
function unigram_train(corpus, vocab_size): # Start with many candidate pieces: ["p", "l", "a", "y", "play", "ing", "ed", "er"] V = bpe_train(corpus, large_vocab_size) p = init_probs(V) while size(V) > vocab_size: piece_counts = {} # Segment each word using the current vocabulary for word in corpus: pieces = bpe_encode(word, merges) # Count how often each piece is used for piece in pieces: piece_counts[piece] += 1 # Update probabilities logp = normalise_to_log_probs(piece_counts) V = remove_low_prob_pieces(V, logp) return V, logp
The encoder considers many possible ways to split a word. It scores each possible split by summing the log probabilities of word pieces, and uses the Viterbi algorithm to efficiently find the highest-scoring segmentation.
function unigram_encode(word, logp): # word = "playing" # logp = {"play": -1.2, "ing": -0.8, "pla": -2.0, "y": -5.0} N = len(word) best = array(N + 1, fill = -infinity) # best[i] = best score for segmenting word[:i] into 1+ tokens # best[4] = best score for "play" back = array(N + 1, fill = -1) # back[i] = where the last token starts # back[7] = 4 means last token = word[4:7] = "ing" best[0] = 0 for i in 1 .. N: # compute best segmentation for word[:i] # i=7 → "playing" for j in 0 .. i-1: piece = word[j:i] # candidate token # i=7 → {"playing", "laying", "aying", "ying", "ing", "ng", "g"} if piece in logp: cand = best[j] + logp[piece] # score(full token sequence) = score(previous tokens) + score(current token) # cand = best[4] + logp["ing"] = -1.2 + (-0.8) = -2.0 if cand > best[i]: best[i] = cand # update best score: best[7] = -2.0 back[i] = j # remember where last token starts: back[7] = 4 return reconstruct(back, word) # reconstruct segmentation using back pointers # back[7] = 4, back[4] = 0 # | play | ing | # 0 4 7 # result = [play, ing]
Segmenting playing with the vocab {play:-1.2, ing:-0.8, pla:-2.0, y:-5.0}:
Step moves to next characters, one at a time. At each time, it remembers the best way to split the word up to that point. Finally, it reconstructs the best split by tracing those remembered positions.