Edit Distance

Edit distance (also known as Levenshtein distance) is a measure of the similarity between two strings, defined as the minimum number of single-character insertions, deletions, and substitutions required to transform one string into the other. It is the foundational metric of sequence alignment, the engine behind diff algorithms in version control, and a key component of spell-checking, DNA analysis, and speech recognition systems.

The dynamic programming formulation computes edit distance in O(nm) time for strings of length n and m, filling a matrix where each cell represents the minimum cost to align the prefixes ending at that position. This matrix structure is identical to that used in the Needleman-Wunsch algorithm and Floyd-Warshall, revealing that edit distance is not a string problem but a shortest-path problem in disguise: each alignment operation is an edge in a grid graph, and the optimal alignment is the shortest path from the top-left to the bottom-right corner.

Edit distance generalizes beyond strings to any sequences where a cost function can be defined over insertions, deletions, and substitutions. The Damerau-Levenshtein distance adds transposition as an operation; the Hamming distance restricts operations to substitutions only. Each variant reflects a different model of what constitutes "similarity" and what operations are plausible in the domain.

The edit distance between two strings is not merely a number. It is a map of the minimal transformations required to make one thing into another — and in that map, we can read the history of divergence, the cost of reconciliation, and the structure of difference itself.