Edit Distance Visualizer

Ask two people how different “kitten” and “sitting” are and you will get two shrugs. Ask how many single-letter changes it takes to turn one into the other and the question suddenly has an answer: three. Swap the k for an s, the e for an i, and add a g at the end. That count is the edit distance, and it has lasted sixty years because it is honest about what it measures. It does not claim the words mean similar things or sound alike. It counts edits, and nothing else.

A number from coding theory

The idea did not start with spelling. Vladimir Levenshtein published it in 1965 in a Soviet journal, and the English translation followed in 1966, under the title “Binary codes capable of correcting deletions, insertions and reversals”. The setting was the same one Richard Hamming had worked in fifteen years earlier: messages travel through machinery that sometimes damages them, and a code is good when the damaged message can still be recognised. Hamming counted damage as positions that differ, which works only when nothing has been lost or added. Levenshtein asked what happens when a symbol drops out or creeps in, so that everything after it slides along by one place.

His answer was to count three kinds of edit on single symbols: delete one, insert one, or replace one with another. The NIST Dictionary of Algorithms and Data Structures still defines the distance in exactly those terms, as the smallest number of insertions, deletions and substitutions that changes one string into the other.

The difference from Hamming’s count is easy to see. “flaw” and “lawn” differ in every one of their four positions, so their Hamming distance is 4. Their edit distance is 2: delete the f, add an n.

Spelling came in from the other side. In 1964 Fred Damerau checked each unknown word against a dictionary, assuming it held at most one error: a wrong letter, a missing one, an extra one, or two neighbours swapped. In his investigation over 80 percent of misspellings were a single error of those four kinds, and a test run on garbled text identified over 95 percent of them correctly. A decade later Robert Wagner and Michael Fischer named the general version the string-to-string correction problem and solved it in time that grows with the product of the two lengths.

The table that does the counting

The trick that makes the problem tractable is to stop thinking about whole words. Write one word down the side of a grid and the other across the top, with an empty row and column in front of each. The cell in row i and column j holds the distance between the first i letters of one word and the first j letters of the other.

The empty row and column fill themselves in. Turning nothing into the first j letters takes j insertions, so the top row reads 0, 1, 2, 3 and so on; the left column counts deletions the same way. Every other cell looks at three neighbours. From the cell above, delete a letter and add 1. From the cell to the left, insert a letter and add 1. From the cell diagonally above and to the left, either keep the letter for free when the two letters match or substitute it for 1 when they do not. The cell takes the smallest of the three.

Fill the grid row by row and the bottom right corner holds the answer, because each cell only ever needs cells that were filled before it. Here is a worked case that the tool on this page opens with. Turning “intention” into “execution” builds a ten by ten grid. Stop at row 5, column 6, where “inten” meets “execut”. Deleting from the cell above offers 6 + 1 = 7. Inserting from the cell to the left offers 5 + 1 = 6. Substituting the n for a t offers 5 + 1 = 6. The cell becomes 6. Keep going and the far corner reads 5.

The grid hides a real cost. Two strings of a thousand characters need a million cells. Each row depends only on the row above, so the distance alone needs just two rows, but tracing the edits back needs the whole grid. No fundamentally faster exact method is expected either: Arturs Backurs and Piotr Indyk showed that strongly subquadratic edit distance would violate the strong exponential time hypothesis, a widely believed conjecture about satisfiability. For two short words the grid is instant; for long texts it is why surveys such as Gonzalo Navarro’s weigh algorithms by running time as much as by answers.

Many routes, one length

The far corner gives one number, but the route that produced it can be traced back. From each cell, follow any neighbour whose offer equalled the cell’s value. Every such chain from the corner back to the start is an optimal alignment, and each one reads as an edit script.

For “kitten” to “sitting” there is exactly one. For “intention” to “execution” there are seven: 5 edits, 7 paths. One replaces the first five letters in place: i with e, n with x, t with e, e with c, n with u. Another deletes the leading i, substitutes the next two letters, inserts a c and substitutes once more. All seven cost 5. None is more correct than another; the distance does not know which story you had in mind.

