Data Structures and Algorithms: Edit Distance (Levenshtein Distance)

Welcome to our deep dive into the fascinating world of Edit Distance, also known as Levenshtein Distance! In this comprehensive guide, we'll explore how to measure the similarity between two strings by calculating the minimum number of edits (insertions, deletions, or substitutions) required to transform one string into another.

💡 Pro Tip: This concept is essential in various real-world applications such as spell checkers, speech recognition, and bioinformatics!

Understanding Edit Distance (Levenshtein Distance)

Edit Distance is a string metric for measuring the difference between two sequences. In our case, these sequences will be strings of characters. The idea is to find the minimum number of operations (insertions, deletions, and substitutions) required to transform one string into another.

📝 Note:

Insertion: Adding a character to a string that is not already present.
Deletion: Removing a character from a string.
Substitution: Replacing a character in a string with another character.

Algorithm: Dynamic Programming Approach

The Edit Distance problem can be solved using dynamic programming. We'll create a 2D table (matrix) where each cell M[i][j] represents the minimum number of edits required to transform the first i characters of the first string into the first j characters of the second string.

Here's the logic behind the dynamic programming approach:

If both strings are empty, there are no edits required, and the Edit Distance is 0.
If the first character of the first string is the same as the first character of the second string, we're off to a good start! The Edit Distance is the same as for the remaining characters, so M[1][1] = M[0][0].
If the first characters are different, we'll have three options:
- Insert the first character of the first string (s1), so M[1][1] = M[0][1] + 1.
- Insert the first character of the second string (s2), so M[1][1] = M[1][0] + 1.
- Substitute the first character of both strings, so M[1][1] = min(M[0][1], M[1][0]) + 1.
As we move further into the matrix, we compare each character pair and choose the minimum edit operation from the previous cell and the current cell.

Now, let's dive into some code examples!

Code Example 1: Python Implementation

python

def levenshtein_distance(s1, s2):
    if len(s1) == 0 or len(s2) == 0:
        return len(s1) + len(s2)

    matrix = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

    for i in range(len(s1) + 1):
        matrix[i][0] = i

    for j in range(len(s2) + 1):
        matrix[0][j] = j

    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                matrix[i][j] = matrix[i - 1][j - 1]
            else:
                matrix[i][j] = min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + 1)

    return matrix[len(s1)][len(s2)]

Code Example 2: JavaScript Implementation

javascript

function levenshteinDistance(s1, s2) {
    if (!s1 || !s2) return s1 ? s1.length + s2.length : s2.length + s1.length;

    const matrix = Array.from({ length: s1.length + 1 }, () =>
        Array(s2.length + 1).fill(0)
    );

    for (let i = 0; i <= s1.length; i++) matrix[i][0] = i;
    for (let j = 0; j <= s2.length; j++) matrix[0][j] = j;

    for (let i = 1; i <= s1.length; i++) {
        for (let j = 1; j <= s2.length; j++) {
            matrix[i][j] = s1[i - 1] === s2[j - 1]
                ? matrix[i - 1][j - 1]
                : Math.min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + 1);
        }
    }

    return matrix[s1.length][s2.length];
}

Quiz

🎯 Keep practicing and honing your skills! You're on your way to mastering Edit Distance, a fundamental concept in the field of data structures and algorithms.

Happy coding! 🚀