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

Metric — where it appears

A distance satisfying non-negativity, identity, symmetry and the triangle inequality, of which a stated substitution matrix generally satisfies the first three. A stated substitution matrix generally satisfies the first three properties and not the fourth, which is a fact to check rather than a law to assume.

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

cost per column of the alignmentab / ba1.00 over 2 · 0.67 over 3kitten / sitting0.43 over 7 · 0.43 over 7intention / execution0.56 over 9 · 0.50 over 10gattaca / gactata0.29 over 7 · 0.29 over 7abracadabra / abrocadabro0.18 over 11 · 0.18 over 11unit cost, in edits per columnupper bar: the optimum, divided · lower bar: the best rate

A distance divided by a length is not a rate

Two substitutions turn "ab" into "ba", a distance of two over an alignment of two columns — a rate of 1.00. Deleting, matching and inserting also costs two, over three columns, for 0.67. Both are alignments of the same pair, the second has the better rate, and the optimal alignment is not the one that achieves it. Over every pair of strings up to three characters on three letters, 21% disagree.

tables · Cost 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 —gactacgat—gattacagt0123456789101234567821012345673211123456432212345554332123456543321234765443222387655432339876554333one unit = one subproblem given a value100 cells, 100 held at once

A distance that is a path through a grid

How far apart two strings are is a shortest-path problem on a grid whose every edge is drawn by the recurrence — and finding a string in a text costs 4,988 character comparisons where measuring how far it is from one costs 96,000.

text · Distance 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

Named alongside it

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

Cost modelEdit distanceAlignmentDynamic programmingHonest limitFailure modeMeasured countPruningRecurrenceTriangle inequalityApproximate matchingCharacter comparison

All concepts