Nobody Wrote This List
Last timeWhere to Cut a Word
The list of pieces is built by a loop that repeatedly glues together the commonest adjacent pair, so what counts as one piece is decided entirely by a corpus.
The previous lesson needed a list of pieces where common words are whole and rare
words decompose into common fragments. Nobody writes such a list. It is built by
a loop short enough to state in three sentences, and the loop was borrowed from a
data compression method from the nineteen nineties.
Start by treating every character as its own piece, so the initial list is the
alphabet of the corpus, a few hundred entries. Every possible string is
representable at this point, which is a property worth noting because the
procedure never destroys it.
Then repeat one step. Count every adjacent pair of pieces across the whole
corpus. Find the most frequent pair. Add the two glued together as a new piece,
and rewrite the corpus so that pair is now a single piece everywhere it appears.
Stop when the list reaches the size you decided on in advance.
Watching it run
The first merges are always the most common letter pairs in the language. After a
few hundred rounds, common short words have been assembled whole. After a few
thousand, most ordinary words are single pieces, and after that the loop spends
its budget on longer multi-word sequences and on rarer vocabulary.
| step | round | what gets merged | why it was the most frequent pair |
|---|---|---|---|
| 1 | early | two very common letters | letter pairs dominate before anything lo |
| 2 | a few dozen in | common endings and short function words | these sequences repeat in nearly every s |
| 3 | a few hundred in | ordinary short words, complete | their letters have already been merged i |
| 4 | a few thousand in | most common words, each one piece | each appears often enough to beat any re |
| 5 | ten thousand and beyond | rarer words, inflected forms, and some m | all the frequent material has been used |
pieces = list(characters_in(corpus))
while len(pieces) < target_size:
pair = most_frequent_adjacent_pair(corpus)
merges.append(pair)
pieces.append(join(pair))
corpus = rewrite_with(corpus, pair)One more property is worth drawing out before moving on. The merges are ordered,
and that order is part of the finished artefact. Encoding a new string does not
search for the best possible cutting; it starts from characters and replays the
saved merges one by one, applying each wherever it fits. The result is whatever
that replay produces. This is cheap, it is deterministic, and it means two
tokenisers holding exactly the same set of pieces in a different order will cut
the same string into different pieces. The list of pieces is not the scheme. The
list of merges, in order, is the scheme.
The lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents