5.2. Measuring Edit Distance

Having looked at the longest common subword and subsequence problem, we now look at a closely related problem called Edit Distance. So, the aim is to measure how similar two pieces of texture, it is so called document similarity problem.

Edit Distance is a metric that quantifies how dissimilar two strings (or texts) are by counting the minimum number of operations required to transform one string into the other. This is useful for examining document similarity, where we want to know how closely related two pieces of text are.

Think of Edit Distance like a puzzle where you have two pictures and want to see how you can turn one into the other. The fewer the moves (insert, delete, or replace pieces), the more similar they are. For example, if you want to change 'cat' to 'hat', you only need to replace the 'c' with an 'h', which means the Edit Distance is 1.

If you have used certain document preparation systems which allow you to track changes, it will typically indicate the changes between one version of a document and other version. [...] So, we have replaced the t by v and an s by n.

Edit operations are essential to calculating Edit Distance. There are three primary operations: insertion (adding a character), deletion (removing a character), and substitution (replacing one character with another). In the provided example, different colors are used to denote these operations: green for characters added, red for deleted characters, and yellow for substitutions. This visual aids in understanding how the transition from one document to another requires these operations.

Imagine you are editing a friend's essay. You add some words (insertions), cross out some (deletions), and change a few others (substitutions) based on your recommended edits. Each of your changes helps transform the original essay to a new, improved version. This helps you see how many changes you truly made, just like in the Edit Distance.

So, in our example we claimed that 28 characters were inserted, 18 were deleted and 2 were substituted. [...] the total number of changes we made is 48.

To calculate the Edit Distance, we add up all the operations performed. In this case, we had a total of 28 insertions, 18 deletions, and 2 substitutions, which sums up to 48 changes. This total indicates the maximum possible Edit Distance at this stage but suggests that a more efficient transformation might exist that requires fewer changes.

Think of it like a store making changes to their inventory system. They might add 28 new items (insertions), remove 18 outdated items (deletions), and update 2 item names (substitutions). The total number of changes gives the store an idea of how much work they’ve put into keeping their inventory up-to-date.

If the edit distance is suppose be the minimum number of changes, it cannot be more than 48, because they already shown that it is possible to do in 48 characters. [...] The edit distance is at most 48 for the two sentences that we shown earlier.

The minimum number of operations required to transform one string into another is also known as the Levenshtein Distance. This term comes from Vladimir Levenshtein, who first proposed this concept. The distance helps us determine how closely related two strings are, with fewer operations indicating greater similarity.

Imagine trying to create a smoothie that matches a friend’s favorite. If you know you need to add, remove, or replace certain ingredients, the fewest actions you take to recreate that smoothie is your ‘Levenshtein Distance’ with respect to their recipe. The more actions it takes, the further away your smoothies are from matching theirs.

So, one criterion for choosing is to identify among all the words in the dictionary that are possible which one is closest to the one that has been typed. [...] Edit distance is also used to compare the genetic information in two different species.

Edit Distance has practical applications in various fields. One primary application is in spell-checking software, which uses Edit Distance to suggest correct spellings by determining which word in the dictionary is closest to the misspelled word. Similarly, Edit Distance can be employed in biology to analyze DNA sequences between different species, helping scientists understand genetic similarities and differences.

Consider how your phone suggests corrections when typing a message. If you mistype ‘teh’, it suggests ‘the’ based on Edit Distance. Similarly, in genetics, it’s like trying to figure out how two species are related by examining their ‘recipes’ for life as encoded in DNA, finding out how many adjustments are needed to transform one sequence into another.

The interesting thing about edit distance is that it also allows a substitution of one character and other. [...] two letters match at the beginning of a word, then it is useful to assume that the common subsequence includes that.

The longest common subsequence (LCS) and edit distance share a close relationship. While LCS focuses on the longest sequence that appears in both strings without alteration, the edit distance includes all necessary changes to make one string resemble another fully. Understanding where characters can remain unchanged directly influences the computation of both metrics.

Imagine you have a list of favorite foods. The longest common subsequence would be the items you both like that match perfectly, while the Edit Distance would tell you how many changes either of you would need to make to have the same list. They are two sides of the same coin, helping you see both similarities and differences.

Now, in the edit distance problem we have a similar criterion, if a[i] is equal to b[j], then I have nothing to do. [...] take the minimum of these three requires the minimum work overall.

The inductive structure of Edit Distance implies that if two characters match, no operations are needed. However, if they do not match, we have three choices: substitute one character, delete a character, or insert a character. The goal is to determine which of these actions leads to the minimum overall edit distance through recursion.

Think of organizing a file cabinet. If both cabinets have the same label, you don’t need to change anything; just move on. However, if two cabinets have different labels, you must decide whether to change one label, remove a cabinet, or add a new label. Your aim is to keep the process as straightforward as possible, just like determining the least complicated path to achieve matching document labels.

So, this gives us the final inductive structure that we want. [...] so that the edit distance when u is empty and v has z position j is n minus j plus 1.

Using dynamic programming, we can efficiently compute the Edit Distance by breaking the problem into smaller subproblems, focusing one step at a time. By creating a table to store intermediate Edit Distances, we can gradually work through the entire problem until we reach the solution. This involves initializing base cases, calculating values, and then using these stored values to derive the overall distance.

Visualize climbing a staircase where each step represents a calculation towards the final distance. Each calculation is like finding your footing at a step; you rely on the previous steps you’ve taken to ensure you don’t go back. Once you reach the top, you have computed the Edit Distance without needing to revisit the entire staircase.

The complexity is order m times n, it is exactly the same as the previous one, because after fill up this table of size m times n and it takes a constant time to compute. [...] the path on the whole thing.

While the time complexity of calculating the Edit Distance is O(m*n), recent advances allow the space required to be significantly reduced. Given that only the current and previous rows (or columns) of the dynamic programming table are necessary at any given computation point, we can limit our storage dramatically, aiding efficiency.

Imagine trying to follow a recipe that needs multiple ingredients. Traditionally, you might use a large counter to keep everything organized. However, if you realize you only need two bowls at a time to mix ingredients, you can reduce your workspace significantly, making it easier and faster to create your dish while still keeping everything effective and on point.

--