5.9. Space Complexity

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.

The edit distance aims to quantify the similarity between two text pieces or sentences. By comparing the accuracy of both sentences, the distance indicates how many edits—like insertions, deletions, or substitutions—are required to transform one into the other. This measurement is crucial for applications like spell checking and document comparison.

Imagine you are rewriting a letter. If you change certain words, add sentences, or remove some lines, the number of changes you make reflects the difficulty of transforming the original letter into the new one. The edit distance is similar; it counts the required changes between two pieces of text.

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. So, replacing of course could be a think taught of us deleting and inserting, so that could be a two step operations, I delete the character and then I insert the character I want.

Editing operations can be classified into three basic types: insertion (adding a character), deletion (removing a character), and substitution (changing one character for another). It's important to note that substitution is treated as a single operation, even though it can be viewed as two steps: deleting one character and inserting another.

Think of editing a photo. If you want to change a blue sky to a sunset (substitution), you could erase the sky (deletion) and then paint a sunset (insertion). The concept is similar when editing text, as each change contributes to the overall edit distance.

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 it in 48 characters. The total number of changes we made is 48.

Calculating the edit distance involves determining the minimum number of operations needed to change one string into another. This distance provides a clear numerical value reflecting how different two texts are. In this scenario, the figure of 48 suggests that this is the least amount of edits necessary to make one sentence resemble the other.

Consider trying to make a cake recipe that has missing or incorrect ingredients. If you need to replace or add 48 ingredients to get it right, it illustrates the idea of 'edit distance' in a practical sense—you can visualize how close the incorrect recipe is to the original one.

If the edit distance is suppose be the minimum number of changes, it cannot be more then 48, because they already shown that it is possible to do in 48 characters. So, the edit distance is also called the Levenshtein distance.

The Levenshtein distance is a specific way to quantify the edit distance. It was developed by mathematician Vladimir Levenshtein. This metric is commonly used in spell checkers or search engines to propose corrections for misspelled words by measuring how closely they match words in a dictionary based on the number of edits required.

Imagine you mistyped a word in a text message. Your phone's autocorrect suggests the correct version based on how many letters you need to change. This is the Levenshtein distance at work—it's determining the proximity of your typo to every word in the dictionary and suggesting the closest match.

Now, if you want to compare the genetic information in two different species, then it is natural to compare them in terms of the content of the DNA and DNA have just long sticks.

Edit distance is not limited to text; it serves in various fields, including genetics. When comparing DNA sequences, edit distance can assess how similar or different two species are. A lower edit distance suggests closer relationships between species, which can be significant in evolutionary studies.

When studying family trees, if you find that two relatives have many similar traits (like eye color or height), they might be more closely related. Similarly, in genetics, the edit distance between two DNA sequences tells us about their similarities and differences, shedding light on related species or organisms.

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.

Calculating the edit distance typically takes time proportional to the lengths of the two strings (m and n). This relationship leads to a time complexity of O(m*n), where a grid or table is often used to track the minimum changes needed. The algorithm fills this table based on previous calculations, allowing efficient computation of the edit distance.

Think of filling out a large spreadsheet where each cell contains a calculation based on the values of other cells. This process can be time-consuming, but after setting it up, repeated calculations become quicker as the framework has already been established. Similarly, with edit distance calculation, using prior values optimally speeds up finding the answer.

So, at any given point, when I am computing this second column for example, I only read the first column.

While computing the edit distance, you do not always need to maintain the entire matrix, because each calculation only relies on the previous row and the current row/column. This can lead to a significant space optimization, enabling the entire process to run with much less memory than initially thought.

Think of packing for a trip; instead of taking everything you own (like the original matrix), you only take essentials (the current row/column). By carefully deciding what to bring, you travel lighter while still being able to manage. In computing edit distance, you can reduce the space needed while still accomplishing the task effectively.

--