Deduplicating Addresses by Fuzzy Canonical Key

Address deduplication is the process of collapsing many spellings of the same physical location into a single record, and it is one of the highest-leverage steps in the caching, deduplication & spatial indexing stage of a normalization pipeline. The core idea is a fuzzy canonical key: a deterministic fingerprint derived from an address string such that every equivalent spelling produces the same fingerprint. Once 123 Main St, 123 Main Street, and 123 MAIN ST. all hash to one key, deduplication becomes a GROUP BY on that key, and the only records that need expensive comparison are the residual near-misses.

This guide covers the full workflow: a canonicalization pipeline that feeds a hash, a blocking strategy that keeps comparison off the O(n^2) cliff, fuzzy scoring for the records the key alone cannot merge, a survivorship rule that elects one golden record per cluster, and the persistence pattern that writes the key back so downstream joins and caches stay stable. Clean, parsed input is a prerequisite, so this stage sits directly downstream of core address parsing and standardization.

---

Prerequisites

Before running deduplication over a production table, confirm these are in place:

• Python 3.8+ with rapidfuzz, pandas, and unidecode installed
• Addresses already parsed into components (street number, street name, unit, city, state, postal code) — see core address parsing and standardization
• A decided grain: one record per building, per delivery point, or per parcel — this determines whether unit numbers survive canonicalization
• A frozen USPS abbreviation map (Publication 28 suffixes and directionals) checked into version control so keys are reproducible across runs
• A column to persist the canonical key back to, indexed for the GROUP BY and downstream joins

A subtle but critical rule: the canonicalizer must be deterministic and versioned. If the abbreviation map or normalization order changes, every previously computed key becomes stale. Treat the canonicalization function like a schema migration — bump a version tag when it changes and recompute keys in a controlled backfill.

---

The Canonicalization Pipeline

The canonical key is built by a fixed sequence of transforms. Order matters: normalizing Unicode before stripping punctuation prevents accented characters from being dropped, and expanding abbreviations before sorting tokens keeps St and Street from sorting into different positions.

Full-precision Unicode handling in step 2 is subtle enough to warrant its own treatment; Unicode and character normalization in Python covers the NFKC-versus-NFC decision and the transliteration edge cases that bite non-Latin input. The step-by-step key builder — including the compiled regex and blake2b hashing — is detailed in generating canonical address keys in Python.

---

Step-by-Step Deduplication Workflow

1. Parse raw input into components. Deduplication on unparsed free-text is fragile; component-level canonicalization is far more reliable.
2. Canonicalize each record into a normalized string and hash it into a canonical key.
3. Collapse exact matches with a GROUP BY on the key. This resolves the large majority of duplicates cheaply.
4. Block the survivors into candidate buckets by a coarse key (for example, postal code plus street initials).
5. Score residuals within each block using fuzzy scorers to catch typos and transpositions the exact key missed.
6. Cluster high-scoring pairs into connected components (a union-find over matched pairs).
7. Elect a survivor per cluster using a deterministic survivorship rule.
8. Persist the canonical key and the survivor’s record id onto every member row.

---

Primary Implementation: Canonical Key Builder + rapidfuzz Deduper

The row-level implementation below builds a canonical key, blocks records, and runs fuzzy scoring inside each block. It is deliberately explicit so each stage can be swapped independently.

from __future__ import annotations

import hashlib
import re
import unicodedata
from collections import defaultdict
from dataclasses import dataclass
from typing import Dict, Iterable, List, Tuple

from rapidfuzz import fuzz

# Compile all patterns once at module level.
_PUNCT = re.compile(r"[^\w\s]")
_WS = re.compile(r"\s+")
_UNIT = re.compile(r"\b(?:apt|apartment|ste|suite|unit|fl|floor|rm|room)\b.*$")

# USPS Publication 28 suffix and directional map (trimmed for illustration).
_ABBREV: Dict[str, str] = {
    "st": "street", "str": "street", "ave": "avenue", "av": "avenue",
    "blvd": "boulevard", "rd": "road", "dr": "drive", "ln": "lane",
    "ct": "court", "cir": "circle", "hwy": "highway", "pkwy": "parkway",
    "n": "north", "s": "south", "e": "east", "w": "west",
    "ne": "northeast", "nw": "northwest", "se": "southeast", "sw": "southwest",
}


def canonical_string(raw: str, drop_unit: bool = True) -> str:
    """Return a deterministic canonical form of an address string.

    Args:
        raw: A single-line address string.
        drop_unit: If True, remove secondary-unit designators (per-building grain).

    Returns:
        A lowercase, abbreviation-expanded, token-sorted canonical string.
    """
    text = unicodedata.normalize("NFKC", raw).lower()
    text = "".join(
        c for c in unicodedata.normalize("NFKD", text)
        if not unicodedata.combining(c)
    )
    if drop_unit:
        text = _UNIT.sub("", text)
    text = _PUNCT.sub(" ", text)
    text = _WS.sub(" ", text).strip()
    tokens = [_ABBREV.get(tok, tok) for tok in text.split()]
    tokens.sort()
    return " ".join(tokens)


def canonical_key(raw: str, drop_unit: bool = True) -> str:
    """Hash the canonical string into a stable 16-byte hex key."""
    canon = canonical_string(raw, drop_unit=drop_unit)
    return hashlib.blake2b(canon.encode("utf-8"), digest_size=16).hexdigest()


def blocking_key(postal: str, street: str) -> str:
    """Coarse bucket key: postal code + first 4 chars of canonical street."""
    street_slug = re.sub(r"\W", "", street.lower())[:4]
    return f"{postal.strip()}:{street_slug}"


@dataclass
class Record:
    rid: int
    raw: str
    postal: str


def dedupe(
    records: Iterable[Record],
    threshold: float = 90.0,
) -> Dict[int, int]:
    """Map each record id to a survivor id via canonical key + fuzzy scoring.

    Args:
        records: Iterable of Record objects.
        threshold: Minimum token_sort_ratio (0-100) to merge residuals.

    Returns:
        Dict mapping record id -> elected survivor id.
    """
    blocks: Dict[str, List[Record]] = defaultdict(list)
    canon: Dict[int, str] = {}
    for rec in records:
        canon[rec.rid] = canonical_string(rec.raw)
        key = blocking_key(rec.postal, canon[rec.rid])
        blocks[key].append(rec)

    parent: Dict[int, int] = {}

    def find(x: int) -> int:
        parent.setdefault(x, x)
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a: int, b: int) -> None:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[min(ra, rb)] = parent[max(ra, rb)] = min(ra, rb)

    for bucket in blocks.values():
        for i in range(len(bucket)):
            find(bucket[i].rid)
            for j in range(i + 1, len(bucket)):
                score = fuzz.token_sort_ratio(
                    canon[bucket[i].rid], canon[bucket[j].rid]
                )
                if score >= threshold:
                    union(bucket[i].rid, bucket[j].rid)

    return {rid: find(rid) for rid in parent}

The union-find (disjoint set) structure is what turns a set of matched pairs into clusters. Two records that never scored against each other directly still merge if a chain of high-scoring pairs connects them — for example, A↔B and B↔C imply A, B, and C are one cluster even if A and C look distant.

Vectorized pandas variant

For batch tables, the exact-key collapse should be a vectorized groupby, and only the residual buckets need Python-level scoring. The pattern below computes keys column-wise, resolves all exact duplicates with a single groupby, then hands only the ambiguous blocks to fuzzy scoring.

import pandas as pd


def add_canonical_columns(df: pd.DataFrame, addr_col: str, postal_col: str) -> pd.DataFrame:
    """Attach canonical string, canonical key, and blocking key columns."""
    out = df.copy()
    out["_canon"] = out[addr_col].map(canonical_string)
    out["_key"] = out["_canon"].map(
        lambda c: hashlib.blake2b(c.encode("utf-8"), digest_size=16).hexdigest()
    )
    out["_block"] = [
        blocking_key(p, c) for p, c in zip(out[postal_col], out["_canon"])
    ]
    return out


def collapse_exact(df: pd.DataFrame) -> pd.DataFrame:
    """Elect one survivor per exact canonical key (most complete record wins)."""
    out = df.copy()
    # Completeness score: count of non-null fields (survivorship input).
    out["_completeness"] = out.notna().sum(axis=1)
    out = out.sort_values("_completeness", ascending=False)
    survivors = out.groupby("_key", as_index=False).first()
    return survivors

Running the vectorized groupby first is the single biggest performance win: on typical address tables it resolves 70-95% of duplicates before a single fuzzy comparison runs, leaving only genuine near-misses for the rapidfuzz scoring pass.

---

Choosing a Survivorship Rule

Once records are clustered, exactly one must be elected as the golden record. The rule must be deterministic so reprocessing is idempotent.

A composite rule is common in practice: sort by source priority, then completeness, then recency, and take the first row. Whatever the rule, tie-break on the record id so the outcome is fully deterministic even when two records score identically.

---

Edge Cases

Unit and Suite Numbers

Whether 123 Main St Apt 4 and 123 Main St Apt 9 are duplicates depends entirely on grain. For a per-building rollup, drop the unit before hashing (the drop_unit=True path above). For a per-delivery-point grain, keep the unit as a discriminating token — but normalize its spelling first, since Apt, Apartment, #, and Unit all denote the same thing. Never let raw unit spelling leak into the key, or Apt 4 and # 4 will falsely split.

PO Boxes and Rural Routes

PO Boxes and rural routes have no street geometry, so street-token sorting produces useless keys. Detect them before canonicalization and route them to a dedicated key scheme: pobox:{zip}:{box_number}. Mixing PO-box records into street-based blocking pollutes buckets and inflates false-match rates.

Transposed Tokens

123 Main St and Main St 123 sort to the same token multiset, so token-sorted canonicalization already merges them — that is the deliberate benefit of sorting. But 123 Main St versus 132 Main St is a genuine typo in the house number, not a transposition; token sorting will not merge them, and it should not. Guard against merging distinct house numbers by keeping the street number as its own weighted comparison rather than folding it into the general token score.

Directional Ambiguity

N Main St and Main St N may be the same street or two different streets depending on the municipality’s grid convention. Directional expansion (n → north) plus token sorting collapses them; if your city genuinely distinguishes them, exclude directionals from the sort and compare them positionally instead.

---

Performance & Scaling

Blocking strategy is the dominant factor in both speed and recall. A blocking key that is too coarse creates huge buckets (slow); too fine and true duplicates land in different buckets (missed merges).

For a 10-million-row table, exact-key groupby should run in a single pass and eliminate most duplicates. The residual fuzzy pass then operates only inside blocks — with postal-plus-initials blocking, average bucket sizes stay in the tens, so total comparisons drop from ~10^14 (full Cartesian) to ~10^7. Precompute canonical strings once and reuse them for both the key hash and the fuzzy comparison; recomputing them per comparison is a common and costly mistake.

For repeat pipelines, cache the canonical-key-to-survivor mapping so re-runs skip re-scoring unchanged records — the same durable-cache pattern used in Redis and Postgres caching patterns.

---

Troubleshooting

Over-Merging Distinct Addresses

If two genuinely different addresses collapse to one key, the canonicalizer is dropping a discriminating token — usually the house number or a needed unit. Audit by sampling clusters with high internal string variance and check which token was lost. Raise the fuzzy threshold and keep the street number out of the general token pool.

Under-Merging Obvious Duplicates

If 123 Main St and 123 Main Street land in different clusters, the abbreviation map is missing an entry or normalization ran in the wrong order (punctuation stripped before Unicode folding). Log the canonical string for both records and diff them; the divergence point identifies the missing transform.

Blocking Buckets Are Enormous

A single ZIP with hundreds of thousands of rows produces a bucket that blows up the fuzzy pass. Add a second blocking dimension (street initials, or house-number parity) to split it, or switch that ZIP to a sorted-neighbourhood window.

Non-Deterministic Keys Across Runs

If the same input yields different keys on different runs, an unordered structure (a set or dict iteration) leaked into token ordering, or the abbreviation map changed unversioned. Sort tokens explicitly and pin the abbreviation map version in the key metadata.

---

FAQ

Why not just deduplicate on the raw address string?

Raw strings encode dozens of equivalent spellings for the same location. 123 Main St, 123 Main Street, and 123 MAIN ST. are byte-distinct but refer to one delivery point. A raw-string GROUP BY treats them as three records. A canonical key normalizes casing, Unicode, abbreviations, and token order first, so all three collapse to one bucket before any comparison happens.

Do I still need fuzzy matching if I have a canonical key?

Yes, for residual matches. A deterministic key catches formatting variance but not typos, OCR errors, or transposed tokens like 123 Main St versus 132 Main St. Fuzzy scoring within a blocking bucket recovers those pairs. The canonical key does the cheap, exact bulk of the work; fuzzy scoring handles the expensive remainder.

How do I keep deduplication from being O(n^2)?

Block first. Partition records into small buckets by a coarse key such as ZIP code plus the first characters of the street name, and only run pairwise fuzzy comparison inside each bucket. Blocking turns a single 10-million-row comparison into millions of tiny comparisons, cutting the pair count by three to four orders of magnitude.

What is a survivorship rule?

It is the deterministic policy that selects one golden record from a group of duplicate records. Common rules pick the most complete record (fewest null fields), the most recently verified, or the one with the highest geocoding confidence. The rule must be deterministic so that reprocessing the same cluster always elects the same survivor.

Should unit and suite numbers be part of the canonical key?

It depends on the grain you are deduplicating to. If you want one record per building, drop the secondary unit so Apt 4B and Apt 12 collapse together. If you want one record per mailable delivery point, keep the unit as a discriminating token. Decide the grain first, then configure the canonicalizer to match it.

---

Related

• Caching, Deduplication & Spatial Indexing — the parent section covering how caching, deduplication, and spatial indexing fit together in a normalization pipeline.
• Fuzzy address matching with rapidfuzz in Python — the scorer-by-scorer breakdown and process.cdist pattern for blocked residual matching.
• Generating canonical address keys in Python — the deterministic key builder with compiled regex, USPS abbreviation map, and blake2b hashing.
• Core address parsing & standardization — the upstream parsing stage that produces the clean components canonicalization consumes.
• Unicode and character normalization in Python — the NFKC and transliteration decisions that make step 2 of the canonicalization pipeline correct.
• Redis and Postgres caching patterns — how to cache the canonical-key-to-survivor mapping so repeat runs skip re-scoring.