Problem

Calculate the minimum edit distance of the two sequences, \( x_{1\ldots m} = x_1 \ldots x_m\) and \( y_{1\ldots n} = y_1 \ldots y_n\)

Definition

\( D_{i,j} \) is the minimum edit distance of the (sub)sequences \( x_{1…i} = x_1 \ldots x_i \) and \(y_{1\ldots j} = y_1 \ldots y_j \)

Initialization

\[
D_{0,0} = 0 \\
D_{i,0} = i \mbox{ for } i=1, \ldots m \\
D_{0,j} = j \mbox{ for } j=1, \ldots n \\
\]

Iteration

\[
\mbox{ for } i=1, \ldots m\\
\mbox{ for } j=1, \ldots n\\
D_{i,j}= \min
\left[ \begin{array}{l}
D_{i-1,j-1} + \delta(a_i,b_j), \\
D_{i-1,j} +1, \\
D_{i,j-1} +1
\end{array} \right.
\]
where
\[
\delta(a_i,b_j) = [ a_i == b_j ? 0:1 ]
\]