Edit Distance Problem

Source: http://people.csail.mit.edu/bdean/6.046/dp/

Problem: 
Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B.

Given two strings A and B, what is the path from A to B with minimum edit distance?


Comments

  1. I think it will be Levenshtein distance if the distance for insertion is same for all character pairs[replacing A with B has same cost as replacing A with G] else Dynamic Time Warp Distance.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Initial Condition: Edit distance for m = 0 , n= 0 is 0 ie (0,0) = 0
    for each (i,j) where i belongs to m and j belongs to n
    check = min { i.(i - 1 , j- 1) + cost of replacement of ith and jth element(here if a[i] == b[j] then the cost will be zero)
    ii.(i,j-1) + cost of insertion of the jth element
    iii.(i-1,j) + cost of the insertion of the ith element
    }
    This problem if solved recursively will take exponential time however can be done in O(m*n) by using dynamic programming with additional O(m*n) spaces.

    eg: APPLE and CAPE
    Considering the cost of addition, deletion or replacement is each 1.
    A P P L E
    C 1 2 3 4 5
    A 1 2 3 4 5
    P 2 1 2 3 4
    E 3 3 2 3 3

    Space Optimization:
    The problem can be further optimized for space by using only the last array. Thus, only additional space required will be 2* min(m,n).

    ReplyDelete

Post a Comment