The edit that reaches back two rows

teh for the. recieve for receive. A transposition — two adjacent characters in the wrong order — is the commonest typing mistake there is, it is one motion of two fingers, and under every model on this ladder it costs two edits: a substitution to fix each position.

So the operation gets added. The recurrence gains a fourth transition, reaching back two rows and two columns, taken when the two characters are crossed. It is four lines, it is in the standard reference implementations, and it produces a function that is not the one the reference is named after.

There is a reason to care beyond tidiness. The two functions differ on about three pairs in a thousand — a rate low enough that a test suite drawn at random needs several hundred cases to see one, and low enough that nobody who ships the four-line version ever finds out. What the difference costs is not the extra edit; it is a property the four-line version quietly does not have, and which anything that indexes strings by distance is built on.

The four lines, and the restriction hidden in them #

The ordinary table’s cell is a minimum over three predecessors. Adding a transposition adds a fourth:

$$d(i,j) = \min\big(\dots,\ d(i-2, j-2) + 1\big) \quad \text{when } a_i = b_{j-1} \text{ and } a_{i-1} = b_j$$

That is the whole change. It is called the optimal string alignment distance, or the restricted Damerau distance, and it is what most libraries compute when they offer a Damerau distance.

The restriction it imposes is not stated in the code and is easy to miss: no substring may be edited more than once. A transposition may not be combined with an insertion between the two characters being transposed, because reaching back exactly two rows assumes the two characters are still adjacent in both strings, and an intervening edit breaks that assumption.

The shortest case where it matters is three characters long. Turning ca into abc: transpose ca to ac, then insert b in the middle — two operations. The restricted rule cannot do it, because the b lands between two characters it has already transposed, so it reports three. The unrestricted definition reports two, and two is correct under the definition both are named for.

It is worth noticing how the restriction arises rather than being imposed. Nobody writes and no substring may be edited twice into the four lines; the clause is a consequence of reaching back exactly two rows, and it has to be discovered by working out what the transition can and cannot express. That is the ordinary situation with a recurrence — the definition is not the algorithm is the theme this collection has for it — and it is why a table’s behaviour has to be enumerated rather than read off its cells.

What the unrestricted version needs #

Computing the real Damerau distance takes a second table, and it is worth seeing why the shape changes rather than the constant.

The unrestricted transposition can move two characters past material that has since been deleted, so the transition does not reach back a fixed distance. It reaches back to wherever the matching character last occurred, which is a quantity that has to be carried: one last-seen row per symbol of the alphabet, updated as the fill proceeds, plus one last-matching column within the current row.

The cell then considers a transition from $d(i_1, j_1)$, where $i_1$ is the last row whose character equals $b_j$ and $j_1$ the last column whose character equals $a_i$, plus the cost of deleting everything between. That is still a constant number of transitions per cell, so the class is unchanged; what changes is that the recurrence’s dependencies are no longer local. A cell can depend on a cell arbitrarily far above and to the left, which means the rolling frontier of the table nobody has to keep is not available: two rows are not enough when a transition can reach back to row three.

That is a real consequence and it explains part of why the restricted version is the one that ships. The restricted rule reaches back two rows, so a three-row frontier suffices and the space stays linear. The unrestricted rule needs the whole table, or at least a row per distinct symbol, and on a large alphabet that is the table again.

There is a third route, and it is the one a careful implementation takes when it wants the restricted rule’s space and something closer to the unrestricted rule’s answer: bound how far back the transition may reach. Allowing a transposition to span at most $k$ intervening characters needs $k+2$ rows and computes a function between the two, converging on the unrestricted one as $k$ grows. That is a parameter, it interpolates two functions that are usually presented as alternatives, and it is the same shape as the dial between two structures in the external-memory field — two named designs turning out to be the ends of one axis.

Why the inequality fails, with the witness #

The triangle inequality says $d(x, z) \le d(x, y) + d(y, z)$ for every triple. Under the restricted rule there are triples where it does not, and the smallest is on strings of two and three characters:

Three against two. The route by way of ba transposes and then inserts; the direct computation cannot do both to the same characters, so it pays three.

The failure is not an artefact of the implementation. It is the restriction itself: a distance that forbids editing a region twice is not a distance on which paths compose, because a two-step route is exactly a route that edits some region twice.

Every structure that prunes by distance rests on that composition. A metric tree, a pivot filter, a ball tree — each of them discards a candidate on the grounds that it is too far from a pivot to be near the query, and each of those arguments is the triangle inequality. Fed a distance function that breaks it on three thousandths of triples, they discard candidates that should have been returned, at a rate nobody measures because the answer is a shorter list rather than an error.

That is precisely the failure a distance that is not a distance measured for a substitution matrix — 2,832 broken triples of 42,840, and 13.22% of a pruning structure’s bounds unsound. The rate here is far smaller and the mechanism is identical, and the smaller rate is worse rather than better: a defect at 13% is found in testing, and a defect at 0.3% is not.

The rate is worth putting in a sentence a reader can use. Twelve pairs in 1,600 is 0.75%; twelve triples in 64,000 is 0.019%. A structure that prunes performs one inequality test per pruning decision, so a search over a dictionary making a thousand pruning decisions has about a one-in-five chance of making at least one unsound one — and an unsound decision does not produce an error, it produces a shorter list of results. The failure has no signature at all, which is what makes a rate this low worse than a rate ten times higher.

What a fourth transition does to the accounting #

This field reports two numbers for every table and both move here.

The cells do not change. Neither the restricted nor the unrestricted version alters the subproblem set, so nothing on this page is the kind of change the cells that were never worth having is about. Both versions fill $(n+1)(m+1)$ cells, both give every cell a value, and the subproblem set is untouched. Whatever else is different, this is not a different table.

