A distance divided by a length is not a rate

Three edits between two five-character words. Thirty edits between two five-hundred-character documents. The same distance, in the same unit, computed by the same recurrence — and nobody would call them the same amount of difference.

So the number gets divided by something. Every practical use of an edit distance divides it: by the longer string’s length, by the shorter one’s, by their sum, by the length of the alignment. The division is so obvious that it is rarely written down as a step, and the thing it produces is called a normalised distance and treated as the distance in different units.

It is not. It is the answer to a different question, and the recurrence above it is answering the first one.

The confusion is worth naming precisely, because it is not carelessness. Dividing a quantity by a size is the right move for almost everything: a cost per item, a rate per second, an error per sample. In all of those the numerator is a sum over the very things the denominator counts, so dividing is genuinely a change of units. Here the denominator is not a count of the input at all — it is a property of the solution, and the solution is what was being optimised. Dividing by something the optimiser chose is the step that does not commute.

What the two optimisations are #

Write an alignment as a sequence of columns: each column is a matched pair, a substituted pair, or a character against a gap. Its cost is the sum of the column costs and its length is the number of columns.

The plain edit distance minimises the cost:

$$d(a,b) = \min_{\text{alignments}} \operatorname{cost}(A)$$

and the thing people want is the minimum of the rate:

$$\rho(a,b) = \min_{\text{alignments}} \frac{\operatorname{cost}(A)}{\operatorname{length}(A)}$$

Those are different minimisations over the same set. Dividing the first by the length of the alignment that achieved it evaluates the quotient at one particular point of the set, and the minimum of a quotient over a set is not generally the quotient evaluated where the numerator is least.

The counter-example is two characters long and can be checked by hand. For “ab” against “ba”, the cheapest alignment substitutes both characters: cost two, two columns, rate 1.00. Another alignment deletes the a, matches the b, and inserts an a: cost two — a deletion and an insertion — over three columns, rate 0.67. The numerator is the same and the denominator is larger, so the second wins on the rate and loses nothing on the cost. An alignment can pay for extra length with nothing at all.

It is worth seeing why that particular move is available, since it is the mechanism behind every disagreement on this page. A substitution and a delete-plus-insert cost the same under unit cost — one for the substitution, one each for the two gap characters, so two either way. They differ in length: one column against two. So wherever a substitution appears in an optimal alignment, splitting it costs nothing and adds a column, which lowers the rate. Under unit cost the two operations are priced identically and measured differently, and that gap is the whole of the effect. Under a model where a substitution costs less than two gap characters the move is not free and the disagreements become rarer.

Why an alignment can be lengthened for free #

The mechanism deserves its own paragraph, because once it is stated the twenty-one per cent stops being surprising and starts being predictable.

Under unit cost there are exactly two ways to account for a pair of characters that differ: substitute one for the other, at a cost of one in one column; or delete one and insert the other, at a cost of two in two columns. The second is dearer in cost and cheaper in rate — two over two is one, against one over one, which is also one. Equal, in that case. The interesting move is elsewhere: take an alignment containing a match and a substitution side by side, and re-cut it so that the substitution becomes a deletion and an insertion straddling the match. The cost rises by one and the length rises by one, and if the alignment’s existing rate is below one, adding a column at a rate of one raises it. If the existing rate is above one — impossible under unit cost, since no alignment costs more than one per column — it would lower it.

So under unit cost the rate is bounded above by one and every alignment with a substitution has a nearby alignment one column longer at the same or better rate. Which of them is optimal depends on the arithmetic of the particular pair, and the enumeration says that on a fifth of short pairs the arithmetic goes the way the plain optimum does not.

Finding the real minimum #

Minimising a quotient over a set is a solved problem and the solution is short enough to state completely.

Guess a rate $\lambda$. Ask for the alignment minimising $\operatorname{cost}(A) - \lambda \cdot \operatorname{length}(A)$, which is an ordinary edit-distance fill with every column’s weight reduced by $\lambda$ — the same rectangle, the same three transitions, a different constant. If the minimum comes out negative, some alignment costs less than $\lambda$ per column, so take its rate as the new $\lambda$ and repeat. If it comes out zero, no alignment beats $\lambda$ and $\lambda$ is the answer.

That is Dinkelbach’s method, it converges in a handful of rounds — two on every pair drawn on this page — and each round is one fill of a rectangle the recurrence already knows how to fill. The cost of the right answer is a small constant multiple of the cost of the wrong one, which is worth knowing because the usual reason given for dividing afterwards is that the real thing is expensive.

The convergence deserves a sentence. Each round’s $\lambda$ is the rate of an actual alignment, so it is an upper bound on the answer; each round either finds a strictly better alignment or proves none exists. There are finitely many alignments, so it terminates, and in practice it terminates immediately because the second round usually proves the first round’s alignment optimal.

There is a second thing the method makes visible and it is worth having explicitly. The modified fill — every column’s weight reduced by $\lambda$ — is an ordinary edit-distance computation under a different cost model, and the search is therefore a search over cost models for the one whose optimum has rate exactly $\lambda$. That reframes the whole exercise: normalising is not a post-processing step at all, it is a statement that the right cost model was not known in advance and has to be found. The cost model is an input is the theme this collection has for the idea, and here the input turns out to be computable from the requirement rather than chosen by hand.

Which denominator, and why the question has no answer #

The formulation above normalises by the alignment’s length, and that is one choice among several. The alternatives in use are the longer string’s length, the sum of the two lengths, and the mean of them. They give different numbers, they induce different orderings on a set of candidates, and none of them is the correct one.

The reason there is no correct one is that the quantity being asked for does not exist independently of the choice. How different are these two strings, per unit of string is not a well-posed question until “per unit of what” is fixed, and each fixing produces a different function with different properties — one of which is worth naming because it is usually what the caller assumed.

Normalising by the longer string preserves the triangle inequality under unit cost, and normalising by the alignment’s length does not. So a system that indexes strings by a normalised distance and prunes on the inequality is relying on a property that depends on which denominator was chosen, and the choice was probably made for readability. That is precisely the failure a distance that is not a distance measured for a substitution matrix, arriving from the denominator instead of from the numerator: the same structure, the same pruning, the same silent loss of candidates.

A second property is worth checking against, because it is the one people rely on without noticing. The plain edit distance is zero exactly when the strings are equal, and every reasonable normalisation preserves that — a rate of zero means every column matched. What is not preserved is the scale: a rate is bounded above by the dearest column cost, so under unit cost every normalised distance lies in $[0, 1]$ and the numbers look like probabilities. They are not probabilities, nothing about them is calibrated, and a threshold of 0.2 chosen because it “sounds like twenty per cent different” is a threshold chosen on the appearance of the units. That is the same class of mistake the error names its denominator exists to flag in the streaming field, arriving here through a division nobody thought of as a modelling step.

What the disagreement rate is a statement about #

Twenty-one per cent of pairs disagreeing sounds like a lot, and the number needs qualifying in both directions.

It is measured on very short strings, in the way a distance that is not a distance enumerates its triples, and short strings are where the effect is largest: an extra column is a third of a three-column alignment and a hundredth of a hundred-column one. On long strings the two answers converge, because the length an alignment can buy is bounded by the number of gaps it can afford and the cost of those gaps grows.

And the disagreements are small when they occur. The largest gap over the three-letter enumeration is the “ab”/“ba” case, at 1.00 against 0.67 — a third — and most are far smaller. The average disagreement is a few per cent.

So the honest form of the finding is: the two are different functions, the difference is exhibitable on two-character strings, and on the lengths people actually use it is a small perturbation rather than a different answer. That is a weaker claim than the plate’s headline and it is the claim the plate supports. This collection has a habit of stating the strong version first and the qualification immediately after, and the reason is that the strong version is what makes anybody look, and the qualification is what makes the number usable.

