5.8. Complexity Analysis

So, the aim is to measure how similar two pieces of texture, it is so called document similarity problem. So, let us look at the following two sentences; the first sentence says the students who were able to appreciate the concept optimal substructure property and its use in designing algorithms. The second sentence says the lecture taught the students to appreciate how the concept of optimal substructures can be used in designing algorithms. So, the third sentence here indicates how one might obtain one of these two from the other.

Edit distance is a way to determine how similar two strings (or documents) are. It does this by calculating the minimum number of operations required to turn one string into another. The operations usually include inserting, deleting, or replacing characters. Two example sentences were given to illustrate various text documents that can be edited into one another.

Think of two drafts of a letter you wrote to a friend. You might have written one version with a few changes made in the second version. Edit distance helps us figure out how many changes you made by counting each editing operation like adding or removing sentences.

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 like this...So, we have 28 characters which have been inserted, 18 characters have been deleted and 2 characters have been substituted. So, the total number of changes we made is 48.

To find the edit distance between two sentences, we first identify the changes made: how many characters were inserted, deleted, or substituted. In our case, the information highlighted indicated a total of 28 insertions, 18 deletions, and 2 substitutions. By adding these numbers, we found that a total of 48 changes were necessary, which sets an upper limit for the edit distance.

Imagine editing a recipe. You might add ingredients, remove some, or change quantities. Counting each change helps you understand the effort involved in making the new version of the recipe, just like finding the edit distance captures the differences between two texts.

If the edit distance is suppose be the minimum number of changes, it cannot be more then 48... So, the edit distance is at most 48 for the two sentence that we shown earlier.

The edit distance we calculated reflects the minimum operations needed to transform one sentence to another, known specifically as the Levenshtein distance. This measurement is crucial in linguistic tasks such as spell-checking, allowing us to suggest corrections based on how many changes would make a typed word match a recognized word.

Consider typing a word incorrectly on your phone. Your device suggests corrections based on how closely your misspelled word matches words in its dictionary, often using algorithms that calculate the edit distance to find the best suggestion.

This also happens when you type queries and search engines. So, if you type something to Google, Google will sometimes change your query to a word which is meaningful...

Edit distance is not only useful in document editing but also in technology applications like search engines and genetic research. Search engines adjust your search terms to better align with exact queries, effectively using edit distance to maximize user search efficiency.

When searching on Google, you may mistype a word. The search engine will often recognize the typo and suggest the correct spelling, allowing you to easily find the information you intended to look for. This is analogous to how edit distance helps determine the closest correct terms.

So, going back to longest common subsequence, it says that if two letters match at the beginning of a word, then it is useful to assume that the common subsequence includes that...

The dynamic programming approach to edit distance involves going through each character in both strings, comparing them while applying specific rules based on character matches or mismatches. This way, we can break down the overall problem into manageable subproblems, making the calculations more efficient.

Think of it like solving a jigsaw puzzle. You approach it piece by piece, checking to see if pieces fit, and making adjustments as needed, ensuring you build up the final solution by carefully managing where each piece goes based on its surrounding pieces.

Now, in all these three problems there is another issue which we have not addressed...So, therefore, there was actually no need to rule m times n size table as storage.

Editing distance calculations can be memory intensive, typically requiring an m x n table, where m and n are the lengths of the two strings. However, because only the current and previous columns or rows are needed for calculations, we can optimize the space usage dramatically to reduce the requirement from m x n to just 2 x n or 2 x m.

Imagine you’re baking and you need to repeatedly check your ingredient list. Instead of writing out the whole list every time, you could just note the most recent changes, allowing you to keep your workspace simpler and more efficient, much like how we optimize space in edit distance calculations.

--