Introduction 

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.

Section 2- Usage of Minimum Edit Distance

You have already seen how to build autocorrect using edit distance. Let's consider a slightly different problem.

• What if you are 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 an LP 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.

Section 3- Calculate Edit Distance 

For calculating minimum at a distance you will use three types of edits operations. All three operations that you already know inserts delite and replace for example to turn play and to stay what is the minimum number of credits required to make this happen?

Section 4- Replace P to S

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 edits operations to cost the same. That is a cost of one 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. Inserts and deletes will have a cost of 1 and replace has a cost of 2. This makes intuitive sense if you think of replacement as it deletes followed by an insert. Calculate for this example. You have to replace edit at a cost of 2 each for a total added 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 couple of texts 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 blog