The transitions per cell go from three to four, on the cells where the characters are crossed, which is a small fraction. Measured over the enumeration the average is barely above three.

And the unrestricted version carries a symbol table, one entry per distinct character in the two strings. That is $O(\sigma)$ space beside the table, invisible in a cell count, and it is the same kind of omission measuring what an algorithm keeps exists to catch — an auxiliary structure that no count of the main one reports.

So the two versions are in the same class, cost within a few per cent of each other, and differ in a property that no count on this site can see. The thing that separates them is not a resource. It is what they compute, and this collection’s counters are all instruments for measuring how much rather than what.

Why the operation is worth adding at all #

Nothing above argues against the transposition; the whole page assumes it earns its place, and it is worth saying why, since the assumption is doing work.

The case for it is empirical rather than mathematical. Studies of typing errors put transpositions at somewhere between a tenth and a fifth of all single-error mistakes, and under a model that charges two for them, a transposed word is as far from its target as a word with two independent wrong letters. A spelling corrector ranking candidates by distance will therefore rank a genuinely-two-error candidate level with a one-keystroke one, and the ranking is the product.

Charging one restores the ordering, and it does so for the same reason a cost that is not one gives for any graded model: the cost is meant to reflect how likely the difference is to have arisen, and a rule that prices two likely things differently from one unlikely one is a better rule for the question being asked.

What that argument does not settle is the value. One is a round number rather than a measured one. A fitted model would give the transposition whatever the log-odds of a transposition against a random pair of errors turns out to be, which is neither one nor two and which depends on the corpus — and that is the direction the end of this page points.

Which one anybody actually wants #

The honest answer is that for the application people have in mind, the restricted version is usually adequate and its defect is usually harmless.

Spelling correction over a dictionary compares a query against candidates one at a time, uses the distance as a score, and never composes two distances. The triangle inequality is not being relied on, so its failure costs nothing. The twelve-in-1,600 disagreement is a difference of one edit on strings where a human would call both answers reasonable.

The defect becomes real in exactly one situation: when the distance is used to prune. An index over a large dictionary that keeps candidates in a metric tree, a nearest-neighbour search that uses a pivot bound, a clustering algorithm that assumes distances compose — each of those turns a harmless approximation into missing results.

So the useful statement is not that one implementation is wrong. It is that two different functions ship under one name, the documentation of neither says which, and the difference between them is exactly the property that decides whether a whole class of structures may be built on top. A caller who knows that can choose. A caller who does not has already chosen.

What the check has to be able to reject #

An assertion that has never rejected anything proves nothing, and there are two ways this page’s claims could be true of a broken implementation rather than of the definitions.

A transposition rule that does nothing. If the fourth transition were never taken — a subscript wrong by one, a condition testing the wrong pair — the “restricted” distance would simply be the Levenshtein distance, it would agree with itself everywhere, and it would satisfy the triangle inequality perfectly. The plate would then report zero disagreements and zero broken triples, and would look like a page arguing that the two definitions are the same. So the check requires ab against ba to cost one rather than two, which is the smallest possible evidence that the transition fires at all.

An unrestricted implementation that is merely a different bug. The unrestricted version is the harder of the two to write and the one with no reference to check against, so agreeing with the restricted version everywhere would be as suspicious as disagreeing everywhere. It is held to three things: it must differ somewhere, it must satisfy the triangle inequality on every one of the enumerated triples, and it must give two on the hand-checkable ca to abc. The third is the one a person can verify without running anything.

That pair of requirements — a check that must fire and a check that must not — is the standing habit of this collection, and it is the reason the numbers on this page are worth the space they take. The check must reject is the theme; here it is what separates a measurement of two definitions from a measurement of two spellings of one.

What is not measured here #

The enumeration stops at four characters, in the same way a distance that is not a distance enumerates its own triples and for the same reason: past that the count of pairs outruns an exhaustive check. Beyond that the number of pairs grows faster than an exhaustive check can follow, and every rate on this page is a rate over short strings. The disagreement rate on realistic words is unmeasured and there is reason to expect it to be higher, since a longer string has more room for an intervening edit.

Only unit costs are used. Under a graded model the transposition’s price becomes a fourth parameter beside the substitution and gap costs, and a cost that is not one is the argument that a fourth parameter is a fourth decision rather than a refinement. A transposition costs one here. Under a model where it costs less than one — which is the point of adding it, since it is one keystroke — the disagreement rate changes and is unmeasured.

And no pruning structure is actually run. The claim that a broken inequality costs a metric tree candidates is inherited from the earlier rung, which measured it, rather than demonstrated again here. The rate at which this violation would cost a real index candidates is a different number from the one that essay reports, and nothing on this page computes it.

Where this ladder goes from here: the model that was fitted rather than chosen #

Every cost model on this ladder has been a stated rule: substitutions cost one, or two, or the log-odds of a drift; gaps cost a constant or an affine pair; transpositions cost one. Each was written down and then measured against.

That is the right practice for a collection that refuses to quote published tables, and it leaves the largest question in this field untouched. Where do the numbers come from?

The answer in every serious application is that they are fitted: a substitution matrix is estimated from a corpus of known correspondences, by counting how often each pair is aligned and taking the log of the ratio against what chance would give. The matrix is therefore a statement about a corpus, not a statement about the alphabet — and two corpora give two matrices, which give two optimal alignments of the same pair, which is a cost that is not one’s finding with the model’s provenance attached.

The rung that follows this one is that estimation, done rather than described: build a matrix from a stated corpus of correspondences, measure how much the alignment moves when the corpus changes, and find out whether the sensitivity is small enough for the fitted numbers to be treated as constants. If it is not — and the affine and metric results on this ladder both suggest it will not be — then every alignment score in use is conditional on a corpus that nobody reports beside it.