Edit Distance
Ever wondered how the auto suggest feature on your smart phones work? How does your phone always know which word you’re attempting to spell? The solution is simple and effective. Smart phones usually use the Edit Distance algorithm to calculate that. It calculates the difference between the word you’re typing and words in dictionary; the words with lesser difference are suggested first and ones with larger difference are arranged accordingly.
Another place we might find the usage of this algorithm is bioinformatics. Here, the algorithm is used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T.
Now let us move on to understand the algorithm.
EXPLAINING THE PROBLEM
Edit Distance also known as the Levenshtein Distance includes finding the minimum number of changes required to convert one string into another. It is a very popular question and can also be found on Leetcode.
Types of changes/operations allowed in this problem are:
1. Replacement
2. Insertion
3. Deletion
For example; if I needed to convert BIRD to HEARD, I would need to make 3 changes, those being:
1. Replacing ‘I’ of BIRD with ‘A’. Thus, BIRD now changes to BARD.
2. Replacing ‘B’ of BIRD with ‘E’. Hence, it further changes to EARD.
3. Adding H at the beginning. Finally, we get HEARD.
Hence, we see that after performing 3 operations, BIRD has now changed to HEARD. We can also say that the edit distance from BIRD to HEARD is 3.
EXPLANATION OF THE OPERATIONS
To find the edit distance between two strings we’re essentially going to check the edit distance for every cross section of substrings between the two strings. Hence, this problem has over-lapping sub problems. Now we’re going to take a look at the four cases we encounter while solving each sub problem.
- Do Nothing: There will be one case where the last character of both strings is the same. In this case, the edit distance of both the strings is the same as the edit distance of the strings minus the last character as they are already same and don’t need any editing.
Let’s see an example; the total number of changes need to convert BIRD to HEARD is essentially the total changes needed to convert BIR to HEAR. This is because the last character of both strings is the same (i.e. ‘D’) and doesn’t need any changes. So remember; no mismatch, no operation.
2. Replace: This case can occur when the last character of both the strings is different. For example; if I wanted to convert ‘BI’ to ‘HEA’, then we’d notice that the last characters of those strings are different. Hence to convert ‘BI’ to ‘HEA’, we just need to convert ‘B’ to ‘HE’ and simply replace the ‘I’ in ‘BI’ to ‘A’. This way we have changed the string to ‘BA’ instead of ‘BI’. So now, we just need to calculate the distance between the strings minus the last character. Hence our edit distance of ‘BI’ and ‘HEA’ is 1 + edit distance of ‘B’ and ‘HE’.
Remember to, transform everything before the mismatch and then add the replacement.
3. Deletion: Deletion can also be considered for cases where the last character is a mismatch. In this example; if we want to convert ‘BI’ to ‘HEA’, we can simply drop the ‘I’ from ‘BI’ and then find the edit distance between the rest of the strings.
Remember, if the last character is a mismatch simply delete the last character and find edit distance of the rest.
4. Insertion: Another way to resolve a mismatched character is to drop the mismatched character from the source string and find edit distance for the rest. In this example; we wish to convert ‘BI’ to ‘HEA’, notice the last character is a mismatch. One possible solution is to drop ‘A’ from ‘HEA’. This way we’ll end up with ‘BI’ and ‘HE’, after finding the distance between these substrings, because if we find the distance successfully, we’ll just have to simply insert an ‘A’ at the end of ‘BI’ to solve the sub problem.
Remember, if the last character is a mismatch simply ignore the last letter of the source string, find the distance between the rest and then insert the last character in the end of destination string.
We want to take the minimum of these operations and add one to it because we’re performing an operation on these two characters that didn’t match.
Now let us consider the base cases:
1. In order to convert an empty string to any string “xyz”, we essentially need to insert all the missing characters in our empty string. Hence, in order to convert an empty string to a string of length m, we need to do m insertions; hence our edit distance would become m.
2. Similarly in order to convert a string of length m to an empty string “” we need to perform m number of deletions; hence our edit distance becomes m.
SOLVING THROUGH RECURSION
One of the naïve methods of solving this problem is by using recursion. The time complexity for this approach is O(3^n), where n is the length of the longest string. The time complexity of this approach is so large because it re-computes the answer of each sub problem every time with every function call.
Below is code for the same:
SOLVING THROUGH DYNAMIC PROGRAMMING
The more efficient approach to solve the problem of Edit distance is through Dynamic Programming. In Dynamic Programming algorithm we solve each sub problem just once and then save the answer in a table. By following this simple step, we can avoid the work of re-computing the answer every time like we were doing in the recursive approach.
One thing we need to understand is that Dynamic Programming tables aren’t about remembering patterns of how we fill it out. It’s about knowing what is happening and why we do we fill it the way we do; what are the sub problems and how are we getting optimal solution from the sub problems that we’re breaking down.
So let us understand the table with the help of our previous example i.e. converting ‘BIRD’ to ‘HEARD’
- We start by writing all the characters in our strings as shown in the diagram below. We put the string to be changed in the horizontal axis and the source string on the vertical axis.
2. Now let us fill our base case values. As discussed above, we know that the edit distance to convert any string to an empty string is the length of the string itself. So the edit distance to convert “B” to empty string is 1; to convert “BI” to empty string is 2 and so on.
3. Similarly to convert an empty string to a string of length m, we would need m insertions. Thus to convert an empty string to “HEA” the distance is 3; to convert to “HE” the distance is 2 and so on.
4. Now that we have filled our table with the base case, let’s move forward. Let’s consider the next case where we have to convert “B” to “H”. Here we will perform a simple replace operation. We want to take the minimum of these operations and add one when there is a mismatch. So in the table, we will just take the minimum value between cells [i-1,j], [i-1, j-1] and [i, j-1] and add one. In this case, we take 0 from diagonal cell and add one i.e. we performed a replace operation.
5. However, when the two characters match, we simply take the value of the [i-1,j-1] cell and place it in the place without any incrementation.
6. Now that we have understood the concept of why the table is filled the way it is filled, let us look into the formula:
Where A and B are the two strings. Hence, our table becomes something like:
Where the arrow indicated where the current cell got the value from. The cell located on the bottom left corner gives us our edit distance value. In this case our answer is 3. That means in order to change ‘BIRD’ to ‘HEARD’ we need to perform 3 operations.
BACK TRACKING FOR SOLUTION
In order to find the exact changes needed to convert the string fully into another we just start back tracing the table from the bottom left corner and following this chart:
Please take in note that this chart is only valid when the current cell has mismatched characters. If the characters are matched we simply move diagonally without making any changes in the string. This is traced back till we find all our changes.
In our case, let us start back tracing:
1. We start with cell [5,4] where our value is 3 with a diagonal arrow. But since the characters at those positions are the same, we don’t need to perform an operation. Hence we simply move to cell [4,3]
2. In cell [4,3] we also have a matching set of characters so we move to [3,2] without doing anything.
3. At [3,2] we have mismatched characters with a diagonal arrow indicating a replacement operation. Hence, we replace ‘I’ in ‘BIRD’ with ‘A’ and again follow the arrow.
4. At [2,1] we again have mismatched characters similar to point 3 so we simply replace ‘B’ with ‘E’ and move forward.
5. At [1,0] we have an upwards arrow meaning insertion. Hence we insert ‘H’ at the beginning of our string then we’ll finally have ‘HEARD’.
Hence, we have now achieved our objective of finding minimum Edit Distance using Dynamic Programming with the time complexity of O(m*n) where m and n are the lengths of the strings.
Code:
I’ve implemented Edit Distance in python and the code for it can be found on my GitHub. I’ve also made a GUI based program to help learners better understand the concept. Here is its walkthrough:
References:
- Introduction to Algorithms — Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- YouTube video on Edit Distance Between 2 Strings by Back To Back SWE.
- GeeksForGeeks article on Edit Distance
