Levenshtein distance: another approach

Imagine a world where we can effortlessly identify misspelled words, understand genetic similarities, or find approximate matches for patterns within a vast dataset. These are just a few real-life problems where the Levenshtein distance comes to the rescue. Remember that Levenshtein distance employs three fundamental transformation operations: insertion, deletion, and substitution, to determine the minimum edit distance between two strings.

We have already been introduced to the Levenshtein distance, a widely used measure of string similarity, using the naive recursive approach. While the naive recursive approach provided a very intuitive and straightforward method for calculating the Levenshtein distance, we quickly understood its drawbacks that we should consider. One major drawback was its inefficiency for long strings due to overlapping subproblems.

To overcome these challenges and optimize the Levenshtein distance calculation, we turn to dynamic programming. In this topic, we focus on the top-down dynamic programming approach, which efficiently eliminates redundant calculations caused by overlapping subproblems. It breaks down the problem into smaller subproblems, solves them recursively, and saves the solution of subproblems for future use.

Intuition

Let's first examine the intuition behind the top-down dynamic programming approach for finding the Levenshtein distance between the two input strings: $a$ and $b$.

Initially, a naive recursive approach might seem like a very intuitive, straightforward, and easy method for calculating the Levenshtein distance, which works well. However, it proves to be quite exhaustive. As the length of the input strings increases, the number of recursive calls and redundant computations grows exponentially. The end result? This inefficiency can lead to significant computational overhead and memory usage, making it impractical for lengthy strings.

Take a look at the following recursion tree of the naive recursive approach for calculating Levenshtein distance, that we observed in a previous topic. Here, $a$ = "bat" and $b$ = "bed".

The recursion tree highlights repetitive calculations using the same color. There are multiple evaluations of substring combinations of strings $a$ and $b$, leading to unnecessary redundant computations.

However, we can optimize these redundant recursive calls and avoid such inefficiencies. To achieve this optimization, we can implement a technique called memoization. Memoization enables us to store the results of previously computed sub-problems, allowing us to reuse these results and avoid redundant calculations.

By caching or memoizing the results of each sub-problem, the algorithm becomes more efficient. Before computing the result for a particular sub-problem, it checks if the result is already present in the cache. If so, it terminates the computation and directly retrieves the pre-computed result from the cache, eliminating the need for repeated evaluations.

This concept of memoization introduces us to a widely used programming paradigm: dynamic programming. In this topic, we utilize the top-down dynamic programming approach, also known as memoization, to efficiently solve the problem of Levenshtein distance. Let's take a closer look at this approach and its implementation.

Top-down dynamic programming approach

Let's consider two input strings, denoted as $a$ and $b$, with character indices $i$ and $j$, respectively. We can represent $a$ as $a=a_1...a_i...a_n$ and $b$ as $b=b_1...b_j...b_m$. Our goal is to determine the Levenshtein distance required to transform $a$ into $b$. This distance represents the minimum number of operations (deletion, insertion, or substitution) needed to make the two strings equal.

To accomplish this, we define a recursive function called minDistance(). This function calculates the Levenshtein distance for substrings of $a$ and $b$, using two indices $i$ and $j$ to track the current characters being compared at the moment.

The top-down dynamic programming approach is simply an extension of the naive recursive approach. In fact, it closely resembles the naive recursive approach, with only a few minor adjustments. This approach involves incorporating caching within the recursive function calls. To store the result of each sub-problem, we employ a data structure known as a memoization table or cache. By using this cache, we optimize the calculations by storing and reusing previously computed results.

By incorporating this caching technique, we significantly reduce redundant recursive calls. This makes the top-down dynamic programming approach more efficient and capable of handling larger inputs for calculating the Levenshtein distance between two strings.

Now, let's delve into the implementation steps of the top-down dynamic programming approach.

1. Caching mechanism:

   • In a recursive call with specific parameters (e.g. minDistance(a, b, i, j)), we store the result of the sub-problem with string $a$ ending at index $i$ and string $b$ ending at index $j$ in the cache.

   • Before computing the result of a sub-problem, we check if it already exists in the cache (e.g. memo[i][j]). If the result is cached, we directly retrieve it, avoiding redundant computations.

   • After computing the result of a sub-problem, we store the result in the cache for future use. So, when encountering the same sub-problem in subsequent recursive calls, we can quickly retrieve its result from the cache (e.g. memo[i][j]).

   Cache array (or memoization table)

   

   Cache often takes the form of a multi-dimensional array, and its dimensions are determined by the number of variable parameters passed in the recursive function. For instance, in the case of minDistance(a, b, i, j), we pass a total of 2 variable parameters, namely $i$ and $j$. Consequently, we utilize a 2-dimensional array as the cache. However, if we had only 1 variable parameter, we would use a 1-dimensional array as the cache.

   This insight usually emerges from solving numerous problems involving memoization. Nevertheless, even from a logical standpoint, it's quite understandable. Because we want to store the results for each combination of $i$ and $j$, as these indices represent the current characters being compared in strings $a$ and $b$ during the recursive process.

2. Base cases: We define the base cases for the recursive function:

   • If $a$ is empty, the edit distance equals the number of characters in $b$.

   • If $b$ is empty, the edit distance equals the number of characters in $a$.

3. Character comparison: When comparing characters at indices, $i$ and $j$, two possibilities arise:

   • If the characters match ($a_i$ $=$ $b_j$), we move to the next index without performing any operation.

   • If the characters don't match ($a_i$ $\neq$ $b_j$), we need to consider the three operations: deletion, insertion, and substitution.

4. Recurrence relations: The recurrence relation for each possible operation is as follows:

   Let's derive it using an example with actual strings. Say, $a$ = "bat" and $b$ = "bed".

   

   • Substitution: minDistance(a,b,i−1,j−1) + 1

   • Insertion: minDistance(a,b,i,j−1) + 1

   • Deletion: minDistance(a,b,i−1,j) + 1

5. Overall recurrence relation: The minimum Levenshtein distance is the minimum of the three operations mentioned above. We can write this in the form of pseudocode as:

   if a[i] == b[j]:
       return minDistance(a, b, i - 1, j - 1)
   
   if a[i] != b[j]:
       return min(
                 minDistance(a, b, i - 1, j - 1),
                 minDistance(a, b, i, j - 1),
                 minDistance(a, b, i - 1, j)
              ) + 1
   

By recursively applying these principles and considering all possible combinations, we can find the Levenshtein distance between $a$ and $b$ as shown using the following pseudocode:

// Example usage:
a = "bat"
b = "bed"
levenshteinDistance = minDistance(a, b)
print(levenshteinDistance)

function minDistance(a, b):
    n = length(a) // Get the length of string `a`
    m = length(b) // Get the length of string `b`
    
    // Create a `cache` or `memoization table`, of `integer` type initialized with `null` values
    memo = Integer(array[n + 1][m + 1])

    // Calling recursive method to calculate Levenshtein distance between strings `a` and `b`
    return calculateDistance(a, b, n, m, memo)

function calculateDistance(a, b, n, m, memo):    
    // Check if the result is already memoized
    if memo[n][m] is not null:
        return memo[n][m]

    // Base case: if `a` is empty, return the length of `b`
    if n == 0:
        return m
    
    // Base case: if `b` is empty, return the length of `a`
    if m == 0:
        return n
    
    // If the characters at the current indices are equal, no operation is needed
    if a[n - 1] == b[m - 1]:
        // Recursively call calculateDistance() method with updated indices
        memo[n][m] = calculateDistance(a, b, n - 1, m - 1, memo)
        return memo[n][m]
    else:
        // Try all three operations and choose their minimum
        // Insertion: decrement m
        insertOperation = calculateDistance(a, b, n, m - 1, memo)
        
        // Deletion: decrement n
        deleteOperation = calculateDistance(a, b, n - 1, m, memo)
        
        // Substitution: decrement both n and m
        replaceOperation = calculateDistance(a, b, n - 1, m - 1, memo)
        
        // Return the minimum of the three operations plus 1
        memo[n][m] = min(insertOperation, min(deleteOperation, replaceOperation)) + 1
        return memo[n][m]

Now, let's turn our attention to the recursion tree of the top-down dynamic programming approach for calculating the Levenshtein distance. Here, $a$ = "bat" and $b$ = "bed".

You'll notice that the algorithm efficiently avoids repetitive calculations (highlighted using the same color). Whenever the algorithm encounters a previously computed subproblem for a particular substring combination of strings $a$ and $b$, it retrieves the result directly from the cache. This way, it eliminates redundant computations. Observe that no further recursive calls were made from a previously computed subproblem. This optimization ensures that computations are performed only once, and the results are stored for future reference. The outcome? A highly efficient Levenshtein distance calculation.

Complexity analysis

Consider $n$ as the length of string $a$ and $m$ as the length of string $b$.

• Time complexity: The time complexity of the memoization approach is $O(n⋅m)$ because for every combination of string $a$ and string $b$, the result is computed only once and then stored in the memoization table. This optimization eliminates redundant calculations by reusing the previously computed results, significantly reducing the number of recursive calls.

• Space complexity: The space complexity is $O(n⋅m)$ due to the additional 2D array memo, of size $n \times m$. This memoization table is used to cache the results of previously computed sub-problems. Consequently, the algorithm consumes additional memory to store and retrieve these cached results, but it ensures efficient reuse of the computed values.

Conclusion

Let's recap the key points we've explored throughout this topic:

• Levenshtein distance quantifies string similarity by measuring the minimum editing operations needed to transform one string into another.
• The naive recursive approach for calculating the Levenshtein distance is a very intuitive and straightforward method, but it is inefficient for long strings due to overlapping subproblems.
• Using the top-down dynamic programming approach, also known as memoization, we can optimize the Levenshtein distance calculation, by avoiding redundant calculations.
• Using the top-down dynamic programming approach, the time and space complexity can be reduced to $O(n⋅m)$.