Math

Edit distance and diff

Build edit-distance tables from your own strings and trace an optimal alignment with adjustable substitution cost.

Actual application image

Try this

Edit two strings of up to ten characters. The Levenshtein table fills row by row, then traces an optimal alignment. Insertions and deletions cost 1; substitution costs 1 or 2. Distance −1 means the table is unfinished.

Equations used in the module

Equations
D(i,0)=i; D(0,j)=j
D(i,j)=min(D(i−1,j)+1, D(i,j−1)+1, D(i−1,j−1)+c)
c=0 for equal symbols; otherwise substitution cost
Traceback yields an optimal insertion/deletion/substitution alignment

Related experiments

Back to catalogue

Math

String search: KMP, Boyer–Moore, Rabin–Karp

Compare naive, KMP, full Boyer–Moore and rolling-hash substring search, with recorded comparisons, prefix tables and overlapping matches.

Math

Mazes: generate and solve

Generate mazes with depth-first carving, Prim and Wilson, then compare breadth-first, A* and wall-following routes.

Math

Quadtree: space that indexes itself

Inspect adaptive quadtree partitions, nearest-neighbour pruning and collision candidates in static or moving point clouds.