ConceptDBISAI-written · not yet proofread

Edit Distance

Also Levenshtein Distance · ED

The edit distance ED(x, y) (Levenshtein distance) is the minimal number of single-character insert, delete and replace operations that transform the string x into the string y.

Formula#

Recurrence (for $n, m > 0$ ):

\mathrm{ED}(x, y) = \min \begin{cases} \mathrm{ED}(x[1..n],\ y[1..m-1]) + 1 & \text{(1) insert } y[m] \\ \mathrm{ED}(x[1..n-1],\ y[1..m]) + 1 & \text{(2) delete } x[n] \\ \mathrm{ED}(x[1..n-1],\ y[1..m-1]) + 1 & \text{(3a) replace, if } x[n] \ne y[m] \\ \mathrm{ED}(x[1..n-1],\ y[1..m-1]) & \text{(3b) keep, if } x[n] = y[m] \end{cases}

with $\mathrm{ED}(\varepsilon, y) = |y|$ and $\mathrm{ED}(x, \varepsilon) = |x|$ .

Dynamic programming. Fill an $(n+1) \times (m+1)$ table $M$ with $M[i][j] = \mathrm{ED}(x[1..i], y[1..j])$ (row/column 0 = $\varepsilon$ ):

$M[i][0] = i$ , $M[0][j] = j$ ,
$M[i][j] = \min\bigl(M[i-1][j-1] + s,\ M[i-1][j] + 1,\ M[i][j-1] + 1\bigr)$ with $s = 0$ if $x[i] = y[j]$ , else $s = 1$ ,
result $\mathrm{ED}(x, y) = M[n][m]$ (bottom-right entry).

Each entry depends only on its left, upper and upper-left neighbour. Time and space $\Theta(n \cdot m)$ ; space $O(\min\{n, m\})$ suffices, since only the previous row is needed.

Properties#

ProofProof sketches (recommended as exam preparation)

Every operation can be undone by one operation (insert ↔ delete, replace ↔ replace); reversing an optimal sequence $x \to y$ gives one $y \to x$ of the same length.
$|x|$ deletions suffice; each operation shortens by at most 1, so at least $|x|$ are needed.
Each operation changes the length by at most 1, and the length must change from $|x|$ to $|y|$ .
Transform $x[1..n-1]$ into $y[1..m-1]$ optimally, then replace $x[n]$ by $y[m]$ (or do nothing if they are equal).

A single operation sequence only proves an upper bound on ED; the exact value needs the DP table or a lower-bound argument (e.g. property 3, or the Q-Gram Lemma read backwards).
ED is the relevance model for fuzzy search on whole words; for search-as-you-type it is replaced by the Prefix Edit Distance.

Example#

DOOF → BOOF (replace(1,B)) → BLOF (replace(2,L)) → BLOE (replace(4,E)) → BLOED (insert(5,D)) proves $\mathrm{ED}(\text{DOOF}, \text{BLOED}) \le 4$ . The table for $\mathrm{ED}(\text{BLOED}, \text{DOOF})$ shows equality:

	$\varepsilon$	D	O	O	F
$\varepsilon$	0	1	2	3	4
B	1	1	2	3	4
L	2	2	2	3	4
O	3	3	2	2	3
E	4	4	3	3	3
D	5	4	4	4	4

Every entry is the ED of two prefixes, e.g. $\mathrm{ED}(\text{BLO}, \text{DOO}) = 2$ ; the result is $\mathrm{ED}(\text{BLOED}, \text{DOOF}) = 4$ .

Exam WS 22/23, Task 2.1: $\mathrm{ED}(\text{alfa}, \text{alpha}) = 2$ via alfa → alpa (replace f by p) → alpha (insert h); at least 2 are needed, since by property 3 one operation would have to be an insert, but deleting any one character of alpha (lpha, apha, alha, alpa, alph) never gives alfa.

Sources#

Slides 08, p. 8 (definition), p. 9 (properties), p. 10 (recurrence), p. 11 (DP table)
DBIS_VL08 > Edit Distance, DBIS_VL08 > Recursive formula, DBIS_VL08 > Dynamic programming algorithm
DBIS_VL13 > Example Task: Q-Grams and Edit Distance (WS 22/23, Task 2.2, 5 points)
Exams: DBIS Exam WS1718 (not published) (Task 3), DBIS Exam WS2223 (not published) (Tasks 2.1–2.3)

Connections

Mentioned in inline links7

Fuzzy Search
fuzzy search returns all $y \in D$ with $\mathrm{ED}(x, y) \le \delta$ (Edit Distance), §
Prefix Edit Distance
where $\mathrm{ED}$ is the Edit Distance and the prefixes $y'$ range over $\varepsilon, y[1..1], \dots, y[1..|y|] = y$ . §
Q-Gram Lemma
For strings $x, y$ and $q \in \mathbb{N}$ , with $Q_q(\cdot)$ the multiset of q-grams and $\mathrm{ED}$ the Edit Distance: §
Q-Gram
Q-grams are a cheap proxy for string similarity: strings with a small Edit Distance agree “at many places” and therefore share many q-grams. The Q-Gram Lemma makes this precise (each edit operation affects at most $q$ q-grams). §
| $q-1$ $ on both sides |
$freiburg$
| ED search | for padded $x', y'$ : $\mathrm{ED}(x, y) = \mathrm{ED}(x', y')$ |
§
VL08 – Fuzzy Search, Prefix Edit Distance, Q-Gram Index
For two strings $x$ and $y$ , $\mathrm{ED}(x, y)$ is the minimal number of transformations to get from $x$ to $y$ , where each transformation is one of (Slide 8, Edit Distance): §
Edit Distance — relevance model for fuzzy search; definition, properties, recurrence, $\Theta(|x| \cdot |y|)$ DP §
VL13 – Evaluation, Exam, Work in our Group
Calculate the minimal possible edit distance between two strings of length 5 that have three 3-grams in common when using padding on both sides, with explanation. §
Edit Distance — the quantity bounded from below in WS 22/23 Task 2.2 §
Fuzzy Search and Q-Grams
Edit Distance — relevance model for whole words, $\Theta(|x||y|)$ DP §
Relevance: ED for fuzzy search, PED for fuzzy prefix search; PED is computed from the same table as ED. §

Search in these mentions →