The columns the candidates share

The bound the search finds for itself took a nearest-word search from 156,714 cells a query down to 26,203, by bounding each candidate’s table with the best distance found so far and meeting the candidates most likely to improve that bound first. It ended one factor of 1.7 above a search that was handed the true answer before it started, and called that factor the price of not knowing.

It also left a fact alone. Each of the 2,424 candidates got a table of its own, and the tables are not independent. Structure, structures and structured share nine letters. If the table is laid out with the query down the rows and the candidate across the columns, the first nine columns of those three tables are identical — computed once, then computed again, then computed again.

That is not a small share of the vocabulary. Every word of it is an English word from running prose, so its words pile up on a few thousand stems, and the arithmetic of how much piles up is the first thing to measure.

A column belongs to a prefix, not to a word #

The recurrence is what makes the sharing exact rather than approximate. Cell $(i, j)$ of the table depends on $(i-1, j)$, $(i, j-1)$ and $(i-1, j-1)$ — three cells all at column $j$ or $j-1$. So column $j$ depends on column $j-1$ and on the $j$-th character of the candidate, and on nothing else about the candidate. Two candidates sharing their first $j$ characters have the same first $j$ columns, whatever they do afterwards.

A structure that makes that sharing available is the trie: one node per distinct prefix of the vocabulary, a node’s children being the letters that extend it. Walking the trie depth-first and carrying the current column down the walk computes each distinct prefix’s column exactly once.

The plate is the whole mechanism in one picture. The column headed with the first s is shared by every word in the vocabulary; the run structure is shared by three of them; the s and d immediately after it are the endings that distinguish structures from structured, and each costs one column rather than a table of ten. Reading along the foot gives the distance from the query to each word, in a single sweep, from a table that is a fraction of the nine it replaces.

The trie is the clearest way to say it and it is not the only way to have it. Sort the vocabulary, walk it in order, and keep a stack of columns: consecutive words in alphabetical order share a prefix, so on moving from one word to the next a search pops the columns that the new word does not share and computes only the ones it adds. That is the same walk with the structure left implicit, it needs no nodes and no pointers, and it costs a sort. Which of the two is right is a question about how often the vocabulary changes — and about what else the structure is asked for, since a band as wide as the answer is the other way of cutting the same table down and composes with either — rather than about the search — and the columns computed are identical either way, which is why everything below is a statement about the sharing rather than about the trie.

On the real vocabulary the arithmetic is the same and the numbers are larger. The 2,424 words hold 17,239 letters and have 7,709 distinct non-empty prefixes, so a shared walk computes 7,710 columns where a list computes 19,663 — one for every letter of every word, plus one initial column each.

What sharing is worth with no bound at all #

That ratio is 2.5, and it is worth isolating before any bound is applied, because it is the one saving on this page that owes nothing to knowing anything about the answer.

Sharing with no bound is worth 2.55 times, and the bound on the list is worth 3.89 times. So the two are the same order of saving, and they arrive by completely different routes: one throws away work that would have been repeated, the other throws away work that would have been wasted. Neither has any claim on the other’s factor, and the interesting question is whether they compose.

They very nearly do. The two together read 16,958 cells against the full search’s 156,714, a factor of 9.2, where multiplying the separate factors would predict 9.9. The small shortfall is real and is the sign of what the last section of this page is about: some of what the bound would have removed had already been removed by the sharing.

The shortfall is worth locating, because it is the first sign of the interaction the rest of the page is about. The cells a bound removes from a list search are the cells of hopeless candidates — long words, words with no letters in common with the query, words the search abandons after two rows. Those are exactly the candidates that a shared walk was never going to spend much on either, because they hang off a node near the root that a handful of columns disposes of. The two methods overlap on the cheapest part of the work and diverge on the rest, so the product overstates the pair by about seven per cent.

The shapes of the four lines say something the factors do not. The full search’s cells rise 13.4 times as the vocabulary rises 9.7 times — slightly faster than the vocabulary, because the words that enter a corpus late are the long ones. The list search with a bound rises 9.3 times, which is the same slope with a smaller constant: a bound applied per candidate cannot change the fact that there is one candidate per word. The shared walk with the same bound rises 5.9 times. That is not a constant factor at all.

A bound applied where it costs the most #

The reason is that the bound stops being a statement about a word and becomes a statement about a prefix.

The row-minimum argument of the previous page said: no cell of a row is smaller than the smallest cell of the row above it, so once every cell of a row exceeds the bound the candidate is finished. Turned on its side, the same fact says that the smallest value in a prefix’s column is a lower bound on the distance from the query to every word that begins with that prefix. A column whose minimum passes the bound takes its whole subtree with it — every word underneath, however many, at the cost of the one column that proved it.

That is the asymmetry between the two structures. A list search’s bound saves the tail of each candidate’s table and always pays for the head: even a word that is obviously hopeless costs the cells it takes to prove it, once per word. A shared search’s bound saves whole regions of the vocabulary, and the deeper in the trie a bound fails to bite, the fewer words are underneath to be paid for.

The node counts are the cleanest form of the claim, because they are counts of the structure rather than of the work. The trie itself grows sublinearly — 7.8 times as many nodes for 9.7 times as many words, since a word added to a large vocabulary mostly extends prefixes that are already there — and the bounded walk grows more slowly still, at 4.9 times. The saving compounds with the vocabulary instead of dividing it, which is what the cells that were never worth having was reaching for from the other direction when it computed only the cells that could matter.

The price of not knowing, paid and re-incurred #

With that in hand the previous page’s closing factor can be re-measured, and it does something unexpected.

The shared search that knows nothing costs 16,958 against a list search that knows the answer at 15,422. Within ten per cent: sharing very nearly pays off, in absolute cells, the whole of what the previous page called the price of ignorance.

