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 copy import deepcopy
from typing import Any, Mapping
 
 

How a recursive deep merge works in Python

recursion immutability dictionaries
Intermediate 6 steps
python 
import secrets
from datetime import datetime, timedelta, timezone
 
from fastapi import APIRouter, Cookie, Depends, HTTPException, Response, status

Cookie session auth in FastAPI

session-authentication cookies dependency-injection
Intermediate 8 steps
python 
from fastapi import APIRouter, Depends, HTTPException, status
from fastapi.security import OAuth2PasswordBearer
from jose import JWTError, jwt
from sqlalchemy.orm import Session

Chaining auth dependencies in FastAPI

dependency-injection jwt-authentication authorization
Intermediate 8 steps
python 
from flask import Blueprint, request, url_for, jsonify, abort
from flask.views import MethodView
 
from .models import Article, db

Building a paginated JSON API with Flask MethodView

rest-api pagination class-based-views
Intermediate 10 steps
python 
import threading
from functools import wraps
 
 

A thread-safe debounce decorator in Python

decorators debounce threading
Advanced 6 steps
python 
from urllib.parse import urlparse, parse_qs
from dataclasses import dataclass, field
 
ALLOWED_SCHEMES = {"http", "https"}

Validating URLs into a safe endpoint in Python

input validation url parsing dataclasses
Intermediate 7 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