Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Pruning — where it appears

Discarding candidates without examining them, using a bound derived from the triangle inequality — which silently discards real answers when the inequality is false. It is safe only under a metric, and under a plausible non-metric cost model it silently discards more than one candidate in eight that should have been kept.

Named by 13 essays across 6 fields — each of them below, with the objects they name alongside it.

—abrocadabro—abracadabra012101221012210122112222123321233212332123321233212322one unit = one subproblem given a value54 of 144 cells, 90 skipped

A band as wide as the answer

If two strings are close, the optimal route stays near the diagonal and nine cells in ten cannot be on it. A band of three finds the right answer on a pair 300 characters long — and a band of thirty-two is needed before anything can prove it.

tables · Distance 01234567891011120123456789101112122332223333122222332231222222223122222233122222221222222122222122221222122121one unit = one subproblem given a value91 cells, 156 transitions, 1.7 per cell

The argmin that cannot go backwards

The same triangular table, the same ninety-one cells, the same tree at the end of it — and 364 transitions one way against 156 the other. At 256 keys the ratio is 38. What removes the factor is not a property of the recurrence but a property of the numbers it is given, and the recurrence does not mention them.

tables · Table pairs where the two disagreerestricted · unrestrictedab → bca3 against 2ac → cba3 against 2ba → acb3 against 2bc → cab3 against 2ca → abc3 against 2triples the restricted rule breaksab → bca costs 3, but by way of ba it costs 2ac → cba costs 3, but by way of ca it costs 2ba → acb costs 3, but by way of ab it costs 240 strings, 1,600 pairs, 64,000 triplesunrestricted: 0 triples broken

The edit that reaches back two rows

Swapping two adjacent characters is one keystroke and costs two edits. Adding it as a fourth transition is four lines, it is what nearly everything ships, and the function those four lines compute is not the one they are named after. Over 1,600 pairs of short strings the two definitions differ on twelve, and the shipped one breaks the triangle inequality on twelve triples where the other breaks it on none.

tables · Cost 10010³10⁴10⁵errors allowed, kacts01234index walkthe whole table4,000 characters · m = 16 · 4 symbolscrossing at k = 4

The branches an error opens

The tree multiplies by 19.6 for the first error, 12.3 for the second, 10.3 for the third and 8.8 for the fourth. A branching factor of four on a sixteen-character pattern would predict sixty-four, and the gap between sixty-four and eight is the intervals emptying.

bounds · Distance 10010³10⁴errors allowed, kacts0123index walkthe whole table3,000 characters · m = 20 · 4 symbolsno crossing in range

The search that spends a budget

A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.

indexes · Distance 10³10⁴10⁵words in the vocabularysubproblems given a valueevery table in full · 1.16best so far · 0.99answer known · 0.96one unit = one subproblem given a valuesubproblems given a value, n from 250 to 2424

The bound the search finds for itself

A spelling checker that computes the full edit-distance table against every word in a 2,424-word vocabulary fills 156,714 cells for each misspelt query. Bound each table by the best distance found so far, and abandon it the moment a whole row exceeds that bound, and the same search fills 40,273 and finds the same words. Meet the candidates nearest in length first and it fills 26,203, starting a table for exactly the words a search that knew the answer in advance would start. The last factor of 1.7 is the price of not knowing, and it is largest when the misspelling is smallest.

tables · Table 010010³10⁴interval extensions—48.1%68.5%69.8%errors allowed · share removed belowno pruningpruned on D4,000 characters · m = 1669.8% removed at k = 3

The branch that cannot reach an answer

Seventy-two rank operations over the pattern remove 27,906 of the 39,957 interval extensions a bounded-error index walk performs — 70% of the tree, at a budget of three. The share grows with the budget, which is what a pruning has to do to be worth its cost.

bounds · Distance 10³10⁴10⁵words in the vocabularysubproblems given a valueevery table in full · 1.16a trie, no bound · 0.99best so far · 0.99a trie, best so far · 0.82one unit = one subproblem given a valuesubproblems given a value, n from 250 to 2424

The columns the candidates share

Three thousand tables against one query, and most of them begin the same way. Stored as a trie, the 2,424-word vocabulary has 7,710 distinct prefixes holding 17,239 letters, and a search that computes one column per prefix reads 61,449 cells against 156,714 — before it applies any bound at all. Apply the bound at a prefix instead of at a word and it reads 16,958, beating a list search that was told the answer in advance.

tables · Table 1632649612810³10⁴10⁵table sizesplit points appliedevery splitbounded per blockbounded per cell, by lengthweights satisfying the quadrangle inequalityall three compute the same table

The bound a block can and cannot have

Knuth's condition turns an interval table's cubic fill into a quadratic one by bounding each cell's best split between its two neighbours'. A blocked fill cannot use it a cell at a time, and the two cells that bound a block lie outside the block — one to its left, one below it. The schedule has finished both for ten per cent of the blocks, the bound then removes eleven per cent of the splits, and it removes half a per cent of the cache misses, because the splits it skips are the ones already in the cache.

tables · Table unit cost — triples broken0.02%unit cost — pivot bound failed0.02%log-odds on a keyboard walk — triples broken6.61%log-odds on a keyboard walk — pivot bound failed13.22%42,840 triples per model, enumerated0.02% shown where the true rate is zero

A distance that is not a distance

Under unit cost the edit distance obeys the triangle inequality and this site asserts that it does. Under a stated substitution matrix it need not, and on 42,840 enumerated triples it fails 2,832 times — taking with it every structure that prunes by distance, at a measured 13.22% of the bounds they rely on.

wrong · Cost atgaattcatgagtgacaag00000111111112222222errorsthe pattern, left to right · D belowleast errors neededD, the bound4 symbols · m = 2090 ranks · 2 resets

The errors the rest of the pattern needs

Read the pattern left to right in an index of the reversed text and count the points where the interval empties. That count is a lower bound on the errors any alignment of the prefix must contain, it costs 72 rank operations, and it removes 70% of a search tree.

text · Distance ranks to compute D72extensions removed27,906extensions remaining12,051one search · k = 3 · 4,000 charactersand one more index: 17,033 bits4,000 characters · m = 16388 extensions a rank

A bound that has to be paid for

The pruning removes seventy per cent of a search tree for seventy-two rank operations. It also needs an FM-index of the reversed text — 17,033 bits against the forward index's 17,032 — which doubles the structure whose small size was the entire argument for walking an index.

space · Distance atgaattcatgagtgacaag00000111111112222222errorsthe pattern, left to right · D belowleast errors neededD, the bound4 symbols · m = 2090 ranks · 2 resets

The pruning that loses an occurrence

Two versions of the same lower-bound pruning, each one character away from correct. Both return only real occurrences, both return fewer of them, and no check that asks whether the answers are right can tell either from the truth.

wrong · Distance

Named alongside it

The objects these essays reach for when they reach for this one.

Edit distanceDynamic programmingMeasurementApproximate matchingBacktracking searchError budgetLower boundFM-indexSubproblemCost modelMeasured countTrade off

All concepts