The case where it is not a perturbation is worth naming: when the two strings are of very different lengths. Aligning a five-character query against a five-hundred-character document, the cheapest alignment is dominated by gaps and its length is nearly five hundred, so the rate is nearly the deletion cost; a shorter alignment matching a region and stopping is a completely different rate. That is the local-alignment question of the previous rung arriving in the denominator, and it is why the two ideas are usually implemented together.

The one that gets used, and why #

Almost every implementation divides. Almost none performs the parametric search.

The reason is not that anybody weighed the two and chose. It is that dividing does not look like a decision — it looks like a change of units, in the way that dividing a distance in metres by a time in seconds looks like a change of units. The step where an optimisation is replaced by a different optimisation happens silently, inside an arithmetic operation that appears to be doing nothing.

That is the recurring shape of this whole field. A cost that is not one found four numbers on one table of which only one was a count; a cell that has to know where it is found a gap model that a single table cannot express; and here a division changes the objective. In every case the change is invisible because the output has the same type as before, and a number that arrives in the expected shape is not questioned.

What a rate is for, and the two things it is asked to do #

It helps to separate the two jobs a normalised distance is put to, because they want different things and only one of them is served by the minimum.

Thresholding. Are these two strings close enough? This is what a spell checker, a record linker and a duplicate detector do. It wants a number that can be compared against a constant across pairs of very different lengths, and it wants the comparison to be conservative in a stated direction. For this job the minimum rate is arguably the wrong quantity: taking the best rate over all alignments means a pair can pass a threshold on the strength of an alignment nobody would call a correspondence, and the plain distance over the longer string is more defensible.

Ranking. Which of these candidates is closest? This is what a search does, and it wants an ordering rather than a scale. Here the choice of denominator decides the ordering directly, and two denominators can rank two candidates in opposite orders — a short candidate matching badly and a long one matching well are ordered one way per-alignment-column and the other way per-longer-string.

The measured disagreement on this page is between two ways of computing the first quantity. What it says about the second is that a search whose ranking depends on a denominator has a free parameter it never declared, which is the count somebody chose in a different field: there is no ranking of these candidates, there are several, and choosing between them is a statement about the application rather than about the strings.

What is not measured here #

Only unit cost is swept. The disagreement rates on this page are under a model where every substitution costs one and every gap character costs one. Under a graded matrix the ratios move and the rate of disagreement is unmeasured — and there is a reason to expect it to rise, since a graded model has more distinct cost values and therefore more ways for a longer alignment to tie.

The parametric search’s cost is charged in fills, not in transitions. Two rounds means two rectangles, which is twice the cells; the counter reports it and the plate does not plot it. On a computation that is already quadratic, doubling it is a real cost and it is the honest price of the right answer.

The enumeration is over short strings only. Every rate on this page comes from strings of at most four characters, which is where an exhaustive check is possible and where the effect is largest. A sampled measurement at realistic lengths would say how fast the two converge, and this field’s habit — measured, not asserted — makes that a gap rather than a footnote.

And nothing here is about approximate matching under a normalised threshold, which is the use that motivates the whole question. A search for all strings within a normalised distance of 0.2 cannot use the band that a band as wide as the answer provides, because the band is derived from an absolute bound and a normalised bound does not give one until the length is known. That is a real gap between what this rung measures and what the quantity is for.

Where this ladder goes next: the edit that reaches back two rows #

The last two rungs have both changed what is optimised while leaving the set of alignments alone. The next changes the set.

A transposition — swapping two adjacent characters — is one keystroke and costs two edits under every model on this page. Adding it as a fourth operation is a four-line change to the table, it is what nearly every practical implementation ships, and the function it computes is not the one it is named after. The restricted rule that a four-line change produces forbids editing any substring more than once, and that restriction is not a simplification of the definition: it computes a different function, and the different function is not a metric.

Both halves of that are enumerable rather than arguable. Over every pair of strings up to three characters on three letters the two definitions differ on twelve pairs, and the shipped one breaks the triangle inequality on twelve triples out of sixty-four thousand while the unrestricted one breaks it on none. A discrepancy that small is exactly the kind that survives testing forever, and it takes with it the same pruning structures the denominator question threatened here.