Case Study · CS · Linguistics
Edit-Distance Visualizer
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.
IPA symbols
| ∅ | f | u | e | g | o | |
|---|---|---|---|---|---|---|
| ∅ | 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
- f f match 0
- o u sub 1
- c e sub 1
- u g sub 1
- m o sub 1
Keyboard mode prices a substitution by how far apart the two keys sit: the distance between cap centres, in key widths, on the chosen layout, with the physical row stagger (on the US board the Q row sits half a key right of the digits, the A row three quarters, the Z row a key and a quarter; the space bar is one point at its centre). The cost is 0.5 + 0.5 · log(d) / log(D), with D the farthest pair on the layout, so neighbouring keys cost 0.5, keys two apart about 0.63, and the farthest pair 1; a symbol the layout lacks costs 1, and case never matters (A and a share a key, as do 1 and !). Insertions and deletions stay at 1. This is the classic typo model behind spelling correction: jello is a nearer miss of hello (0.5, j beside h) than zello is (0.79). Switch the layout and the same slip reprices: on Dvorak, j and h are not neighbours (0.75).
Phonetic mode aligns IPA phones, not letters. English words are transcribed with the CMU Pronouncing Dictionary (125,000 words, General American), keeping diphthongs and affricates as single phones, so shape aligns as /ʃ eɪ p/; the cognate presets are hand-checked, and a word the dictionary does not know is read letter by letter, softening c and g before e, i, y (c reads /s/ or /k/, g reads /dʒ/ or /g/; q as /k/). Spaces split the input into words, each transcribed on its own, so face palm is two lookups, not one miss. Switch entry to IPA to type or click phones directly. Substitutions cost a feature distance: voicing is cheap (weight 0.35), place grows with ordinal separation (up to 0.9; bilabial vs labiodental costs little, bilabial vs velar more), manner grows with separation (up to 0.7), and vowels price nucleus quality plus glide trajectory, so /e/→/eɪ/ is a short onglide, not a leap. Natural changes are priced below their raw distance: debuccalization to /h/ or /ʔ/, homorganic spirantization, the glide/vowel pairing (/w/ with /u/, /j/ with /i/), and the rhotic pairing (/ɹ/ with /ɝ/). So /k/→/g/ lenition costs 0.35 and /b/→/ʃ/ costs over 1. Insertions and deletions stay at 1. Treat these numbers as a heuristic, not ground truth: the phonology they lean on (voicing, lenition toward /h/, spirantization) is real and recurrent, but the exact weights are hand-tuned by eye, not fitted to attested change.
The approach
The recurrence is the whole algorithm. With the distance between the first characters of the source and the first of the target:
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 grid bottom-up, each subproblem solved exactly once: time and 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 time in 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
| 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.
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 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 derived from phonological feature distance, dropped into the same recurrence:
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 , 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 the distance between two keys and the distance between the farthest pair on the layout, a substitution costs
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.txtis a 3.8 MB file checked into the repo; a script that fetches it and a line in.gitignorewould spare every clone the download. - Time it properly. The benchmark averages wall-clock
time.time()over 25 runs.perf_counterand 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 tkintercan 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.