Solving the Edit Distance Problem with Dynamic Programming

Solving the Edit Distance Problem with Dynamic Programming

Problem Description
Edit Distance (Levenshtein distance) is a metric for measuring the similarity between two strings. It is defined as the minimum number of single-character edit operations required to transform string A into string B. Allowed operations include: inserting a character, deleting a character, and replacing a character. For example, the edit distance between "kitten" and "sitting" is 3 (replace k→s, replace e→i, insert g at the end).

Dynamic Programming Approach Analysis

  1. Problem Decomposition: Break down the transformation of long strings into subproblems. If A[0..i] and B[0..j] represent the first i characters of A and the first j characters of B respectively, then the edit distance dp[i][j] can be derived from shorter substrings.
  2. State Definition: Let dp[i][j] represent the minimum number of operations required to convert the first i characters of A into the first j characters of B.
  3. Boundary Cases:
    • If A is empty (i=0), j characters need to be inserted, so dp[0][j] = j.
    • If B is empty (j=0), i characters need to be deleted, so dp[i][0] = i.
  4. State Transition Equation:
    • If A[i-1] == B[j-1] (the last characters are the same): No operation is needed, dp[i][j] = dp[i-1][j-1].
    • Otherwise, take the minimum of the three operations plus 1:
      • Replace: Replace A[i-1] with B[j-1], cost = dp[i-1][j-1] + 1.
      • Delete: Delete A[i-1], cost = dp[i-1][j] + 1.
      • Insert: Insert B[j-1] at the end of A, equivalent to deleting a character from B, cost = dp[i][j-1] + 1.
        Formula:

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } A[i-1] = B[j-1] \\ \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 & \text{otherwise} \end{cases} \]

Example Derivation (A="kitten", B="sitting")

  1. Initialize the dp table (row and column lengths are len(A)+1 and len(B)+1 respectively):

    • First row: dp[0][j] = j (0,1,2,...,7)
    • First column: dp[i][0] = i (0,1,2,...,6)

  2. Calculate row by row (i=1..6, j=1..7):

    • i=1, j=1: A[0]='k', B[0]='s', different. Compare:
      • Replace: dp[0][0]+1 = 0+1 = 1
      • Delete: dp[0][1]+1 = 1+1 = 2
      • Insert: dp[1][0]+1 = 1+1 = 2
        Take the minimum 1, so dp[1][1] = 1.
    • Key subsequent steps:
      • When i=6, j=7: A[5]='n', B[6]='g', different. Compare:
        • Replace: dp[5][6]+1 = 2+1 = 3 (cost for "kitte"→"sittin" is 2, then replace 'n' with 'g')
        • Delete: dp[5][7]+1 = 3+1 = 4
        • Insert: dp[6][6]+1 = 3+1 = 4
          Final result: dp[6][7] = 3.

  3. Result: dp[6][7] = 3 is the edit distance.

Optimizations and Extensions

  1. Space Optimization: In practice, only two arrays (rows) are needed for rolling storage, reducing space complexity from O(mn) to O(min(m,n)).
  2. Operation Recording: An auxiliary array can be used to record the operation types, allowing backtracking to output the specific sequence of edit steps.
  3. Application Scenarios: Spell checking, DNA sequence alignment, similarity calculation in natural language processing.

This method optimizes the exponential brute-force search to an O(mn) time complexity efficient algorithm using dynamic programming, exemplifying the core idea of trading space for time in dynamic programming.