python 45 lines · 9 steps

A spelling suggester with edit distance

A dictionary is indexed by word length so a cached Levenshtein distance only runs on plausibly close words.

Explained by highlit
Intermediate edit-distance dynamic-programming memoization indexing fuzzy-matching
1from functools import lru_cache
2 
3 
4class SpellingSuggester:
5 def __init__(self, dictionary):
6 self.words = set(dictionary)
7 self.by_length = {}
8 for word in self.words:
9 self.by_length.setdefault(len(word), []).append(word)
10 
11 def suggest(self, term, max_suggestions=5, max_distance=2):
12 term = term.lower()
13 if term in self.words:
14 return [term]
15 
16 candidates = []
17 for length in range(len(term) - max_distance, len(term) + max_distance + 1):
18 for word in self.by_length.get(length, ()):
19 distance = self._edit_distance(term, word)
20 if distance <= max_distance:
21 candidates.append((distance, word))
22 
23 candidates.sort(key=lambda pair: (pair[0], pair[1]))
24 return [word for _, word in candidates[:max_suggestions]]
25 
26 @staticmethod
27 @lru_cache(maxsize=100_000)
28 def _edit_distance(a, b):
29 if not a:
30 return len(b)
31 if not b:
32 return len(a)
33 
34 previous = list(range(len(b) + 1))
35 for i, ca in enumerate(a, start=1):
36 current = [i]
37 for j, cb in enumerate(b, start=1):
38 cost = 0 if ca == cb else 1
39 current.append(min(
40 previous[j] + 1,
41 current[j - 1] + 1,
42 previous[j - 1] + cost,
43 ))
44 previous = current
45 return previous[-1]
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Bucketing candidates by length prunes the search space before running the expensive distance function.
  2. 2Levenshtein distance is a classic dynamic-programming problem solvable with two rolling rows instead of a full matrix.
  3. 3Caching a pure function with lru_cache pays off when the same argument pairs recur across many lookups.

Related explainers

python 
from fastapi import APIRouter, BackgroundTasks, Depends, HTTPException, status
from pydantic import BaseModel, EmailStr
from sqlalchemy.orm import Session
 

Building a signup endpoint in FastAPI

dependency-injection request-validation background-tasks
Intermediate 8 steps
python 
from django import forms
from django.utils import timezone
 
from .models import Reservation

Multi-field validation in a Django ModelForm

form validation cross-field validation modelform
Intermediate 7 steps
python 
from django import template
from django.urls import reverse, NoReverseMatch
from django.utils.html import format_html
 

Active nav-link template tags in Django

template tags url routing active state
Intermediate 7 steps
python 
from functools import wraps
import asyncio
 
from fastapi import APIRouter, FastAPI, Request

Per-route request timeouts in FastAPI

decorators async timeouts
Intermediate 6 steps
python 
import os
from pathlib import Path
 
BASE_DIR = Path(__file__).resolve().parent.parent.parent

How a Django settings module is wired

configuration environment-variables middleware
Intermediate 8 steps
python 
def is_valid_card_number(number: str) -> bool:
    digits = [int(c) for c in number if c.isdigit()]
 
    if len(digits) < 13 or len(digits) > 19:

Validating card numbers with the Luhn check

checksum validation luhn-algorithm
Intermediate 6 steps

Share this explainer

Here's the card — post it anywhere.

A spelling suggester with edit distance — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code