The Levenshtein distance between two sequences is the simplest weighting factor in which insertion has a cost of  1, deletion has a cost of 1, and substitution has a cost of 2 (since any substitution can be represented by one insertion and one deletion). For example, the Levenshtein distance between "play" and "stay" is 4.

Levenshtein distance

To better use the edit distance algorithm to generate an alignment, we can visualize the alignment as a path through a table, here referred to as the edit distance matrix. The tabular approach of creating a matrix is very helpful to deal with long strings. To compute the alignment path, first, we apply the minimum edit distance algorithm to each cell and store backpointers. Second, we perform a backtrace that starts from the last cell (at the final row and column) and follows the backpointers back to the first cell through the matrix. There might be multiple paths. Each complete path between the final cell and the first cell is a minimum distance alignment.

Compute the alignment path

The minimum edit distance algorithm is a dynamic programming algorithm commonly used in evaluating the similarity between strings. 

Given two strings, the source string $X$ of length n, and target string $Y$ of length m, we’ll define $D[i, j]$ as the edit distance between $X[1..i]$ and $Y[1.. j]$. 
- Initialization: the zeroth row and column is the distance from the empty string 
    - $D[0,0] = 0$
    - for each row i from 1 to n do: 
                           $D[i,0] \leftarrow D[i-1,0] + $del-cost$(source[i])$
    - for each column j from 1 to m do: 
                           $D[0,j] \leftarrow D[0, j-1] + $ins-cost$(target[j])$
- Recurrence relation:
    - for each row i from 1 to n do:
        - for each column j from 1 to m do:

University of Michigan - Ann Arbor

The minimum edit distance between two strings is defined as the minimum number of operations (also called edits) needed to transform one string into another. Operations includes insertion, deletion, substitution, and switch.

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) 

Given two sequences, an alignment is "a correspondence between substrings of the two sequences". With a small change, minimum edit distance and alignment can provide the minimum cost alignment between two strings. For example, in speech recognition, minimum edit distance alignment can be used to compute the word error rate. In machine translation, alignment can help match sentences in a parallel corpus in two languages.

Learn Before

Related

Learn After