And in the same measurement the price of ignorance got larger — 1.70 on a list, 4.66 on a trie. That is not a contradiction and it is the most useful thing on the page. A tight bound is worth more to a shared walk than to a list precisely because of the mechanism above: the earlier a bound can kill a node, the more words die with it, and a bound that is right from the first candidate kills nodes near the root. The list has no such leverage — its bound saves the tail of one table however early it arrives.

There is a way to read that as a disappointment and it is the wrong reading. The factor of 4.66 is not a cost the shared walk incurs; it is a measurement of how much a better bound would still be worth to it, and no search has that bound. What a reader can act on is the absolute figure: 16,958 cells, reached with no oracle, no tuning and no sorted copy of the vocabulary, against 26,203 for the best thing the previous page could build. The widening ratio is the reason to keep looking for a better bound rather than a reason to doubt the structure.

So the two structures are not two constants on the same curve. The thing that a better bound buys is different in kind, and stacking the two savings gets less than the product of them because a shared walk’s cheapest work is exactly the work a good bound would also have removed.

The order that stops mattering #

The list search had one more lever and it was worth a lot: meeting the candidates whose length is nearest the query’s first, which found a good bound sooner and took 40,273 cells to 26,203. That lever is not available to a trie, whose order is fixed by its own shape — and the measurement says it is not needed.

Rearranging the trie moves it by 12%; the list’s two orders differ by 54%. And the worst of the three arrangements still reads a third fewer cells than the best-ordered list. The reason is the same one as before: a list search’s order decides how long it carries a bad bound, and a shared walk’s first few columns already rule out most of the vocabulary whatever order the children are in.

That is a property worth naming, because ordering the candidates was a piece of tuning a real spelling checker would have to get right, would have to re-tune when the vocabulary changed, and would have to store a sorted copy of the vocabulary to use. The shared walk does without it. The site’s check states the opposite — that rearranging the trie costs as much as ordering the list is worth — and requires the measurement to refuse it.

Where the sharing is worth most #

One regime remains, and it inverts the ranking.

At one error a list search told the answer beats the shared search that discovers it, 6,647 against 16,583. At two errors they are level. At three and four errors the shared search that knows nothing beats the list search that knows everything — 22,632 against 32,339, and 27,939 against 46,120.

The reason is that a loose bound is the case where a list pays most and a trie pays least. A bound of four admits a band eight cells wide in every one of 2,424 tables, and admits it whether or not the candidate is plausible; the same bound of four kills a trie node a few letters down and takes a thousand words with it. So the shared walk’s cost rises by 1.7 from one error to four and the list’s by 3.2, and the two lines cross.

This is the regime a looser budget wastes a larger share is about, seen from the side that benefits. It is also the regime that matters: one-error misspellings are the easy ones, and a checker that only handles those is a checker that gives up on exactly the queries a user needs help with.

What is being counted, and what is not #

A cell is a cell and nothing else. Every number here is subproblems given a value, which is the unit the cost is the number of subproblems established for this kind of work. The shared walk’s cells are not cheaper or dearer than a list’s — the arithmetic in each is the same three-term minimum — but the walk does carry a cost the list does not, and it is not counted here: it holds one column per level of the trie on its stack, up to the length of the longest word, where a list search holds two columns. That is a few hundred bytes against a few dozen, and the count is not the time is the standing caution about reading any of these ratios as a speed.

The trie is built once and is not costed. Building it reads every letter of every word — 17,239 of them — which is a twentieth of what one query’s full search costs and is amortised over every query afterwards. A checker that answers one query in its lifetime should not build one. The same trade is priced properly in the dictionary that builds itself, where the structure is the output rather than an accelerator.

The vocabulary is English prose and the sharing depends on that. 17,239 letters over 7,709 prefixes is 2.24 letters a node, and that figure is a property of the corpus. A vocabulary of random strings over a large alphabet would share almost nothing, and the whole of the hero plate’s first factor would vanish; a vocabulary of long shared stems would share more. The measured ratio rises with the vocabulary here — 1.49 letters a node at 250 words, 2.24 at 2,424 — which is the ordinary behaviour of natural language and not a general fact.

Every search is required to return the same answer. All seven strategies are run on all 300 queries and the site’s check refuses any run where one of them reports a different distance, which is the guard against a pruning rule that is fast because it is wrong — the failure the bound the search finds for itself found in the tempting version of the row-minimum rule. The column-minimum rule is checked more directly as well: for every node of a small trie, the minimum of its column is compared against the true distance to each word beneath it, computed by a table that knows nothing about tries.

One bound was not tried. The band — only computing cells within the bound of the diagonal — is applied to both structures here, and there is a second bound available to a trie that is not: a node at depth $d$ whose subtree contains only words of length at least $\ell$ cannot reach a query of length $n$ within $|n - \ell|$ edits. Storing the shortest and longest word under each node is a few bytes a node and would prune with no cells at all.

Still open: the structure that the queries choose #

Everything on this page is a property of the vocabulary. The trie’s shape is decided by the words, the sharing is whatever the words happen to share, and the queries are told about none of it.

That is a choice rather than a necessity. A search that knew which prefixes its queries actually reach could split the ones that are visited often and collapse the ones that are not — the trie becomes a structure fitted to a workload rather than to a dictionary, which is what the filter that feeds the table does one level up when it decides which candidates reach a table at all.

The measurement that follows fits a trie to a stream of queries and asks the question this page cannot: how much of the 30% of nodes a bounded walk visits is the same 30% from query to query, whether collapsing the never-visited part is worth the space it saves, and what happens to both numbers when the queries stop being drawn from the vocabulary the trie was built from — since a spelling checker’s hardest inputs are the words that are not in its dictionary at all, and every measurement here uses a query made by damaging a word that is.