python 41 lines · 9 steps

Building a fuzzy autocomplete matcher

A FuzzyMatcher blends prefix binary search with similarity scoring to rank suggestions for a query.

Explained by highlit
Intermediate fuzzy-matching binary-search ranking string-similarity
1from difflib import SequenceMatcher
2from bisect import bisect_left, bisect_right
3 
4 
5class FuzzyMatcher:
6 def __init__(self, candidates, min_score=0.45):
7 self._items = sorted(set(candidates), key=str.lower)
8 self._lowered = [c.lower() for c in self._items]
9 self.min_score = min_score
10 
11 def _prefix_window(self, query):
12 lo = bisect_left(self._lowered, query)
13 hi = bisect_right(self._lowered, query + "\uffff")
14 return set(range(lo, hi))
15 
16 def _score(self, query, candidate):
17 matcher = SequenceMatcher(None, query, candidate)
18 ratio = matcher.ratio()
19 if candidate.startswith(query):
20 ratio += 0.35
21 elif query in candidate:
22 ratio += 0.15
23 length_penalty = min(len(candidate), 30) / 300
24 return min(ratio - length_penalty, 1.0)
25 
26 def suggest(self, query, limit=8):
27 query = query.strip().lower()
28 if not query:
29 return []
30 
31 prefix_hits = self._prefix_window(query)
32 scored = []
33 for idx, candidate in enumerate(self._lowered):
34 if not prefix_hits and SequenceMatcher(None, query, candidate).quick_ratio() < self.min_score:
35 continue
36 score = self._score(query, candidate)
37 if idx in prefix_hits or score >= self.min_score:
38 scored.append((score, self._items[idx]))
39 
40 scored.sort(key=lambda pair: (-pair[0], pair[1].lower()))
41 return [item for _, item in scored[:limit]]
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Precomputing a sorted, lowercased index lets you binary-search a prefix window in log time.
  2. 2Combining a similarity ratio with prefix bonuses and a length penalty produces more intuitive rankings than raw ratios.
  3. 3A cheap quick_ratio filter prunes weak candidates before the more expensive full score runs.

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.

Building a fuzzy autocomplete matcher — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code