Minimum Edit Distance

Intro

This blog post is primarily focused on strengthening the concept of Dynamic Programming by using Minimum Edit Distance problem. Although you won’t require any knowledge of Dynamic Programming to understand this post. However, if you are also looking for an elaborate explanation of Dynamic Programming, then please visit this post .

What is Minimum Edit Distance ?

Given two strings P and Q, it is possible to transform P into Q or vice-versa by performing the following operations on one of the strings. For e.g let us assume that we need to transform the string P into the string Q. Then, the following operations done in some sequence, will complete the job.

  • Insertion – insert a missing character into P (the missing character is present in Q)
  • Deletion – deleting a character from P (which might not be present in Q)
  • Replacement – replacing a character in P from the corresponding character in Q

Here are three simple use cases:

Insertion

  • P is “abd”
  • Q is “abcd”
  • Inserting the character “c” in P between “b” and “d” would result into Q

Deletion

  • P is “abcd”
  • Q is “acd”
  • Deleting the character “b” from P will result into Q

Replacement

  • P is “abd”
  • Q is “abc”
  • Replacing “d” in P with “c” from Q, will result into Q

So , the number of operations performed to transform P into Q is called the edit distance. Now, here is a funny thing, you can perform infinite operations on P to transform into Q. For e.g.: In the replacement use case, let us use the following steps:

  • Delete “d”
  • Insert “a” at the end
  • Insert “c” at the end”
  • Delete the last “a” from P

This is why the blog post states “Minimum Edit Distance” because we are interested in the minimum number of operations used to transform P to Q.

Intuition behind solving the Minimum Edit Distance

So, as we see that there can be infinite values for the Edit Distance, so we definitely cannot exhaustively search the complete solution space. Let us evaluate, what we know about the problem and if it can be of any help.

  • We have strings P and Q
  • Let say we want to transform P to Q.
  • At any point of time, we try to do either of the below things:
    • either insert/delete the character from P (in case the corresponding characters do not match)
    • replace the character in P with the corresponding character in Q.
    • do nothing (if the characters match)

Let me explain this to you using a concrete example:

Case 1:

  • P –
  • Q –

Both the strings P and Q are empty. What does it take to transform P to Q. The answer is absolutely nothing. Hence, you can do it in zero operations. And we can say that the Min Edit Distance between P and Q is zero.

Case 2:

  • P – HELLO
  • Q –

Here, P has some content but Q is empty. I am sure, you already know that the Minimum Edit Distance in this case is 5. Here is how we can prove it.

The first column represents the characters of the strings P and the first row represents the characters of the String Q.

The grey cells, represent the case, when both Strings were empty. And the value in cell(0,0) represents the minimum edit distance of the two strings P(0..0) and Q(0..0).

  • The representation P(i..j) means the sub string of P starting at character i and ending at character j . Hence, the expression P(0..0) means the sub string of P starting at character 0 and ending at character 0. 

Now according to case 2, Q is still empty. However,  P has a String “HELLO”.

Let us just consider P(0..1), which means the sub string starting at 0 and ending at 1. What takes sub string H to transform to an empty string. And the answer is one deletion. If we delete the H, we will get an empty string.

Similarly, consider P(0..2), which is “HE”. To transform it to an empty string, we need to deletions. So on and so forth.

Case 3:

  • P – HELLO
  • Q – HOLLOW

Note: The dark grey row and columns are not part of the table, they are here, just for convenience.

Now, let us look at row (0) – the green row. Each cell in the represents the minimum edit distance for transforming an empty string to sub strings of Q. For e.g. :

  1. Cell (0,0) tells us the minimum edit distance between two empty strings. (Remember case 1)
  2. Cell (0,1) , tells us what it takes to convert an empty string to “H” – the answer is one insertion.
  3. Cell (0,2), tells us what it takes to convert an empty string to “HO” — the answer is two insertion. So on and so forth.
  4. Similarly, if you look at the row (1), cell (1,1) tells us, what it takes to transform ” H” (from P) to “H” (from Q) and the answer is 0.
  5. Cell(1,2) on the other hand tells us that it takes 1 replacement to transform “H” (from P) to  “HO” )from Q, and the answer is 1.
  6. If you look at cell (3,5), it tells us that it will take 3 operations to transform from “HEL” (from P) to “HOLLO”  (from Q)
  7. When we examine cell (5, 6) it tells us that it takes 2 operations to transform ‘HELLO” to “HOLLOW”.

Possibly you noticed that I was able to point out the exact operations for bullet points 2 and 3. However, in the other bullet points, it is simply tough to find the set of operations done in a given order. We will need another sophisticated technique to find that out.