find_likely_duplicates(): compare within a postcode, not across the whole list
"""find_duplicate_customers.py
Flags likely-duplicate customer records for review before a mailing run.
Exact matching misses "J Smith" vs "John Smith" at the same postcode; a
full pairwise comparison across every record is O(n^2) and too slow past
a few thousand rows. This blocks records by postcode first (customers who
don't share a postcode are never compared), then only runs the more
expensive name-similarity check within each block.
"""
from __future__ import annotations
from collections import defaultdict
from dataclasses import dataclass
from difflib import SequenceMatcher
from itertools import combinations
NAME_SIMILARITY_THRESHOLD: float = 0.82
@dataclass(frozen=True)
class CustomerRecord:
customer_id: int
full_name: str
postcode: str
def normalise_name(full_name: str) -> str:
"""Lower-case and collapse whitespace so 'J. Smith' and 'j smith'
compare the same way, without touching the original record used for
display.
"""
return " ".join(full_name.lower().replace(".", "").split())
def block_by_postcode(customers: list[CustomerRecord]) -> dict[str, list[CustomerRecord]]:
"""Group customers by postcode. Two customers who don't share a
postcode are never compared at all, which is what keeps this fast:
the expensive step below only ever runs inside one block, not across
the whole table.
"""
blocks: dict[str, list[CustomerRecord]] = defaultdict(list)
for customer in customers:
blocks[customer.postcode].append(customer)
return blocks
def find_likely_duplicates(
customers: list[CustomerRecord],
) -> list[tuple[CustomerRecord, CustomerRecord, float]]:
"""Return every pair of customers judged a likely duplicate, as
(customer_a, customer_b, similarity_score), highest similarity first.
Only pairs within the same postcode block are ever compared, so the
total number of SequenceMatcher calls stays close to O(n), not
O(n^2), for any real customer list, where postcodes are reasonably
well spread.
"""
likely_duplicates: list[tuple[CustomerRecord, CustomerRecord, float]] = []
for postcode_block in block_by_postcode(customers).values():
if len(postcode_block) < 2:
continue # nothing in this postcode to compare against
for customer_a, customer_b in combinations(postcode_block, 2):
similarity_score = SequenceMatcher(
None,
normalise_name(customer_a.full_name),
normalise_name(customer_b.full_name),
).ratio()
if similarity_score >= NAME_SIMILARITY_THRESHOLD:
likely_duplicates.append((customer_a, customer_b, similarity_score))
likely_duplicates.sort(key=lambda match: match[2], reverse=True)
return likely_duplicates
block_by_postcode is the step that actually solves the scaling problem: it costs one pass over the whole customer list, and every comparison that follows happens only inside a block, never across the full table.
itertools.combinations then generates each pair within a block exactly once, so "Smith, J" is never compared against "Smith, J" a second time in reverse order, and normalise_name means a stray full stop or a difference in capitalisation never costs a match that should have been found.
The frozen dataclass gives each customer record a real, self-documenting type instead of a loose tuple or dict, so a typo in a field name fails immediately at the point it's written, not silently somewhere downstream.