Words and Tokens

2.9 Minimum edit distance

1. Define minimum edit distance.
   The minimum number of editing operations (insertion, deletion, substitution) needed to transform one string into another.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 60
2. What is an alignment between two strings?
   A correspondence between substrings of two sequences, often shown with an operation row (d, s, i) below the aligned strings.

   D R I V E *
   | | | | | |
   B R I * E F
   s     d   i

   Turning drive into brief: substitute d→b, delete v, insert f (Levenshtein distance 3).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 60
3. What is Levenshtein distance, and what is its alternative version?
   Each insertion, deletion and substitution costs 1 (identity substitution costs 0). In the alternative version substitutions are disallowed, equivalently cost 2 (a deletion plus an insertion).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 60
4. Why can minimum edit distance be computed efficiently with dynamic programming?
   Many edit paths reach the same intermediate string, and the optimal path to the target must include the optimal path to every intermediate string on it. So we store the best solution for each subproblem in a table instead of searching all paths.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 61
5. What is dynamic programming?
   A class of table-driven algorithms (Bellman, 1957) that solve problems by combining solutions to subproblems. In NLP: minimum edit distance, Viterbi, CKY parsing.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 61
6. What is \(D[i,j]\) in the minimum edit distance algorithm, and what are its base cases?
   The edit distance between the first \(i\) characters of the source and the first \(j\) characters of the target. Base cases: \(D[i,0] = i\) deletions, \(D[0,j] = j\) insertions. The answer is \(D[n,m]\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 62
7. Give the recurrence for minimum edit distance.
   \(D[i,j] = \min\{D[i-1,j] + \text{del}(x_i),\; D[i,j-1] + \text{ins}(y_j),\; D[i-1,j-1] + \text{sub}(x_i, y_j)\}\), with \(\text{sub}(x,x) = 0\).

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 62
8. How do you get an alignment, not just a distance, out of the edit distance algorithm?
   Store backpointers in each cell to the neighbor(s) the minimum came from, then backtrace from \(D[n,m]\) to \(D[0,0]\). Each complete path is a minimum-cost alignment: a horizontal step is an insertion, a vertical step a deletion, a diagonal step a match or substitution.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 62
9. What are applications of minimum-edit-distance alignment?
   Computing word error rate in speech recognition, matching sentences in a parallel corpus for MT, and spelling correction.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 63
10. Why might edit operation costs not be uniform in spelling correction?
    Some errors are more likely, e.g. substitutions between letters that are adjacent on the keyboard, so the algorithm allows letter-specific weights.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 64
11. How does the Viterbi algorithm relate to minimum edit distance?
    It is a probabilistic extension: instead of the minimum-cost alignment of two strings it computes the maximum-probability alignment.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2, §2.9, p. 64