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 FastAPI, WebSocket, WebSocketDisconnect
 
app = FastAPI()
 

Building a WebSocket chat with FastAPI

websockets broadcast connection-management
Intermediate 9 steps
python 
import time
import uuid
 
from django.utils.deprecation import MiddlewareMixin

Attaching per-request context in Django

middleware request lifecycle multi-tenancy
Intermediate 7 steps
python 
import random
from typing import Iterator, List
 
 

How reservoir sampling picks k items

reservoir-sampling streaming randomness
Intermediate 5 steps
python 
import secrets
 
from django.contrib.auth import authenticate, login
from django.core.cache import cache

Two-factor login with OTP in Django

two-factor-auth one-time-passwords caching
Intermediate 9 steps
python 
import re
from functools import total_ordering
from typing import Optional
 

Parsing and comparing semantic versions

regex operator-overloading sorting
Intermediate 7 steps
python 
from typing import Any, Sequence, Mapping
 
 
def render_markdown_table(

Rendering an aligned Markdown table in Python

string formatting data transformation closures
Intermediate 8 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