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

Q gram — where it appears

A substring of exactly q characters, counted with multiplicity over a pattern or a window. One error destroys at most q of them, which is what lets a count of shared q-grams decide whether a window is worth verifying.

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

k = 0k = 1k = 2k = 3k = 4k = 5k = 6q = 223211917151311q = 3221916131074q = 4211713951-3q = 520151050-5-10q = 6191371-5-11-17q = 81791-7-15-23-31a shaded cell is a threshold of zero or less: every window proposedt = m + 1 − q(k+1) · m = 2411 collapsed cells

The q-grams an error cannot destroy

A pattern of twenty-four characters holds twenty-one four-grams. Two errors can destroy at most eight of them, so any occurrence with two errors still shares thirteen — and a filter that keeps only the windows sharing thirteen proposes 104 of 3,977 and computes 16,744 table cells instead of 96,000.

text · Distance 00.1000.2000.30000.2500.5000.7501misspelt vocabulary words correctedunfamiliar words given a false suggestionat 1at 2at 3at 4cap aloneeach point: one threshold, with the cap of twoup and right: the cap alone

The triples a typo writes

A spelling checker capped at two edits keeps every correction it could make and still gives a false suggestion to 72% of the unfamiliar words it answers, because on short words distance cannot tell a typo of a vocabulary word from a word the vocabulary lacks. The query's letters were proposed as the second test: decline a query whose letter-triples the vocabulary has never seen. They cannot separate the two either. One edit writes about one unseen triple into any word, familiar or not, while an unfamiliar word brings 0.59 of its own, and two thirds bring none. Declining at two unseen triples removes a quarter of the false suggestions and costs half the corrections — twenty-two corrections for every false suggestion removed.

tables · Table 0.010.11errors allowed, kshare of windows proposed01234q = 3q = 4q = 5a shaded dot is a collapsed thresholdm = 24 · n = 4,000 · 6 planted1 collapsed rows

The threshold that reaches zero

At q = 5 and four errors on a twenty-four-character pattern the filter demands zero shared q-grams, proposes all 2,977 windows, and computes 986,266 table cells where filling the whole table would have cost 96,000. The failure is arithmetic and is knowable before a character is read.

wrong · Distance the whole table60,00060,000r · 0rkcounting filter24,84315,369r · 0rkseed filter17,7452,415r · 1,377rkindex walk00r · 177,046rkn = 3,000 · m = 20 · q = 4cells drawn · r = characters read, rk = index rankscells computed6 occurrences

Three savings in three currencies

The same six occurrences, found four ways. The table computes 60,000 cells and reads 60,000 characters. The counting filter computes 6,251 cells and reads 13,022 characters. The seed filter computes 3,325 and reads 550. The index walk computes none, reads none, and performs 18,645 ranks.

wrong · Distance

Named alongside it

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

Edit distanceApproximate matchingCounting filterFilteringMeasurementSeed-and-extendSelectivityVerificationFalse-positiveThresholdUnit of costAlphabet size

All concepts