The bound the search finds for itself

The cells that were never worth having closed three attacks on the cost of a dynamic program — the transitions inside a cell, the order the cells are filled in, and which cells exist — and pointed at a fourth that none of them touches. An edit distance is a single number, and almost nothing that asks for one wants the number. A spelling checker wants the dictionary words closest to what was typed. It does not want the distance from the typed word to every other word, and a search that computes those distances and then discards all but the smallest has done most of its work for nothing.

That essay framed the question precisely. When the threshold is known in advance, a band as wide as the answer already says what it costs: only cells within the threshold of the diagonal can matter, so a table of $n$ by $m$ cells shrinks to about $n$ times the threshold. The interesting case is the threshold that is not known, and is discovered as the search runs — the best distance found so far, which falls as better candidates are met. Is the number of cells such a search needs closer to the band’s or to the full table’s?

This page measures it on a real vocabulary: every distinct word of three letters or more in a fixed corpus of twelve essays on algorithms, 2,424 words averaging seven letters, searched for the nearest match to 300 queries made by applying typing errors to words drawn from that vocabulary.

Two ways to stop a table early #

A search for the nearest word walks the vocabulary and computes one edit-distance table per candidate. Two facts let it stop computing a table before it is finished, and both hold for any bound $k$ on the distance that is still worth finding.

The band. A path through the table that reaches cell $(i, j)$ has already made at least $|i - j|$ insertions or deletions, so no cell further than $k$ from the diagonal can lie on a path that costs $k$ or less. Those cells need no value. The same fact gives a rule before any table is started: a candidate whose length differs from the query’s by more than $k$ is at least $k + 1$ away and costs no cells at all.

The row minimum. No cell of a row is smaller than the smallest cell of the row above it. A cell is the cell above it plus one, the cell diagonally above it plus nothing or one, or the cell to its left plus one; the first two are at least the row above’s minimum, and working along the row from its first cell — which is one more than the first cell of the row above — the third never falls below it either. So once every cell in a row exceeds $k$, every cell in every later row does too, and the candidate can be abandoned there.

The plate shows both rules on one candidate. The query is a misspelling of structure, and by the time the search meets stricture it has already found structure at distance 1. So the bound is 1. The band limits each row to three cells, and after six rows no cell is at 1 or below: the $u$ where stricture has $i$ has cost one edit, the missing $t$ costs another, and the table can prove it has passed the bound without reaching the corner. Twenty cells of ninety.

The second rule has a tempting shortcut, and it is wrong. It is natural to look at a row’s last cell — the distance between the query’s prefix and the whole candidate — and abandon when that exceeds the bound. But a later row can bring the last column back down, because a prefix of the query that is far from the whole candidate can be extended into a query that is close to it. The site’s check runs that rule against the correct one on two hundred queries and it fails on the query ranc, returning and at distance 2 where rank is at distance 1. The row’s minimum is the statistic that cannot come back, and it is the one the search uses.

The search that learns its bound #

With both rules in hand, four searches are compared. Every table in full is the definition: compute the whole table for every word and take the smallest corner. Best so far walks the vocabulary in its own order — the order the words first appear in the prose — and bounds each candidate by the smallest distance found among the candidates before it. The first candidate has no bound and costs its whole table; the bound falls as closer words are found. Best so far, by length does the same with the candidates sorted by how far their length is from the query’s. Answer known bounds every candidate by the true nearest distance from the start, which no real search can do; it is the floor the other two are measured against.

All four are run on the same 300 queries, each with one or two typing errors, and the site’s check requires every one of them to find the same distance on every query. They differ only in how many cells they compute to find it.

At the full vocabulary the search that learns its bound computes 40,273 cells per query, a quarter of the full tables’ 156,714. Ordering the candidates by length takes it to 26,203, a sixth. Knowing the answer in advance would take it to 15,422, a tenth.

