5.6. Inductive Structure of Edit Distance

Having looked at the longest common subword and subsequence problem, we now look at a closely related problem called Edit Distance.

Edit Distance is a way to measure how similar two texts are. It quantifies the minimum number of operations required to change one text into another. These operations typically include inserting, deleting, or replacing characters.

Imagine you are changing a recipe. If the original recipe says 'add 2 cups of sugar' and you modify it to 'add 3 cups of sugar', you can think of this as needing to replace '2' with '3', which counts as one edit operation.

The aim is to measure how similar two pieces of texture, it is so called document similarity problem.

Document similarity involves determining how closely two versions of a document relate to each other. Edit Distance is a practical method for this comparison, as it calculates how many edits are necessary to convert one document into another.

Consider tracking changes in a Word document. When you edit a document, the software shows which words were added, deleted, or changed, reflecting the edit distance between versions.

So, we have to define what we mean by editing operations. Either you can insert a character or you can delete a character or you can replace one character by another one in one step.

The three basic operations in Edit Distance are: 1) Inserting a character, 2) Deleting a character, and 3) Replacing a character. Importantly, a replacement can be viewed as a two-step process of deletion followed by insertion, but for simplicity, it is treated as a single operation.

Think of formatting a document. If you want to change 'color' to 'colour', it's similar to deleting the 'o' and adding 'u', which showcases insertion and deletion operations in practice.

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 it in 48 characters.

The Edit Distance calculated here is also known as Levenshtein distance. It represents the least amount of edits needed between two text strings. For example, if transforming one string into another requires 48 edits, then that is the upper limit for the edit distance.

Imagine someone types 'book' as 'bokk'. The spell checker analyzes and suggests changes by measuring the distance - which in this case involves just replacing a letter.

So, the first thing is to suggest spelling corrections. Now, if somebody types something that is a wrong, then it is spelling corrective will have to suggest the correct word from the dictionary to replace it.

Edit Distance has practical applications such as suggesting spelling corrections in word processors or search engines. When a user mistypes a word, the software calculates which correct word from the dictionary is closest based on edit distance.

When you type 'texhnology' instead of 'technology', your phone may suggest 'technology' because it recognizes that only a few edits separate the two words.

if you want to compare the genetic information in two different species, then it is natural to become to compare them in terms of the content of the DNA.

In genetics, edit distance helps compare the DNA sequences of different species. This comparison can illustrate the degree of similarity or difference in their genetic make-up.

Consider two different species, like dogs and wolves. By applying edit distance, scientists can identify how many genetic 'edits' exist between them, reflecting their evolutionary relationship.

So, the inductive substructure in edit distance is exactly the same as in LCS.

The inductive structure for Edit Distance follows a specific process which is similar to the longest common subsequence (LCS) problem. It involves using previously calculated distances to build the solution dynamically through recursion.

Think of climbing stairs. If you know how many steps it takes to get to each previous stair, you can easily calculate the total number of steps to reach the summit without starting from the ground each time.

So, this is a space complexity. So, we have this table that we have to compute which we have a green is m times n.

The space complexity for calculating Edit Distance can be optimized. Instead of using a full table of size m*n, you can reduce it to just two columns, since each column depends only on the previous one.

Imagine packing for a trip. Instead of bringing your whole wardrobe, you optimize and only take two outfits that you can mix and match in different combinations, utilizing space more efficiently.

--