Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are:

1) Delete a letter

2) Add a letter

For example, the minimal editing distance from $X=Sport$ to $Y=Sort$ is $1$. We just need to remove the $p$. The minimal editing distance from $X=Computer$ to $Y=Commuter$ is $2$. First we need to remove the $p$, and then we need to add $m$. Pretty straightforward.

The question was to find a recursive formula for $d(i,j)$ where $d(i,j)$ is the minimal editing distance from $X=x_1...x_i$ to $Y=y_1...y_j$.

What I did:

Firstly the edge cases are pretty clear, $d(i,0)=i$ and $d(0,j)=j$ and $d(0,0)=0$.

Now comes the trickier part:

Suppose $i>j$. then at least we need $i-j$ actions so $X$ and $Y$ will be same length, length $j$. Now they are both same length so we have the optimal solution $d(j,j)$.

and if $j \geq i$, then the opposite happens, we need $j-i$ so they are same length, and from there we need $d(i,i)$ steps.

So $d(i,j)=i-j+d(j,j)$ if $i>j$, and $d(i,j)=j-i+d(j,j)$ if $j\geq i$.

Is this the correct result? This doesn't seem correct because well, won't $d(i,i)$ depend on what the letters actually are? What letters are we deleting / adding? It seems too simple.

Edit: Also this is wrong because for example the case where $i=j$. I define $d(i,i)$ using $d(i,i)$ so this is clearly wrong.


Managed to find an answer that fits and seems to work:

if $x_i \neq y_j$ then $d(i,j)=min(d(i-1,j)+1,d(i,j-1)+1,d(i-1,j-1)+2)$

and if $x_i=y_j$ then $d(i,j)=min(d(i-1,j)+1,d(i,j-1)+1,d(i-1,j-1))$


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.