Almost-linear approximation of edit distance

The explanation

Turn the word kitten into sitting. Change the k to an s. Change the e to an i. Add a g at the end. That is three edits, and no shorter route exists. The edit distance between two strings is this smallest count. Each insertion, deletion or swap of one symbol costs one.

The classic method fills in a table with one cell for each pair of positions. For kitten and sitting that is 6 times 7, or 42 cells. The work grows with the product of the two lengths. Two strings of a million symbols each need about a trillion cells. Robert Wagner and Michael Fischer described this table method in 1974.

Doing much better exactly looks out of reach. In 2018, Arturs Backurs and Piotr Indyk showed a link to a standard belief about hard problems. A fast exact method of a certain strong kind would break that belief. Their result says nothing against good estimates, though. So researchers turned to approximation, meaning an answer that may be off by a controlled factor.

Estimates improved over two decades. In 2020, Alexandr Andoni and Negev Shekel Nosatzki reached a fixed error factor in time just above linear. Linear time means work proportional to the total length. But their factor could not be pushed close to one. In 2026, Xiao Mao and Aviad Rubinstein got within any factor 1 + ε. Here ε is a small accuracy setting, such as 0.1. Their running time was only a little below the square of the length.

This paper proves that both goals can be met at once. Fix any fraction ε between 0 and 1. With probability at least 2/3, the algorithm returns a whole number between the true distance and 1 + ε times itSource 1. Its expected running time is N to the power 1 + o(1), where N is the total length. That means barely more than linear: the extra factor grows slower than any fixed power of N. Equal strings always give zeroSource 2.

Back to kitten and sitting, with ε set to 0.1. The answer must lie between 3 and 3.3. The only whole number there is 3. So a correct run gives the exact answer here. On long strings, a 10 percent error is the price for skipping most of the trillion cells.

The hard part was cost, not accuracy. The method splits the first string into pieces, then pieces of pieces. It estimates how each piece lines up against stretches of the second string. Checking every possible stretch for every piece would use up the whole time budgetSource 3. The paper predicts where a best alignment should go from rough early estimates. That confines each piece to a narrow band of positionsSource 4. It then bounds how many smaller estimates are ever actually requested.

The result is a statement about very long inputs. For each fixed ε, the guarantee only kicks in past some length that depends on ε. Below it, the algorithm falls back on the exact table methodSource 5. The paper says these thresholds are very largeSource 6. One condition requires the length to exceed roughly 2 raised to 2 raised to 2 to the 999th power. So this is a theorem about growth rates, not a practical tool. The paper also does not claim a good dependence on εSource 7.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers the accuracy guarantee with probability at least 2/3 and the zero answer on equal strings. It also covers the almost-linear bound on expected work, for symbols of polynomially bounded size. A tool called Comparator matches it against a fixed reference statement. No specialists have published a review yet.

What it doesn't show. This does not give a practical program: below enormous input lengths the method falls back on the classic quadratic table.