5.7. Pseudo Code for 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 method used to measure how similar two strings or documents are by determining the number of operations needed to convert one string into another. This can include operations such as insertion, deletion, and substitution of characters.

Imagine you are editing a document and need to change certain words. Each time you add a word, remove a word, or correct a typo, you are performing an 'edit'. The total number of these edits gives you a sense of how much work you've put into changing the original document into the revised one.

So, the edit distance with the minimum number of edit operations required to transform one document to another, so we have to define what we mean by editing operations. So, let us just start with very basic operation, either you can insert a character or you can delete a character or you can replace one character by another one in one step.

There are three fundamental operations in edit distance: inserting a character, deleting a character, and replacing one character with another. Each of these operations contributes to the total edit distance. For instance, if you replace 't' with 'v', it counts as a single substitution operation.

Think of a puzzle where you need to swap pieces around to match a picture. Every swap (insertion, deletion, or replacement) helps you get closer to completing the image, just like each edit moves you closer to making one document match another.

If the edit distance is suppose to 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, possible to do it in more clever way less than 48.

The edit distance for two sentences, which includes 28 insertions, 18 deletions, and 2 substitutions, totals to 48 changes. However, the actual edit distance may be less than 48 if there are more efficient ways to achieve the same result using fewer operations.

When cooking, you might think you need many ingredients, but sometimes you find that combining or using substitutes can simplify the recipe, just like finding a more efficient way to change one document into another can reduce the total number of edits required.

So, the edit distance is also called the Levenshtein distance, because it was first proposed by the Soviet, now Russian scientist called Vladimir Levenshtein and this like the longest common subsequence problem, it is extremely useful in practice.

The edit distance, known as the Levenshtein distance, is widely used in various applications like spell checking, where it helps find the closest word in a dictionary to a misspelled word. This application is critical for both software development and improving user experience in search engines.

Consider when you send a text often auto-correct suggests 'did you mean' based on your typing. This function uses edit distance to determine the closest possible word to what you typed, similar to how humans correct each other’s mistakes.

So the interesting thing about edit distance is that it also allows a substitution of one character and other. It might give us a slightly different metric from longest common subsequence.

Edit distance incorporates substitution, giving it a different angle compared to the longest common subsequence (LCS) which only considers insertions and deletions. By allowing substitutions, edit distance can provide more nuanced measurements of string similarities based on allowed operations.

Imagine a line of dancers where some have minor costume changes (substitutions) while others may have simply changed the sequence of their moves (inserts/deletes). The edit distance reflects all these kinds of changes, making it a comprehensive evaluation of differences.

So, the inductive substructure in edit distance is exactly the same as in LCS. Every position depends on i plus 1 j plus 1 and though i plus 1 j and i j plus 1.

The computation of edit distance uses dynamic programming, where the solution for larger problems builds upon solutions to smaller subproblems. This is similar to LCS, where each character's comparison leads to recursive evaluations until the base case is reached.

Think about building a complicated LEGO structure, where each smaller block's placement relies on the previous blocks' configurations. Like drawing connections between parts, each step either fixes or changes the configuration progressively.

So, 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.

While the computational complexity is O(m*n), meaning we need to fill a table of size m times n, it is possible to reduce the space used in computations by only keeping track of recent columns or rows instead of the entire table. This can significantly save memory while maintaining the time complexity.

Imagine packing for a trip; instead of bringing your entire closet, you only bring essential clothes for the trip duration. This way, you travel lighter without compromising the actual time spent selecting your outfits each morning.

--