1

We are given $2$ strings $A=[1 \dots m]$ and $B[1 \dots n]$ and the following $3$ operations are allowed:

  • Insert a charachter,with cost $c_i$
  • Delete a character,with cost $c_d$
  • Replace a character,with cost $c_r$

We are looking for the optimal sequence of operations(sequence of operations with the minimum cost),for the conversion of the string $A$ to the string $B$.

$$T(i,j)=\text{ the minimum cost of the conversion of the string }\\ A[1 \dots i] \text{ to } B[1 \dots j], 1 \leq i \leq m, 1 \leq j \leq n$$

According to my notes: $$T(i,j)=\min \left\{\begin{matrix} T(i-1,j)+c_d & \text{ // delete the i-th charachter of A}\\ T(i,j-1)+c_i & \text{ // insert the j-th charachter of B} \\ T(i-1,j-1) & \text{if } A[i]=B[j]\\ T(i-1,j-1)+c_r & \text{if } A[i] \neq B[j] \end{matrix}\right.$$

Why is the cost given by the above formula?Could you explain it to me?

EDIT:

For example,suppose that we want to convert the string $ \text{ exponential}$ to the string $\text{ polynomial }$ ,knowing the costs:

$$ c_d=c_i=2 , c_r=1$$

I created the following matrix: enter image description here

Is it right? If so,is the minimum cost of the conversion then $ T[11,10]=11$ ? Or am I wrong?

evinda
  • 7,823
  • This doesn't seem right. The first row and the first column (indexed $0$) are incorrect. For example, the cost for converting an empty string into "p" (which corresponds to the entry at $(0, 1)$), is not $0$. – Tunococ Aug 20 '14 at 01:22

1 Answers1

2

I'm not sure if this is what you're looking for. I'll just walk you through each of the cases. Here are possible ways to obtain a conversion from $A[1..i]$ to $B[1..j]$.

  1. If you already know how to convert $A[1..(i-1)]$ to $B[1..j]$, you can convert $A[1..i]$ to $B[1..j]$ by doing what you did with $A[1..(i-1)]$, and deleting $A[i]$.
  2. If you already know how to convert $A[1..i]$ to $B[1..(j-1)]$, you can convert $A[1..i]$ to $B[1..j]$ by doing what you did with $A[1..i]$, and adding $B[j]$.
  3. If you already know how to convert $A[1..(i-1)]$ to $B[1..(j-1)]$, you can do what you did to $A[1..(i-1)]$, and replace $A[i]$ by $B[j]$. However, if $A[i]$ and $B[j]$ are already equal, there's no need to replace it.

One important property of this problem is that these exhaust all the possibilities. (It's quite tedious to prove this formally and I don't think people do that.) So in order to obtain $T(i, j)$, the minimum cost for converting $A[1..i]$ to $B[1..j]$, you only need to compare the costs of the three ways of obtaining the conversion, assuming that you already know minimum costs of converting smaller problems.

Tunococ
  • 10,303
  • 1
    I haven't understood why we take the minimum of these $3$ cases.. Doesn't the cost depend on $A$ and $B$ and on the case at which we are? – evinda Aug 18 '14 at 16:56
  • 1
    The algorithm assumes a left-to-right approach. In the first step 1 of the 4 operations is selected for the first character. After that we continue character by character until the string is complete. In the end we will pick the method that turned out to be cheapest by recursively working backward from the end result. – Klaas van Aarsen Aug 18 '14 at 19:13
  • 1
    @IlikeSerena Could you explain it further ro me? – evinda Aug 18 '14 at 22:24
  • 1
    @evinda The cost does depend on $A$ and $B$. That is considered in the third case I listed, which includes the last two cases in your definition of $T(i, j)$. – Tunococ Aug 19 '14 at 00:38
  • 1
    I edited my post..could you tell me if that what I did is right? – evinda Aug 19 '14 at 22:10
  • I think it can be done cheaper. We want to go from 11 letters to 10 letters and the last 3 are identical. So 7 replacements plus 1 deletion is an upper bound (cost=9). :/ – Klaas van Aarsen Aug 21 '14 at 18:20