Count the Pairs, Join the Winner, Repeat
Last timeWhy Not Just Words
The algorithm that builds a vocabulary is four lines long. Start from single bytes, count every adjacent pair, join the commonest into one new symbol, and do it again.
The corpus and the starting point
Take a corpus small enough to do by hand. Four distinct words, with how often
each occurs: low appears five times, lower twice, newest three times, widest
twice.
Begin by breaking every word into single characters. At this point the
vocabulary is just the characters that occur, and the corpus is a long sequence
of them. Nothing has been learned.
The algorithm now asks one question, over and over: which two adjacent symbols
occur together most often across the whole corpus? Note the phrase across the
whole corpus. A pair inside a word that appears five times counts five, not one.
This is the single detail that makes the method work, because it is what makes
common words assemble themselves before rare ones.
| o | w | e | s | t | r | |
|---|---|---|---|---|---|---|
| l | 7 | 0 | 0 | 0 | 0 | 0 |
| o | 0 | 7 | 0 | 0 | 0 | 0 |
| w | 0 | 0 | 5 | 0 | 0 | 0 |
| e | 0 | 3 | 0 | 5 | 0 | 2 |
| s | 0 | 0 | 0 | 0 | 5 | 0 |
The loop
Join the winning pair into one symbol, replace every occurrence of it in the
corpus, and count again. The counts are now different, because the merge
consumed the symbols that fed the old counts and created new neighbours that
were not adjacent before.
| step | round | winning pair | count | new symbol | how low now looks | what happened |
|---|---|---|---|---|---|---|
| 1 | 1 | l + o | 7 | lo | lo w | Seven because low occurs five times and lower twice, and both contain it. |
| 2 | 2 | lo + w | 7 | low | low | The symbol created in round one immediately becomes half of the round two winner. After two merges the commonest word in the corpus is a single symbol. |
| 3 | 3 | e + s | 5 | es | low | Three from newest and two from widest. Notice this fragment spans two words that share no prefix, which a word-based method would never have found. |
| 4 | 4 | es + t | 5 | est | low | The suffix assembles itself. Nobody told the algorithm that est is a morpheme; it is simply what keeps occurring together. |
| 5 | 5 | n + e | 3 | ne | low | The count is down to three, which is the general shape: the first merges pay enormously and later ones pay less and less. |
Two things in that table are worth pausing on. In round two the symbol made in
round one is immediately half of the next winner, which is how multi-character
symbols grow: each merge makes longer merges possible. And in round three the
winner spans two unrelated words, newest and widest, because the algorithm has
no idea what a word is. It sees adjacency and nothing else.
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