Gregory Friedman The Greg Wide Web on the name →

Case Study · CS · Linguistics

Edit-Distance Visualizer

2026 · repository

The idea

Levenshtein distance is usually taught as a formula: the minimum number of insertions, deletions, and substitutions needed to turn one string into another. I first met it properly in a group project for CSE 3500 (Algorithms and Complexity), LevDistanceAlg, where the assignment was to implement the algorithm several ways and measure how the implementations diverge as inputs grow. The docstring at the top of our Lev.py states the plan plainly: “implement Levenshtein’s distance algorithm, then make a GUI.” We built the first half four ways and measured it carefully. The second half is this page.

The algorithm deserves better than a formula, and better than a desktop window that opens beside the code. Edit distance is best understood as a table you can watch fill in: every cell is a subproblem (the distance between two prefixes), every value is a choice among three neighbors, and the finished table contains not just the answer but the entire argument for it; trace the optimal path backward and you can read off exactly which edits to make.

The reason I keep coming back to it is linguistic. “How far apart are these two words?” is the first question of comparative linguistics, and edit distance is its bluntest answer. That’s why the default pair below is not kitten/sitting but Latin focum and Spanish fuego; an ancestor and its descendant, four sound changes apart.

The same table turns up wherever similarity has to be made numerical. git diff fills it, so does the spell checker on your phone, and speech recognition reports its accuracy as word error rate, which is this distance computed over a transcript and divided by the transcript’s length. The recurrence is identical in all of them; what differs is the price of a substitution, and that price is where the domain knowledge lives. Molecular biology follows that thread furthest, scoring an amino-acid substitution by how often it has actually happened in proteins known to be related. This page follows it into phonology and into the geometry of a keyboard.

The plate below is the table itself, filling in cell by cell; play with it first, then read how the recurrence and the two weightings work.

Costs
Levenshtein dynamic-programming table. Rows are prefixes of the source word, columns are prefixes of the target word; each cell holds the edit distance between those prefixes.
∅ fuego
∅ 0 1 2 3 4 5
f 1 0 1 2 3 4
o 2 1 1 2 3 3
c 3 2 2 2 3 4
u 4 3 2 3 3 4
m 5 4 3 3 4 4

Distance 4; optimal path highlighted.

Operations along the path

  1. f f match 0
  2. o u sub 1
  3. c e sub 1
  4. u g sub 1
  5. m o sub 1
Plate I The Levenshtein table for focum → fuego: distance 4, by one match and four substitutions along the diagonal. Type your own pair, then step or run the fill. Switch to keyboard costs and each substitution prices by how far apart the two keys sit on a QWERTY, Dvorak or AZERTY board, the typo model behind spelling correction; switch to phonetic costs and the substitutions reprice by feature distance, so a plausible sound change costs less than a wild one. The strip under the table prices every step, so the whole distance is itemised.

The approach

The recurrence is the whole algorithm. With Di,jD_{i,j} the distance between the first ii characters of the source and the first jj of the target:

