Why Edit distance (Levenshtein) in NLP? - Purpose & Use Cases

The Big Idea

What if you could instantly know how close two sentences really are without reading every letter?

The Scenario

Imagine you have two long sentences and you want to find out how different they are by counting the changes needed to turn one into the other.

Doing this by hand means checking every letter, word, or space one by one.

The Problem

Manually comparing texts is slow and tiring.

It's easy to miss differences or count wrong, especially with long or similar sentences.

This leads to mistakes and wastes a lot of time.

The Solution

Edit distance (Levenshtein) quickly calculates the smallest number of changes needed to turn one text into another.

It counts insertions, deletions, and substitutions automatically, saving time and avoiding errors.

Before vs After

✗ Before

count = 0
for i in range(min(len(text1), len(text2))):
    if text1[i] != text2[i]:
        count += 1
count += abs(len(text1) - len(text2))

✓ After

distance = levenshtein(text1, text2)

What It Enables

It enables fast and accurate measurement of how similar or different two texts are, powering spell checkers, search engines, and language tools.

Real Life Example

When you type a word wrong, your phone suggests the correct spelling by finding words with a small edit distance from what you typed.

Key Takeaways

Manual text comparison is slow and error-prone.

Edit distance automates counting changes needed between texts.

This helps many language and search applications work better and faster.

Practice

1. What does the edit distance (Levenshtein distance) between two words measure?

easy

A. The length difference between two words

B. The minimum number of single-character edits to change one word into the other

C. The number of common letters between two words

D. The number of vowels in both words combined

Solution

1. Step 1: Understand the definition of edit distance

   Edit distance counts how many changes like insertions, deletions, or substitutions are needed to convert one word into another.

2. Step 2: Compare options with the definition

   Only The minimum number of single-character edits to change one word into the other correctly describes this minimum number of single-character edits.

3. Final Answer:

   The minimum number of single-character edits to change one word into the other -> Option B

4. Quick Check:

   Edit distance = minimum edits [OK]

Hint: Edit distance = smallest edits to match words [OK]

Common Mistakes:

• Confusing edit distance with common letters count
• Thinking it measures length difference only
• Mixing up vowels or letter counts

2. Which of the following Python code snippets correctly initializes a 2D table for computing edit distance between strings s1 and s2 of lengths m and n?

easy

A. table = [[0] * (n + 1) for _ in range(m + 1)]

B. table = [[0] * m for _ in range(n)]

C. table = [[0] * (m + 1) for _ in range(n + 1)]

D. table = [[0] * n for _ in range(m)]

Solution

1. Step 1: Recall table size for edit distance

   The table size must be (m+1) rows and (n+1) columns to include empty prefixes of both strings.

2. Step 2: Match code to correct dimensions

   table = [[0] * (n + 1) for _ in range(m + 1)] creates a list with (m+1) rows and each row has (n+1) zeros, which is correct.

3. Final Answer:

   table = [[0] * (n + 1) for _ in range(m + 1)] -> Option A

4. Quick Check:

   Table size = (m+1) x (n+1) [OK]

Hint: Table size = (len(s1)+1) x (len(s2)+1) [OK]

Common Mistakes:

• Swapping m and n in dimensions
• Forgetting to add 1 for empty string prefix
• Using wrong list comprehension order

3. What is the edit distance between the words "kitten" and "sitting"?

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Identify edits from "kitten" to "sitting"

   Changes: substitute 'k' -> 's', substitute 'e' -> 'i', insert 'g' at the end.

2. Step 2: Count total edits

   There are 3 edits: 2 substitutions and 1 insertion.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Edits counted = 3 [OK]

Hint: Count substitutions + insertions + deletions [OK]

Common Mistakes:

• Counting only substitutions
• Missing the final insertion
• Confusing similar letters as no change

4. Consider this Python code snippet for edit distance calculation. What is the error?

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        table[i][0] = i
    for j in range(n + 1):
        table[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i] == s2[j]:
                cost = 0
            else:
                cost = 1
            table[i][j] = min(table[i-1][j] + 1, table[i][j-1] + 1, table[i-1][j-1] + cost)
    return table[m][n]

medium

A. The return statement should be table[0][0]

B. The table initialization is incorrect

C. The cost should be 2 when characters differ

D. Indexing s1[i] and s2[j] causes an off-by-one error

Solution

1. Step 1: Check string indexing in loops

   Strings are 0-indexed, but loops start at 1, so s1[i] and s2[j] skip first character and cause index errors.

2. Step 2: Correct indexing

   Use s1[i-1] and s2[j-1] to access correct characters for comparison.

3. Final Answer:

   Indexing s1[i] and s2[j] causes an off-by-one error -> Option D

4. Quick Check:

   Indexing error = s1[i-1], s2[j-1] needed [OK]

Hint: Remember strings start at index 0, loops at 1 need offset [OK]

Common Mistakes:

• Using s1[i] instead of s1[i-1]
• Thinking cost must be 2 for difference
• Returning wrong table cell

5. You want to find the closest word to "flame" from the list ["frame", "flan", "flame", "blame"] using edit distance. Which word will the algorithm select as closest?

hard

A. "flame"

B. "frame"

C. "blame"

D. "flan"

Solution

1. Step 1: Calculate edit distances to each word

   Distances: "flame" to "frame" = 1 (substitute 'l'->'r'), to "flan" = 2 (delete 'm' and 'e'), to "blame" = 1 (substitute 'f'->'b'), to "flame" = 0 (same word).

2. Step 2: Identify minimum distance

   The smallest distance is 0 for "flame" itself, meaning exact match.

3. Final Answer:

   "flame" -> Option A

4. Quick Check:

   Exact match distance = 0 [OK]

Hint: Exact match has zero edit distance [OK]

Common Mistakes:

• Choosing word with one letter difference over exact match
• Ignoring exact matches
• Miscounting substitutions