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.

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

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