Edit distance

Remarks

Example: $d(abc, acd) = 2$. Deleting $b$ and then inserting $d$ at the end turns $abc$ into $acd$, so $d \le 2$. A single operation either changes the length or changes exactly one position, while $abc$ and $acd$ have equal length and differ in two positions, so $d \ge 2$.

Non-example: if only substitutions are allowed, the strings $ab$ and $b$ are at no finite distance, since substitution never changes the length. That restricted distance is the Hamming distance, defined only for strings of equal length.

Since each operation can be undone by one operation, $d$ is symmetric, and $d$ is a metric on $\Sigma^*$. For $x = x_1 \cdots x_m$ and $y = y_1 \cdots y_n$, let $D(i, j)$ be the edit distance of the prefixes $x_1 \cdots x_i$ and $y_1 \cdots y_j$. Then $D(i, 0) = i$, $D(0, j) = j$, and $$D(i, j) = \min\bigl(D(i - 1, j) + 1,\ D(i, j - 1) + 1,\ D(i - 1, j - 1) + [x_i \ne y_j]\bigr),$$ where $[x_i \ne y_j]$ is $1$ if $x_i \ne y_j$ and $0$ otherwise. This gives $d(x, y) = D(m, n)$ in time $O(mn)$. Other edit distances use other sets of operations, for example adding the transposition of two adjacent symbols.