Di,0=i,D0,j=j,D_{i,0} = i, \qquad D_{0,j} = j, Di,j={Di−1, j−1if ai=bj,1+min⁡(Di−1, j−1⏟substitute,  Di−1, j⏟delete,  Di, j−1⏟insert)otherwise.D_{i,j} = \begin{cases} D_{i-1,\,j-1} & \text{if } a_i = b_j,\\[4pt] 1 + \min\bigl(\underbrace{D_{i-1,\,j-1}}_{\text{substitute}},\; \underbrace{D_{i-1,\,j}}_{\text{delete}},\; \underbrace{D_{i,\,j-1}}_{\text{insert}}\bigr) & \text{otherwise.} \end{cases}

The repo works through four implementations of exactly this recurrence, in escalating discipline. Set side by side, the distance between “correct” and “usable” is the whole lesson:

  • Naive slicing recursion. Recomputes the same overlapping subproblems again and again, and rebuilds a fresh substring on every call. Exponential time with a copy on top of it: correct, and hopeless past a dozen characters.
  • Index-passing recursion. The identical recomputation, but it hands down indices instead of slicing, so it is honest about why it is slow. Still exponential time, now with the copying overhead stripped away so the real cost stands exposed.
  • Full DP table. Fills the (m+1)×(n+1)(m{+}1)\times(n{+}1) grid bottom-up, each subproblem solved exactly once: O(mn)O(mn) time and O(mn)O(mn) space. This is the version the plate above animates.
  • Two-row DP. Keeps only the current and previous rows, since the recurrence never reaches further back than one row. The same O(mn)O(mn) time in O(min⁡(m,n))O(\min(m,n)) space.

To measure the divergence we sampled random word pairs from a 370,105-word dictionary at lengths 3 through 19, twenty pairs per length, each timed as an average of 25 runs, and plotted the curves. The two exponential versions fall off a cliff exactly where the theory says they must; the two table versions sit indistinguishably flat beneath them, and the two-row variant buys its memory saving with nothing given back in time.

You do not have to take the curves on faith; the plate below runs all four in your own browser. Give it a pair of short strings and it computes the distance with each implementation, counts what each actually did (recursive calls for the top two, cell fills for the bottom two), and confirms they all land on the same number. Then it sweeps the string length and plots the counts, so the exponential and the polynomial pull apart in front of you.

The recurrence, four ways · counted on paper

The four implementations of the edit-distance recurrence with their time and space complexity: naive slicing recursion and index-passing recursion are both exponential in time; the full DP table is order m times n in both time and space; the two-row DP is the same time in space proportional to the shorter string.
implementation time space
naive slicing recursion correct, hopeless past a dozen characters exponential O(m+n) stack, plus a fresh substring on every call
index-passing recursion the same calls, the copying overhead stripped away exponential O(m+n) stack, no copies
full DP table each subproblem solved exactly once O(mn) O(mn), the whole grid held at once
two-row DP same time, the memory saving with nothing given back O(mn) O(min(m,n)), two rows kept

With JavaScript enabled this plate runs all four on a pair of strings and counts what each actually does: recursive calls for the top two, cell fills for the bottom two, and it checks that all four agree on the distance. Then it sweeps the string length and plots the counts, so the gap between exponential and polynomial appears as the distance between two curves.

Plate II The four implementations, made runnable. On Run each computes the distance for the pair you type, and the plate counts the work: recursive calls for the two exponential versions, cell fills for the two table versions, with the twins in each pair separated by a second axis (throwaway copies, then memory held). The scaling chart sweeps mismatched worst-case strings; the recursive call count is capped at length 7, where it has already climbed off the top of a chart the DP curve barely troubles.

The visualizer is the piece the repo lacked. It’s an Astro island in vanilla TypeScript, no framework and no chart library, about five kilobytes of script gzipped (the pronunciation dictionary that phonetic mode uses is fetched separately, and only on demand), that renders the DP table as an HTML table styled entirely with the site’s design tokens. The default table is computed at build time and served fully filled, so the figure above is complete even with JavaScript disabled; the script only makes it replayable. Step fills one cell, Run animates the whole fill (instantly, if you prefer reduced motion), and when the table completes, the optimal traceback path lights up: green for matches, ochre for edits, with arrows showing whether each move was a substitution (↖), insertion (←), or deletion (↑). Below the table an alignment strip spells the same path out column by column, source symbol over target symbol, each labelled with its operation and what it cost, so the strip sums to the distance and you can read off exactly which edit turned one word into the other at every position. Inputs are capped at 12 characters, partly because the table is O(mn)O(mn) cells, mostly because past that size the animation stops being legible, and legibility is the only reason the plate exists.

The phonetic turn

Unit costs treat all substitutions as equal, and phonology emphatically does not. Substituting /b/ for /p/ changes one feature; voicing; substituting /b/ for /ʃ/ changes voicing, place, and manner at once. The natural extension is a weighted cost function c(x,y)c(x, y) derived from phonological feature distance, dropped into the same recurrence:

Di,j=min⁡(Di−1, j−1+c(ai,bj),  Di−1, j+cdel,  Di, j−1+cins).D_{i,j} = \min\bigl(D_{i-1,\,j-1} + c(a_i, b_j),\; D_{i-1,\,j} + c_{\text{del}},\; D_{i,\,j-1} + c_{\text{ins}}\bigr).

Nothing else about the algorithm changes, but the distance starts to mean something different: cheap paths are now paths made of plausible sound changes. Phonetic mode first transcribes each word into IPA phones (so focum aligns as /f o k u m/ against fuego /f w e g o/, not letter for letter), then prices each substitution by feature distance. Voicing is cheap, place grows with articulatory distance (bilabial to labiodental costs little; bilabial to velar more), and a few recurrent changes are discounted below their raw feature cost: debuccalization to /h/, homorganic spirantization, and the glide/vowel pairing that makes a diphthong’s onglide cheap. The lenition that turned Latin intervocalic /k/ into Spanish /g/ (the /k/ → /g/ substitution you can read off the plate’s alignment strip) is one of the most common changes in the world’s languages, and this weighting prices it at just 0.35. The whole focum → fuego alignment now costs 3.6 rather than the flat 4: one match, the cheap /k/→/g/ lenition and /u/→/o/ merger, the diphthong’s onglide, and the deleted final /m/. That turns edit distance into a coarse cognate-similarity measure, and a legible one; the thread I pick up in a draft essay on the regularity of sound change, which embeds this same plate.

The scope of these weights is worth stating plainly: they are a heuristic, not a measurement. The linguistics underneath them is real and old. Sound change is directional and gradient, not a fair coin over the alphabet, and a handful of paths recur across unrelated families far more often than chance would allow. The lenition chain s > h > nothing is the textbook case; Latin and Greek both weakened intervocalic /s/ toward /h/ and then to silence, and the same drift turns up again from Proto-Indo-European into Iranian. Debuccalization, spirantization between vowels, and voicing in the same position are common in exactly this way, which is why I priced them cheap. But the specific numbers (0.35 for a voicing flip, at most 0.9 for the full span of place) are mine, tuned by eye until the cognate presets aligned the way a philologist would read them by hand. They encode the shape of the phenomenon, not its ground truth; a diachronic model meant for research would fit them to a corpus of attested changes, which is on the list at the end of this page.

The transcription itself deserves a word, because English spelling is where letter-based methods go to die. Phonetic mode transcribes English words with the CMU Pronouncing Dictionary (125,000 words, General American, converted to broad IPA by a build script and fetched only when you switch the costs over), keeping diphthongs and affricates as single phones: shape aligns as /ʃ eɪ p/, three segments, not five letters. The plate shows each word’s transcription and says when it had to fall back to reading letters (a fallback that at least knows c and g soften before e, i, and y); spaces split the input into words looked up separately, so a short phrase works as well as a word; and an IPA entry mode with a symbol palette lets you type the phones yourself, for languages the dictionary has never heard of. The dictionary weighs 2.9 MB. It is generated by a checked-in script, carries its license, and is fetched only when a reader switches the costs to phonetic, so the page itself loads none of it.

Keyboard distance

The recurrence takes any c(x,y)c(x, y), and the other weighting on the plate has nothing to do with phonology. Keyboard mode prices a substitution by the physical distance between the two keys. Each key is a point at the centre of its cap, measured in key widths on the real layout with its real row stagger: on a US board the Q row sits half a key to the right of the digit row, the A row three quarters, the Z row a key and a quarter, and the space bar is one point at its centre. With dd the distance between two keys and DD the distance between the farthest pair on the layout, a substitution costs

c(x,y)=12+12 ln⁡dln⁡D,c(x, y) = \tfrac{1}{2} + \tfrac{1}{2}\,\frac{\ln d}{\ln D},

so neighbouring keys cost exactly 0.5, keys two apart about 0.63, and the two farthest keys 1. A symbol the layout does not have costs 1, case is ignored (A and a are one key, as are 1 and !), and insertions and deletions stay at 1, so every substitution is at most as dear as under unit costs. The logarithm is the point: the first key of separation should matter more than the tenth, because a typo is usually a near miss. This is the classic typo model behind spelling correction, the simplest substitution table a noisy-channel corrector can use: a candidate one adjacent key away is a likelier reading of what was typed than one from across the board, so jello is a nearer miss of hello (0.5, j beside h) than zello is (0.79). The layout selector swaps the geometry under the same words. The j-for-h slip costs 0.75 on Dvorak, where the two keys are not neighbours, and n for m, a neighbour’s slip on QWERTY at 0.5, costs 0.75 on AZERTY, which puts m on the home row beside l.

What I would build next

  • Fetch the word list instead of committing it. Words.txt is a 3.8 MB file checked into the repo; a script that fetches it and a line in .gitignore would spare every clone the download.
  • Time it properly. The benchmark averages wall-clock time.time() over 25 runs. perf_counter and more repetitions would clean up the noise at short word lengths, where per-call overhead dominates the thing being measured.
  • Close the docstring’s promise in the repo itself. The GUI it announced exists now, on this page rather than in a tkinter window, and the unused import tkinter can go with it. What the repo could still use is a plain-text rendering of the same table beside the four implementations, so that the code and the figure that explains it travel together.
  • Fit the phonetic weights to attested change. Unit-cost edit distance is a weak cognate signal, and the phonetic weighting is a hand-tuned heuristic. What historical linguists actually need is the alignment, not the number, and serious computational work uses sound-class alignment models far beyond this. The plate points at that literature; the next step is to fit its weights to a corpus of attested changes rather than by eye.
  • Learn the keyboard costs from data. Keyboard mode is geometry, not error statistics. The noisy-channel spelling correctors this mode simplifies learn a confusion matrix from real misspellings, which prices p-for-o by how often that slip is actually made rather than by how far the fingers travelled. They also carry the transposition Damerau added to Levenshtein’s three operations: swapping two adjacent letters is among the commonest typos, and this recurrence charges it as two edits.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.