Sign in to continue learning
Minimum Edit Distance has a wide variety of applications. It allows you to implement spelling correction, document similarity, machine translation, DNA sequencing, and more. I will also show you the different types of edits. You have already seen how to build AutoCorrect using Edit Distance, but consider a slightly different problem. What if you were given two words, strings, or even whole documents and you wanted to evaluate how similar they are? Minimum Edit Distance can be used to do this. Given two strings, the Minimum Edit Distance is the lowest number of operations needed to transform one string into the other. It has many applications. In NLP, for example, it could be used in spelling correction, document similarity, and machine translation. It can also be found in computational biology and DNA sequencing. For calculating Minimum Edit Distance, you will use three types of edit operations. All three operations that you already know. Insert, Delete, and Replace. For example, to turn Play into Stay, what is the minimum number of edits required to make this happen? So to turn P into S, you replace P with an S. And to turn L into T, you replace L with a T. Both A and A are the same, so do nothing. And it's the same with Y and Y. So the total number of edits is 2. Until this point, you've considered all edit operations to cost the same. That is, a cost of 1. But now you will consider a different cost for each type of operation. You will use these costs to calculate the edit distance, which now represents the total edit costs. This is what you are trying to minimize. It is simply the sum of costs for the edits that were made. Insert and Delete will have a cost of 1, and Replace has a cost of 2. This makes intuitive sense if you think of replacement as a delete followed by an insert. Calculate for this example. You have 2 replace edits at a cost of 2 each, for a total edit distance of 4. This is a relatively simple example, and it was possible to find the minimum edit distance just by looking at it. But imagine the number of operations between much longer strings, and large corpora of text, or even DNA strings. You can try and solve these problems by brute force, adding one edit distance at a time, and enumerating for all possibilities until one string changes to the other. But this could take a very, very long time. In fact, by solving this way, the computational complexity increases exponentially as each string grows in length. A much faster way is by using a tabular approach. You will implement this next. The tabular approach I spoke about allows you to speed up the enumeration of all possible strings and edits. In doing so, you will also be learning about a new concept known as dynamic programming. We'll see about this in the next video.