Counting them takes a second pass over the same grid. Each cell’s count is the sum of the counts of the neighbours it was chosen from, so the work is the same size as filling the table. The numbers, though, can grow fast. Between forty a’s and forty b’s, with only insertions and deletions allowed, every interleaving of forty deletions with forty insertions is optimal, and there are 107,507,208,733,336,176,461,620 of them. That is far past the 9,007,199,254,740,991 that a JavaScript number holds exactly, which is why the count is kept in BigInt, the language’s whole-number type for integers too large for an ordinary number.

That example is also the cleanest view of a neighbour of edit distance. When substitution is forbidden, the shortest script keeps a longest common subsequence, the longest run of letters that appears in both words in order though not necessarily side by side, and deletes or inserts everything else. So the distance is the two lengths added together minus twice that subsequence. For “intention” and “execution” the common subsequence has 5 letters, and 9 plus 9 minus 10 gives 8 insert and delete operations.

What a swap adds, and what it breaks

Damerau’s fourth kind of error, two neighbouring letters swapped, sounds like a small addition. Typing “teh” for “the” is one slip of the fingers, not two, so it seems fair to charge it as one edit. Adding one more option to each cell is simple: if the last two letters on each side are the same pair reversed, look two rows and two columns back and add 1.

That simple rule is not quite the distance it seems to be. The version that adds one cell lookup is usually called optimal string alignment, and it carries a hidden condition: no substring is edited more than once. Once two letters have been swapped, nothing may be inserted between them.

The standard example is “CA” and “ABC”. With unrestricted swaps the distance is 2: swap CA into AC, then insert B between them. Under the restricted rule that second step is forbidden, because it edits the swapped pair again, and the cheapest script costs 3: 3 versus 2 for the same pair. Now look at the three distances together. CA to AC costs 1. AC to ABC costs 1. Yet CA to ABC costs 3, which is more than 1 plus 1. The triangle inequality, the rule that a detour can never be shorter than the direct route, has failed, so the restricted version is not a true metric.

That matters more than it looks. Metric trees, search structures that prune candidates by distance, rely on the triangle rule to skip whole regions safely, and the restricted measure cannot be used with them. Fed a measure that breaks the rule, such a structure can skip the right answer without any sign that something went wrong.

The unrestricted distance keeps the triangle rule but needs more bookkeeping. Roy Lowrance and Robert Wagner showed in 1975 that it can still be computed in time proportional to the product of the lengths, under conditions on the costs; the usual statement is that a swap must cost at least the average of an insertion and a deletion. Their method remembers, for every letter, the last row in which it appeared, so that a swap can reach back across the letters deleted or inserted between the pair. In short words with one or two errors the two versions rarely disagree. When they do, the difference is real.

Costs open the same question in another way. Charge 2 for a deletion and 1 for an insertion, and turning a word into nothing no longer costs the same as building it from nothing. The distance still finds the cheapest script, but it is no longer symmetric: deleting a two-letter word costs 4 and building it costs 2. A metric must measure the same distance both ways, so this one is not. Keep every cost positive and price insert and delete alike, since each undoes the other, and the metric comes back.

What counts as a character

Every step above assumed that we know what a letter is. Computers offer at least three answers, and the distance depends on which one you pick.

The family emoji of a man, woman, girl and boy is listed by Unicode as one sequence of seven code points: four people joined by three invisible joiners. JavaScript’s string iterator walks it as seven code points. Encoded as UTF-8 with a TextEncoder it is 25 bytes. A browser’s grapheme segmenter, which finds what a reader would call one character, treats it as a single cluster. So the same emoji is 1, 7 or 25 units long, and replacing it with the plain man emoji costs 1 edit in clusters, 6 in code points and 21 in bytes.

Accents raise the same problem more quietly. An e followed by a combining acute accent and the single precomposed letter look identical on screen but are different code point sequences. Count clusters and they differ by one substitution; count code points and the gap is two edits. Normalising both strings to the composed form, NFC, first removes the difference entirely.

None of these answers is wrong. Bytes matter when the question is storage or transmission, code points when it is how a program sees a string, clusters when it is what a person sees. The cluster boundaries themselves come from the Unicode data built into the browser in use.

The measure cannot tell you which question you are asking. It cannot say that “colour” and “color” are the same word, or that “now” and “won” are not. It counts edits, faithfully, in whatever units it is handed.