- 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$.

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.

Viterbi

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. 

University of Michigan - Ann Arbor

In NLP, we need to find out how similar the two strings are to each other. Minimum edit distance finds out the dissimilarity of two strings and counts the minimum number of modifications to transform a string to another. Levenshtein distance is the method that is used to measure the minimum edit distance.

Minimum Edit Distance

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

Speech and Language Processing (3rd ed. draft) 

Levenshtein distance is a string metric, the simplest weighting factor, that measures the differences between two strings and counts the number of changes needed to make. It is the simplest weighting factor because each of the three operations (insertion, deletion, substitution) has a cost of 1.

Learn Before

Related

Learn After