1
$\begingroup$

I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming.

The problem is defined as follows:

suppose that you are making a spell-checker with suggestions for misspelled words. You would like to be able to find the words that are closest to the string of non-word letters that a user has input.

These words can differ from the typed string by

  1. missing a letter
  2. having an extra letter
  3. having a letter replaced with another letter

the costs are:

$c_i$, the cost of an insert

$c_d$, the cost of a deletion

$c_r$, the cost of a replacement

with the intention of beginning with a recursive approach that can be converted into a dynamic program, the idea is to build up from substrings.

let T(j,k) denote minimum cost to transform 
substring A[1...j] to substring B[1...k]. 

then there are four ways to convert A[1...j] 
into B[1...k]

1. delete the jth character of A[1...j] and 
convert the first j-1 characters of A into the 
first k characters of B.  This equals cost cd + 
T(j-1, k)

2. convert the first j characters of A into the 
first k-1 characters of B, and insert a kth 
character into B[1...k-1].  This equals cost ci 
+ T(j, k-1)

3. replace the jth character of A with the kth 
character of B and convert the first j-1 
characters of A into the first k-1 characters 
of B.  This equals cost cr + T(j-1,k-1)

4. If characters A[j] = B[k], just convert 
A[1..(j-1)] into B[1..(k-1)]
This has cost T(j-1,k-1)


This can be written as a recursion equation, 
taking the minimum over all four alternatives 
at each step:

T(j,k) = minimum of:
    {    T(j-1, k) + cd
         T(j,k-1) + ci
        T(j-1,k-1) if A[j] = B[k]
      T(j-1, k-1) + cr if A[j] != B[k]
    }

The question is this: suppose we're to add a "swap" function which corrects two letter which are typed in the wrong order. How would we modify the euation for the cost of changing string A into string B if the the cost of a swap is $C_s$?

My thought is:

T(j-1, k+1) if A[j,k] = B[k,j] ?
$\endgroup$
1
$\begingroup$

the additional cost of adding a swap function should be:

T(j-2,k-2) + Cs , if A[j-1]=B[k],and A[j]=B[k-1]

I found the answer by studying the Damerau–Levenshtein distance modification of the classic edit distance problem.

Source: https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.