You can find the dynamic programming code to calculate the levenshtein distance between two strings here. The code will calculate the levenshtein distance and output the edit distance table as described below.

Minimum edit distance allows us to assess how similar two strings are. For example, the word ‘graffe’ has few words that are similar to it such as ‘graf’, ‘graft’, ‘grail’, ‘giraffe’ but which one is the closest. This is useful for computational biology or IR. The minimum edit distance is the minimum number of editing operations such as insertion, deletion and substitution that are needed to transform one into the other.

As shown above, in order to turn ‘intention’ to ‘execution’ we need to do few edition. If each operation has a cost of 1, the distance between the word ‘intention’ and ‘execution’ is 5. The Levenshtein distance is when substitution operation has a cost of 2 which means that so the total distance is now 8. We can use this has an evaluation of how well machine translation/speech recognition works by calculating the distance (cost) of what the machine translation does vs the actual text.

How to find the minimum edit distance?

Intuitively, we would search for a path (sequence of edits) from the start string to the final string. We will start with the initial state (the word we’re transforming), follow by edit operations (insert, delete and substitute). We will then have a goal state (the word we’re trying to get to), by which then we can calculate the path cost (number of edits – what we want to minimise). However, the space of all edit sequences is huge and we can’t afford to navigate naively. There are lots of distinct paths that wind up at the same state and we don’t have to keep track of all of them. We just need to keep track of the shortest path to each of those revised path. For example:

Two strings: X of length n and Y of length m. We will define a distance matrix D(i, j) which is the edit distance between X and Y i.e. the first i characters (n) of X and the first j characters (m) of Y. Therefore the edit distance between X and Y is D(n, m).

Computing Minimum Edit Distance

We can use dynamic programming which combines solutions to subproblems to compute D(n, m). This is a bottom-up approach where we compute D(i, j) for small i, j values and then compute larger D(i, j) based on previously computed smaller values. Below is an example (Levenshtein):

Ryan

Ryan

Data Scientist

Leave a Reply