levinshtein_distance.py

"""
Spell Correction Using Levenshtein Distance Algorithm
=====================================================
To correct misspellings, a source string is tokenized by splitting it on whitespace and then normalized by lowercasing, removing punctuation and stop words, 
and optionally applying stemming or lemmatization. A dictionary of correct target terms is used as a reference for comparison.
K-grams (e.g., trigrams) of the misspelled term are compared with those of dictionary terms, and candidates with the highest overlap are ranked as the most similar.
The best match is then chosen using Levenshtein distance, which calculates the minimum number of edits needed to transform the source string 
into a target string. This is done using an m × n matrix comparing each character, and the final distance is found in the bottom-right cell.

What This Code Does:

This implementation demonstrates the core Levenshtein distance calculation for spell correction.
It compares the misspelled word "infoolmation" against the correct word "information" by:

1. Matrix Initialization: Creates an (m+1) × (n+1) matrix where m and n are the lengths of the source and target strings
2. Base Case Setup: Fills the first row and column with incremental values (0, 1, 2, 3...)
3. Dynamic Programming: For each cell, calculates the minimum cost among three operations:
   - Deletion (moving down in the matrix)
   - Insertion (moving right in the matrix)
   - Substitution (moving diagonally, with cost 0 for matching characters or 1 for mismatches)
4. Result Display: Uses pandas to create a readable matrix visualization showing the edit distances at each step

The final Levenshtein distance (found in the bottom-right cell) represents the minimum number of single-character edits needed to transform "infoolmation" into "information".
In this case, 1 deletion (an extra 'o') and 1 substitution ('l' to 'r') are required.
"""


import numpy as np
import pandas as pd


# Source (misspelled) and Target (correct)
source = "infoolmation"
target = "information"


# Initialize the matrix with dimensions (source_length + 1) x (target_length + 1)
# Extra row and column are needed for base cases (empty string comparisons)
rows = len(source) + 1
cols = len(target) + 1
D = np.zeros((rows, cols), dtype=int)


# Fill in base cases - these represent the cost of transforming empty string
# D[i][0] = i: cost to transform source[0:i] to empty string (i deletions)
# D[0][j] = j: cost to transform empty string to target[0:j] (j insertions)
for i in range(rows):
    D[i][0] = i
for j in range(cols):
    D[0][j] = j


# Dynamic programming: compute minimum edit distance for each substring
for i in range(1, rows):
    for j in range(1, cols):
        # Cost of substitution: 0 if characters match, 1 if they don't
        cost = 0 if source[i - 1] == target[j - 1] else 1
        
        # Take minimum of three possible operations:
        D[i][j] = min(
            D[i - 1][j] + 1,        # deletion: remove source[i-1], compare source[0:i-1] with target[0:j]
            D[i][j - 1] + 1,        # insertion: insert target[j-1], compare source[0:i] with target[0:j-1]
            D[i - 1][j - 1] + cost  # substitution: replace source[i-1] with target[j-1] (cost if different)
        )


# Create a DataFrame for easier viewing with character labels
labels_row = [''] + list(target)    # Column headers: empty string + each target character
labels_col = [''] + list(source)    # Row headers: empty string + each source character
df = pd.DataFrame(D, index=labels_col, columns=labels_row)
print("Levenshtein Distance Matrix:")
print(df)
print(f"\nMinimum edit distance between '{source}' and '{target}': {D[rows-1][cols-1]}")