Frequent letter groups keep long pieces, while rare strings fall back to short pieces. That trade keeps common text compact without a huge table.
The table of pieces is fixed before use. The same text then splits the same way every time on that splitter.
Piece length | When it appears | Example shape |
|---|---|---|
Long piece | A frequent group in the training corpus |
|
Short piece | A rare group or a single character fallback |
|
Single character | Anything unseen: the guaranteed fallback | One character per piece |
Training starts from single characters and repeats one step: count adjacent pairs, join the most frequent pair into a new piece. Each round adds exactly one piece.
Ties need a stated rule, such as first in sorted order. Without one, two runs can learn different tables.
The calc block joins pairs on a tiny corpus by hand. It is separate from the program corpus below.
corpus: "ab" x 3, "ac" x 1
start pieces: [a, b] x 3 and [a, c] x 1
pair counts: (a,b) = 3, (a,c) = 1; total pairs = 4
merge 1: join (a,b) -> "ab" since 3 > 1
after merge 1: [ab] x 3 and [a, c] x 1
remaining pairs: (a,c) = 1
merge 2: join (a,c) -> "ac"
result: table gains "ab" then "ac"; "ab" splits as [ab], "ac" as [ac]The program below is a real deterministic trainer on a small corpus. It learns 5 merges, tokenizes seen and unseen words, and checks its own invariants.
Unseen words reuse the learned merges in order. Joining the pieces always rebuilds the input word.
import sys
CORPUS = {"low": 3, "lowest": 2, "newer": 2, "wider": 1}
ROUNDS = 5
splits = {}
for word in CORPUS:
splits[word] = list(word)
merges = []
for _ in range(ROUNDS):
counts = {}
for word, freq in CORPUS.items():
parts = splits[word]
for i in range(len(parts) - 1):
pair = (parts[i], parts[i + 1])
counts[pair] = counts.get(pair, 0) + freq
if not counts:
break
best = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))[0][0]
new_tok = best[0] + best[1]
for word in splits:
parts = splits[word]
out = []
i = 0
while i < len(parts):
if i + 1 < len(parts) and parts[i] == best[0] and parts[i + 1] == best[1]:
out.append(new_tok)
i += 2
else:
out.append(parts[i])
i += 1
splits[word] = out
merges.append((best[0], best[1], new_tok))
def tokenize(raw):
parts = list(raw)
for a, b, new_tok in merges:
out = []
i = 0
while i < len(parts):
if i + 1 < len(parts) and parts[i] == a and parts[i + 1] == b:
out.append(new_tok)
i += 2
else:
out.append(parts[i])
i += 1
parts = out
return parts
bad = 0
if len(merges) != ROUNDS:
bad += 1
for a, b, new_tok in merges:
if new_tok != a + b:
bad += 1
for w in ["low", "lowest", "newer", "wider", "lower", "newest"]:
tok = tokenize(w)
if "".join(tok) != w:
bad += 1
if len(tok) > len(w):
bad += 1
if any(t == "" for t in tok):
bad += 1
if bad != 0:
print("FAIL: " + str(bad) + " checks wrong")
sys.exit(1)
print("PASS: " + str(len(merges)) + " merges " + str(merges) + " newest " + str(tokenize("newest")))Pair counts 3 against 1 over 4 total pairs. The larger count joins first.
newest is not in the program corpus. How does the program still split it, and what stays true?It reuses the 5 learned merges in order on its characters. Joining the pieces still rebuilds newest, with no more pieces than characters.