Edit distance (Levenshtein) in NLP - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein distance function

What is the output of this Python function call?

```python def levenshtein(s1, s2): if len(s1) < len(s2): return levenshtein(s2, s1) if len(s2) == 0: return len(s1) previous_row = range(len(s2) + 1) for i, c1 in enumerate(s1): current_row = [i + 1] for j, c2 in enumerate(s2): insertions = previous_row[j + 1] + 1 deletions = current_row[j] + 1 substitutions = previous_row[j] + (c1 != c2) current_row.append(min(insertions, deletions, substitutions)) previous_row = current_row return previous_row[-1] print(levenshtein("kitten", "sitting")) ```

NLP

def levenshtein(s1, s2):
    if len(s1) < len(s2):
        return levenshtein(s2, s1)
    if len(s2) == 0:
        return len(s1)
    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    return previous_row[-1]

print(levenshtein("kitten", "sitting"))

A 4

B 6

C 5

D 3

💡 Hint

Count the minimum edits needed to change 'kitten' into 'sitting'.

The Levenshtein distance between 'kitten' and 'sitting' is 3: substitute 'k'->'s', substitute 'e'->'i', insert 'g' at the end.

🧠 Conceptual

intermediate

Understanding Levenshtein distance properties

Which of the following statements about Levenshtein distance is TRUE?

A Levenshtein distance is always equal to the length difference between two strings.

B Levenshtein distance is a measure of semantic similarity between words.

C Levenshtein distance can only be zero or positive, never negative.

D Levenshtein distance counts only substitutions, ignoring insertions and deletions.

💡 Hint

Think about what the distance measures and if it can be negative.

Levenshtein distance counts the minimum number of insertions, deletions, and substitutions to transform one string into another, so it is always zero or positive.

❓ Hyperparameter

advanced

Choosing weights in weighted Levenshtein distance

In a weighted Levenshtein distance, you assign different costs to insertions, deletions, and substitutions. If you want to penalize substitutions more than insertions and deletions, which weight setting is correct?

A Insertion=2, Deletion=2, Substitution=2

B Insertion=1, Deletion=1, Substitution=3

C Insertion=3, Deletion=3, Substitution=1

D Insertion=0, Deletion=0, Substitution=5

💡 Hint

Higher cost means more penalty.

To penalize substitutions more, assign a higher cost to substitutions than insertions or deletions.

🔧 Debug

advanced

Identify the error in Levenshtein distance code

What error will this code raise when called with levenshtein('a', 'b')?

```python def levenshtein(s1, s2): if len(s1) < len(s2): return levenshtein(s2, s1) if len(s2) == 0: return len(s1) previous_row = [0] * len(s2) for i, c1 in enumerate(s1): current_row = [i + 1] for j, c2 in enumerate(s2): insertions = previous_row[j + 1] + 1 deletions = current_row[j] + 1 substitutions = previous_row[j] + (c1 != c2) current_row.append(min(insertions, deletions, substitutions)) previous_row = current_row return previous_row[-1] ```

NLP

def levenshtein(s1, s2):
    if len(s1) < len(s2):
        return levenshtein(s2, s1)
    if len(s2) == 0:
        return len(s1)
    previous_row = [0] * len(s2)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    return previous_row[-1]

levenshtein('a', 'b')

A IndexError: list index out of range

B TypeError: unsupported operand type(s) for +: 'int' and 'str'

C Returns 0 incorrectly

D No error, returns 1

💡 Hint

Check the length of previous_row and how indexes are accessed.

previous_row is initialized with length len(s2), but code accesses previous_row[j + 1], which causes IndexError when j is last index.

❓ Model Choice

expert

Best model for approximate string matching using edit distance

You want to build a system that suggests corrections for misspelled words by finding dictionary words with smallest edit distance. Which model or approach is best suited for this task?

A Use a BK-tree data structure with Levenshtein distance for fast approximate matching

B Train a deep neural network to classify words as correct or incorrect spellings

C Use a bag-of-words model with cosine similarity to find closest words

D Apply k-means clustering on word embeddings to group similar words

💡 Hint

Think about efficient search for words within a certain edit distance.

BK-trees are designed for efficient approximate matching using edit distance metrics, making them ideal for spell correction tasks.