So the answer to the question is closer to the band. On a logarithmic scale, the best-so-far search in vocabulary order sits a little nearer the known bound than the full tables, and the length-ordered search sits much nearer: its cost is 1.7 times the known bound’s and a sixth of the full tables’.

The four lines are also nearly parallel. Across a vocabulary 9.7 times larger, each of the three bounded searches grows by about 9.3 times, and the full tables by 13.4 times, only because the later words of the prose are longer than its first ones. Each grows in proportion to the vocabulary, because each candidate costs roughly a fixed number of cells whatever else is in the list. A discovered bound does not change the growth of a dictionary search; it changes the constant, and the constant it changes is the cells per word.

What one candidate costs #

Dividing by the candidates each search actually started shows where its cells go. A full table between a seven-letter query and a seven-letter word is about sixty-four cells — 64.7 on average at the full vocabulary, less on the smaller vocabularies because the prose uses its short common words first. A search that knew the answer computes 14.6 cells per candidate it starts, where a band three cells wide down all eight rows of a seven-letter query’s table would be about twenty-four. The known bound comes in under a band’s worth because it rarely finishes a table: of the 1,056 candidates it starts per query, it abandons 1,050 before the corner.

The best-so-far searches spend about twice the known bound’s cells per candidate — 28.6 in vocabulary order, 24.8 in length order. That is not because their bound is usually loose. It is because the bound is loose at the start: until the search meets a candidate within the true distance, it bounds each table by something larger, and a larger bound means a wider band and later abandonment for every candidate in that stretch. The first candidate of all is bounded by nothing and costs a whole table.

What ordering by length buys #

The length rule does most of the pruning on this plate. At the full vocabulary, a search that knew the answer rules out 1,368 of the 2,424 words by length alone and starts a table for the other 1,056. The best-so-far search in vocabulary order starts 1,409, because in the early part of its walk its bound is still too large to rule anything out by length.

The length-ordered search starts exactly as many as the search that knew the answer: 120, 232, 445, 800 and 1,056 at the five vocabulary sizes. That is not a coincidence of these queries; it follows from the order. Sorting by length difference puts every word within the true distance $d$ of the query’s length before every word beyond it. While the search is among the first group, its bound is never below $d$, since no candidate can beat the true answer, so none of them is ruled out by length. By the time it reaches the second group it has met the nearest word, whose length is within $d$, so its bound is exactly $d$ and every remaining word is ruled out exactly as the known search rules it out.

So ordering by length recovers the known bound’s choice of candidates completely. What it cannot recover is the known bound’s width on the candidates it meets before the answer, and that is the whole of the remaining factor of 1.7.

That order is an instance of a pattern the graph searches measured earlier depend on. The length difference between two words is a lower bound on their distance that costs nothing to compute, and an estimate borrowed from an easier problem is this collection’s account of what such a bound is for: it decides what to look at first, and a search guided by a lower bound meets the answer earlier and wastes less before it.

When the answer is close #

Sweeping the number of typing errors moves the true distance, and it separates the cost of the band from the cost of discovering it. The full tables do not care what the answer is: about 160,000 cells at every setting. The known bound cares a great deal. With one error the nearest word averages 0.97 away and the known search computes 6,934 cells; with four it averages 2.78 away and the known search computes 45,957, since a wider bound means a wider band, later abandonment and fewer words ruled out by length.

The discovering searches rise more slowly, and the gap between them and the known bound closes. In length order the search costs 2.59 times the known bound with one error, 1.53 times with two, 1.28 with three and 1.20 with four. In vocabulary order the ratios are 5.10, 2.41, 1.70 and 1.45.

That is the price of discovery, measured from the other side. When the answer is far, the bound the search carries while hunting for it is not much looser than the true one, so hunting costs little extra. When the answer is close — the ordinary case for a spelling checker, where most misspellings are one keystroke — the true bound is very tight, and every candidate met before the answer is computed under a bound several times wider. The discovered bound is closest to knowing where knowing would help least.

Where the extra cells go #

The cost of not knowing can be located exactly, by splitting each search’s cells at the moment it meets the word that sets its final bound. Over the queries with one or two errors, a search that knew the answer spends 6,703 cells before that moment and 8,719 after it. The best-so-far search in vocabulary order spends 31,554 before and the same 8,719 after — the same, because from that moment it walks the same words under the same bound. In length order it spends 16,839 before and 9,364 after.

So the whole of the gap is in the stretch before the answer is found, and none of it is after. With one error the stretch before costs the length-ordered search 14,195 cells against the known search’s 3,174, while the cells after are 3,767 and 3,761. With four errors the stretch before costs 21,908 against 15,248, and the cells after dominate both. A search that could meet the nearest word sooner would close the gap, and nothing else would.

A distance of 0.97 with one error means some errors land on another real word. The searches here do not stop when they find a distance of zero, which is a refinement worth having: nothing can beat a word the query spells exactly, and a search that notices can end there.

Where the bound comes from #

Three sources of a bound have now appeared for this recurrence, and setting them side by side says what this page adds.

A band as wide as the answer measured a band chosen before the computation, and Ukkonen’s doubling, which finds a band for a single pair by trying 1, 2, 4 and so on until the answer fits. Doubling pays in proportion to the distance of the pair it is computing. In a dictionary search nearly every candidate is far from the query — an unrelated word is most of its length away — so doubling each candidate’s band until its own distance fits would spend most of the full table on words that were never contenders.

The best-so-far bound comes from other candidates. Once any word within distance 1 has been found, every later candidate is computed as if its own distance were at most 1, whatever it actually is, and the question each table answers changes from how far is this word to is this word closer than the best so far. The second question is almost always answered no, and a no is cheap: it takes a few rows.

That change of question is the fourth attack the earlier essay asked for. The cost is the number of subproblems says a dynamic program costs its cells, and the cells are not the cost qualified it with the transitions per cell; both take for granted that every cell’s value is wanted. Here most cells’ values are never wanted, because the question asked of most tables is a yes-or-no question with a threshold, and the threshold is supplied by the answers to other tables. The subproblem set is decided by the whole search, not by any one table in it.

What the measurement leaves out #

Queries drawn uniformly from the vocabulary. Real misspellings come from common words far more often than from rare ones, and a vocabulary sorted by frequency would meet the answer earlier in its walk. The vocabulary order here — the order the prose first uses each word — is roughly that, and it still loses to ordering by length; a combination of the two is not measured.

Random typing errors. Real errors are not uniform over insertions, deletions and substitutions, and transposed neighbouring letters are among the commonest. A corpus that was not generated is the standing warning that generated inputs have the statistics they were given.

Cells as the whole cost. Sorting the vocabulary by length difference costs a pass per query, or nothing if the vocabulary is kept in buckets by length, and the plates charge neither. A table computed in machine words changes the unit from a cell to a word operation, and a bound can be applied to that computation too, with different constants.

Rows kept. Every search here keeps two rows of each table, as the table nobody has to keep showed is enough for a distance; none of them needs the table itself, since no alignment is wanted.

Still open: the columns the candidates share #

Every candidate on this page gets its own table, and the tables are not independent. Structure, structures and structured share their first nine letters, and the first nine columns of the query’s table against each of them — if the table is laid out with the candidate along the columns — are identical. A vocabulary stored as a trie lets a search compute each shared column once, at the trie node where the prefix ends, and abandon a whole subtree of words the moment a column at that node exceeds the bound.

The measurement that follows repeats this page’s searches over the same vocabulary stored as a trie, and asks how many cells the sharing saves with no bound, with the best-so-far bound, and with the bound known — and whether abandoning subtrees makes the order of candidates matter less, since a trie’s order is fixed by the alphabet rather than chosen for the search.