To compute the minimum edit distance of two strings, we will need to compute bottom-up, combining solutions to subproblems.

First, we need to consider the basic cases :
$$D[0, 1] = 1$$, which means to convert a null string to a string with one character. The edit distance is one insertion.

$$D[1, 0] = 1$$, which means to convert a string with one character to a null string. The edit distance is one deletion.

$$D[1,1] = 0 \quad or \quad 2 $$, which means to convert a string with one character to another string with one character. The edit distance is zero if two characters are the same, while the edit distance is two if two characters are different.

Then we compute larger cases based on previous values.

$$
D[i, j] = min \begin{cases}\ D[i - 1, j] +1 
\\D[i, j  - 1] +1
\\D[i- 1, j  - 1] +\begin{cases} 2;\quad if source[i]  \neq  target[j]\\0; \quad if source[i] = target[ j]\end{cases} 

\end{cases} 
$$

Explanation for Minimum Edit Distance Algorithm

- The minimum edit distance can be computed by using dynamic programming in which the shortest path is stored every time we found it. 
- First, we define the minimum edit distance between two strings $X$ and $Y$ with lengths of n and m respectively. $D[i, j]$ would be defined as the edit distance between $X[1..i]$ and $Y[1..j]$. Then we get that $D[n, m]$ is the edit distance between $X$ and $Y$.

University of Michigan - Ann Arbor

Dynamic programming is an algorithm technique that recursively solves subproblems of a problem and finds the optimal solution from the optimal solution of the subproblems. Some of the algorithms in NLP uses dynamic programming, such as the Viterbi algorithm, CKY algorithm for parsing, and the Minimum Edit Distance Algorithm. 

Dynamic Programming

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

The Minimum Edit Distance Algorithm

2 steps to compute the alignment path:
- The backpointers are stored in each cell by augmenting the minimum edit distance algorithm.
- A backtrace is performed from the last cell to where the pointers are pointing to through the dynamic programming matrix.

Minimum Cost Alignment

The Viterbi algorithm is a probabilistic extension of minimum edit distance. It computes the maximum probability alignment of two strings instead of minimum edit distance.

Learn Before

Related

Learn After