THE FOLD / RESPAWN / ROLLBACK / THE EDIT DISTANCE
THE EDIT DISTANCE
Levenshtein — the minimal diff between two strings
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Levenshtein edit distance. How different are two strings? Count the fewest single-character edits — insert, delete, or substitute — that turn one into the other. ‘kitten’ to ‘sitting’ is 3. It is what spell-checkers, diff tools, and DNA aligners run on.
The Wagner–Fischer method fills a grid: cell (i, j) is the distance between the first i characters of one string and the first j of the other, and it is just the minimum of three neighbours — delete (up), insert (left), or match/substitute (diagonal, +1 if the letters differ). The bottom-right corner is the answer, and tracing back the choices gives the actual alignment.
LIT verified live: over 20,000 random pairs the grid DP equals a brute-force recursion exactly, the distance is symmetric, and it obeys the triangle inequality — so it is a genuine metric (window.__lev.dpEqualsBrute && symmetric && triangle). FIG no framing needed; the three-way minimum, the exact distances, and the metric axioms are all real.
The Wagner–Fischer method fills a grid: cell (i, j) is the distance between the first i characters of one string and the first j of the other, and it is just the minimum of three neighbours — delete (up), insert (left), or match/substitute (diagonal, +1 if the letters differ). The bottom-right corner is the answer, and tracing back the choices gives the actual alignment.
LIT verified live: over 20,000 random pairs the grid DP equals a brute-force recursion exactly, the distance is symmetric, and it obeys the triangle inequality — so it is a genuine metric (window.__lev.dpEqualsBrute && symmetric && triangle). FIG no framing needed; the three-way minimum, the exact distances, and the metric axioms are all real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in ROLLBACK, beside THE EXACT TRANSFORM — the respawn domain of getting from one state back to another with the least undoing. Edit distance is the minimal edit script — the shortest diff that rolls string A into string B. AVAN (AI) built the instrument: the DP grid, the traceback, the metric checks.
The weave: David names the seat (the minimal rollback); I make the grid fill and the alignment surface — the edit script in 1D, the DP grid with traceback in 2D, the cost surface with its geodesic in 3D. The sphere is the seam. Credit: Vladimir Levenshtein (1965); Wagner & Fischer (DP, 1974).
The weave: David names the seat (the minimal rollback); I make the grid fill and the alignment surface — the edit script in 1D, the DP grid with traceback in 2D, the cost surface with its geodesic in 3D. The sphere is the seam. Credit: Vladimir Levenshtein (1965); Wagner & Fischer (DP, 1974).
3 ONE DIMENSION
The alignment: the actual sequence of matches, substitutions, insertions and deletions that transforms one word into the other with the fewest edits — the minimal ‘diff’ read out one column at a time.
4 TWO DIMENSIONS · INTERACTIVE
The DP grid for two words. Each cell is the minimum of its up, left, and diagonal neighbours; the bottom-right is the edit distance. The highlighted traceback is the cheapest path — the alignment itself. Cycle the word pairs to watch it change.
5 THREE DIMENSIONS + AVAN’S INVERSE
The DP grid as a turning cost surface — green, the distance climbing from the near corner to the far one.
AVAN’s addition (the inverse-companion): the magenta line is the traceback geodesic — the path of least resistance from corner to corner. The edit distance is a single number, but that number hides a whole surface of partial answers, and the number alone can never tell you how. The alignment is the inverse of the scalar: unfold the one value back into the sequence of moves that realised it. Distance is what; the path down the valley is how. Every answer that compresses to a number has a hidden route that produced it — the green tells you the cost, the magenta tells you the story.
LIT Genuine Levenshtein distance / Wagner-Fischer DP (Levenshtein 1965; Wagner & Fischer 1974). Verified live: over 20,000 random string pairs the grid DP equals a brute-force recursion exactly, the distance is symmetric, and it satisfies the triangle inequality d(a,c) <= d(a,b)+d(b,c) — so it is a genuine metric (window.__lev.dpEqualsBrute && symmetric && triangle, all true). kitten->sitting = 3. The three-way-minimum recurrence and traceback are exact.
FIG No metaphor is doing the work: the DP recurrence, the exact distances, the traceback alignment, and the metric axioms are all real and checked. Calling it a 'diff' or 'rollback' is the only framing.
FIG No metaphor is doing the work: the DP recurrence, the exact distances, the traceback alignment, and the metric axioms are all real and checked. Calling it a 'diff' or 'rollback' is the only framing.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of ROLLBACK · David Lee Wise (ROOT0), with AVAN