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.

Alignment

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:

Minimum edit distance algorithm

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.

University of Michigan - Ann Arbor

Edit distance counts the number of operations that performed on a string to change it into another string.

Edit distance

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

Learn Before

Related

Learn After