Levenshtein Distance

easyFREEMachine TranslationNLP 3: Advanced

Compute the Levenshtein (edit) distance between two strings. The edit distance is the minimum number of single-character operations (insertions, deletions, substitutions) needed to transform one string into another.

Implement levenshtein(s1, s2).

Input:

s1: First string
s2: Second string

Output: Return an integer (the edit distance).

Example

Input

kitten
sitting

Output

Reasoning

Inputs: s1 is kitten (6 letters), s2 is sitting (7 letters). Every insert, delete or substitute costs 1.
Line them up: keep the letters of kitten in order and set them against sitting, leaving the final g unmatched:

k i t t e n -
s i t t i n g

Four columns agree (i, t, t, n) and cost nothing. k vs s and e vs i are two substitutions; the gap opposite g is one insertion. Total: $1 + 1 + 1 = 3$ , the output 3.
Why not fewer: the lengths differ by $7 - 6 = 1$ , so at least one insertion is unavoidable. With only one, the six letters of kitten sit opposite six of the seven letters of sitting, and the best such pairing still leaves 2 mismatches. So 3 is the minimum.
Notice: the distance counts only the cheapest edit sequence. Identical strings score 0, and against an empty string the distance is the other string's length (every character is inserted).

Constraints

Strings can be empty
Operations: insert, delete, substitute (each costs 1)
Output: Single integer

More from NLP 3: Advanced

Temperature Samplereasy ROUGE-1 Score Calculatoreasy Context Window Findereasy Keyword Answer Extractoreasy Word-Level Translatoreasy

Concept primer

Background Knowledge

The Levenshtein Distance is a measure of the minimum number of single-character operations (insertions, deletions, substitutions) needed to transform one string into another. This concept is fundamental in Natural Language Processing (NLP) and Machine Translation, as it helps in evaluating the similarity between two strings. The Levenshtein Distance is named after Vladimir Levenshtein, who considered this distance in 1965.

The key concept here is edit operations. There are three types of edit operations:

Insertion: Adding a character to the first string to make it more similar to the second string.
Deletion: Removing a character from the first string to make it more similar to the second string.
Substitution: Replacing a character in the first string with a character from the second string to make them more similar.

Understanding the dynamic programming approach is crucial for solving this problem efficiently. Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem only once, and storing the solutions to subproblems to avoid redundant computation.

Algorithm/Approach

The general approach to solve this problem involves using dynamic programming to build a 2D matrix where each cell represents the minimum edit distance between substrings of the input strings. The algorithm pattern involves:

Initializing a matrix with dimensions $(m+1) \times (n+1)$ , where $m$ and $n$ are the lengths of the input strings.
Filling in the matrix by comparing characters from the input strings and considering the minimum edit distance for each substring.

Step-by-Step Strategy

To implement the solution:

Initialize a 2D matrix with dimensions $(m+1) \times (n+1)$ , where $m$ and $n$ are the lengths of the input strings.
Fill in the base cases for the matrix, where one of the strings is empty.
Iterate over the characters in the input strings, comparing each pair of characters and considering the minimum edit distance for each substring.
For each cell in the matrix, calculate the minimum edit distance by considering the minimum cost of insertion, deletion, and substitution.

Common Pitfalls

Things to watch out for:

Incorrectly initializing the base cases for the matrix.
Failing to consider all possible edit operations (insertion, deletion, substitution) when calculating the minimum edit distance.
Not using dynamic programming to store and reuse solutions to subproblems, leading to inefficient computation.

Time & Space Complexity

The expected time complexity for this problem is $O(mn)$ , where $m$ and $n$ are the lengths of the input strings. The space complexity is also $O(mn)$ , as we need to store the 2D matrix.

solution.py

Python 3.13

Test results