Tag Archives: levenshtein

Levenshtein Part 2: Dynamic Programming

Proceeding from the earlier post on the same topic, we have the following code for a Dynamic Programming bottom-up approach to the Levenshtein “Edit Distance” algorithm where all the weights are simply “1” for insert, delete, substitute operations. Note that this would be also referred to the “tabular” approach as well since we fill up a matrix as we go along.

In a later post, we would attempt to reduce the space requirement from O(m.n) to a constant. In another post, we would provide a way to configure the weights and thereby providing weighted edges to the DAG.

 

And the test code:

Levenshtein: elementary recursion – a gateway to DP

This is my first post on Levenshtein Algorithm: a way to calculate the edit distance between two strings. A way to calculate the cost to transmute a string1 to a string2.

The comments in the codebase are useful for comprehension on their own. I start with the recursing and building a matrix where the answer (the cost to transmute or convert str1 into str2) lies at index [m][n] for the first implementation. For the second case, the cost would be at index [0][0].

This is the gateway to elucidating DP through the implementation of this algorithm. We would implement in ways that classify as DP (both memoization and tabulation) as well as plain and simple recursion or iteration with no DP components. We start with vanilla recursion in the following codebase. Please review the comments in the codebase to understand why this is not DP. A future post would elucidate DP.

 

A snippet of the test code: