Implementing Levenshtein Distance for Vendor Name Matching

This page solves one concrete scenario: a bank-statement descriptor and an ERP vendor master record refer to the same supplier, but a deterministic join fails because the strings differ by truncation, a legal-entity suffix (LLC, GMBH), or an OCR artefact. The fix is to score the two strings with Levenshtein edit distance — the minimum count of single-character insertions, deletions, and substitutions needed to turn one into the other — and confirm the pair only when that score, combined with amount and date gates, clears a calibrated threshold. This stage runs strictly after deterministic matching: it belongs to the Fuzzy String Matching Techniques layer of the broader Transaction Matching Algorithms & Logic cascade, and it is invoked only on the residue that survives Exact Match & Hash Comparison.

Prerequisites checklist

Before this matcher executes, the upstream pipeline must have produced the following state:

Records are already normalised to a common schema (vendor name as UTF-8 str, amount as Decimal, posting date as date).
The deterministic gate has run and emitted a residue of unmatched records — fuzzy scoring never touches a record an exact hash already reconciled.
rapidfuzz>=3.0 is installed (pip install rapidfuzz); it provides a C-accelerated Levenshtein.distance.
A structured audit logger named reconciliation.audit is configured so every match decision emits trace_id, source_hash, and match_decision.
Amount-variance and date-window values are available per candidate pair, computed by the Date-Window & Amount Tolerance Rules stage.

Step-by-step implementation

Step 1 — Normalise both strings before measuring

Raw descriptors carry noise that inflates edit distance: punctuation, casing, and corporate suffixes. Strip them first so the distance reflects the meaningful divergence, not formatting. Removing LLC/INC/CORP/LTD is what eliminates the most common class of false negatives.

python

import re

_SUFFIXES = ["LLC", "INC", "CORP", "LTD", "CO", "GMBH", "AG"]
_SUFFIX_PATTERN = re.compile(rf"\b(?:{'|'.join(_SUFFIXES)})\b", re.IGNORECASE)
_PUNCT_PATTERN = re.compile(r"[^\w\s]")

def normalize(text: str) -> str:
    text = _PUNCT_PATTERN.sub("", text).strip().upper()
    return _SUFFIX_PATTERN.sub("", text).strip()

Step 2 — Compute distance and a length-normalised similarity

A raw edit distance of 2 means very different things for "IBM" versus "INTERNATIONAL BUSINESS MACHINES". Always normalise the integer distance into a 0.0–1.0 confidence score against the longer of the two strings, and apply a length-adaptive ceiling so short names are held to a stricter standard.

python

from rapidfuzz.distance import Levenshtein

def score(ref: str, target: str) -> tuple[int, float]:
    ref_n, tgt_n = normalize(ref), normalize(target)
    if not ref_n or not tgt_n:
        return 0, 0.0

    raw_dist = Levenshtein.distance(ref_n, tgt_n)
    max_len = max(len(ref_n), len(tgt_n))
    # Short names (<8 chars) tolerate at most 1 edit; longer names tolerate 25%.
    max_allowed = 1 if max_len < 8 else int(max_len * 0.25)
    if raw_dist > max_allowed:
        return raw_dist, 0.0

    similarity = 1.0 - (raw_dist / max_len)
    return raw_dist, similarity

The integer returned by Levenshtein.distance is the bottom-right cell of a dynamic-programming matrix that fills the cheapest edit path between the two strings. The diagram below traces it for a one-character OCR slip — ACME against ACNE — where the only non-zero step is the M→N substitution, so the final distance is 1.

Step 3 — Gate the match on similarity, amount, and date together

A string match is never sufficient on its own. The same supplier name can appear on transactions that are months and thousands of dollars apart. Confirm a pair only when the normalised similarity clears 0.72 and the amount and date already fall inside tolerance. Every decision emits a structured audit record.

python

import hashlib
import logging
from typing import Optional

logger = logging.getLogger("reconciliation.audit")

def evaluate_match(
    trace_id: str,
    ref_name: str,
    tgt_name: str,
    amount_diff_pct: float,
    date_window_days: int,
) -> Optional[dict]:
    raw_dist, similarity = score(ref_name, tgt_name)

    if similarity < 0.72:
        return None
    if abs(amount_diff_pct) > 0.0005 or date_window_days > 3:
        return None

    decision = {
        "trace_id": trace_id,
        "source_hash": hashlib.sha256(ref_name.encode()).hexdigest()[:12],
        "target_hash": hashlib.sha256(tgt_name.encode()).hexdigest()[:12],
        "raw_distance": raw_dist,
        "normalized_score": round(similarity, 4),
        "match_decision": "CONFIRMED",
    }
    logger.info("FuzzyMatchAudit", extra=decision)
    return decision

Step 4 — Break ties deterministically

Fuzzy scoring is inherently ambiguous: one descriptor may align with several vendor records at similar scores. To keep the ledger auditable, never auto-post when two candidates are too close. Apply a fixed hierarchy — highest similarity, then most recent historical posting frequency, then an exact suffix match on the routing/account number — and route to manual review when the top two differ by < 0.03.

python

def select_candidate(candidates: list[dict]) -> dict:
    ranked = sorted(candidates, key=lambda c: c["normalized_score"], reverse=True)
    if len(ranked) >= 2 and ranked[0]["normalized_score"] - ranked[1]["normalized_score"] < 0.03:
        top = ranked[0]
        logger.info(
            "FuzzyMatchAudit",
            extra={
                "trace_id": top["trace_id"],
                "source_hash": top["source_hash"],
                "match_decision": "AMBIGUOUS_REVIEW",
            },
        )
        return {**top, "match_decision": "AMBIGUOUS_REVIEW"}
    return ranked[0]

Step 5 — Parallelise for batch close cycles

Month-end batches process millions of ledger lines, and Levenshtein.distance is CPU-bound. Offload scoring to a bounded ThreadPoolExecutor driven by asyncio so you saturate cores without exhausting database connection pools.

python

import asyncio
from concurrent.futures import ThreadPoolExecutor

async def process_batch(batch: list[dict], max_workers: int = 8) -> list[dict]:
    loop = asyncio.get_running_loop()
    with ThreadPoolExecutor(max_workers=max_workers) as pool:
        tasks = [
            loop.run_in_executor(
                pool,
                evaluate_match,
                item["trace_id"],
                item["ref_vendor"],
                item["tgt_vendor"],
                item["amount_diff_pct"],
                item["date_window_days"],
            )
            for item in batch
        ]
        return [r for r in await asyncio.gather(*tasks) if r is not None]

Configuration boundary table

Parameter	Default	Valid range	Notes
`min_similarity`	`0.72`	`0.60–0.90`	Lower admits more matches and more false positives; raise for high-value ledgers.
`short_name_len`	`8`	`5–12`	Names shorter than this fall under the strict edit ceiling.
`strict_distance`	`1`	`0–2`	Max edits allowed for short names. `0` forces exact match below `short_name_len`.
`length_ratio`	`0.25`	`0.10–0.40`	Edit ceiling for long names as a fraction of `max_len`.
`amount_tol_pct`	`0.0005`	`0.0–0.01`	Absolute amount variance gate (±0.05%); `0.0` demands an exact amount.
`date_window_days`	`3`	`0–7`	Business-day window around the posting date.
`tie_break_delta`	`0.03`	`0.01–0.10`	Minimum score gap between top two candidates before auto-posting.
`max_workers`	`8`	`1–32`	Thread pool size; cap below your DB connection pool.

Verification and testing

Confirm the implementation against a small fixture before pointing it at a live feed. The fixture pairs known descriptors with expected outcomes so you can assert both confirmed matches and correctly rejected ones.

python

FIXTURE = [
    # (ref, target, amount_diff_pct, date_window_days, expect_match)
    ("ACME WIDGETS LLC", "ACME WIDGETS", 0.0001, 1, True),     # suffix only
    ("ACME WIDGETS LLC", "ACNE WIDGETS", 0.0001, 1, True),     # 1-char OCR slip
    ("IBM", "IBN", 0.0000, 0, False),                          # short name, strict
    ("ACME WIDGETS LLC", "GLOBEX TRADING", 0.0001, 1, False),  # different vendor
    ("ACME WIDGETS LLC", "ACME WIDGETS", 0.0200, 1, False),    # amount out of tolerance
]

def test_fixture() -> None:
    for ref, tgt, amt, days, expect in FIXTURE:
        result = evaluate_match("test-trace", ref, tgt, amt, days)
        matched = result is not None
        assert matched == expect, f"{ref!r} vs {tgt!r}: got {matched}, want {expect}"
    logger.info("FuzzyMatchAudit", extra={"trace_id": "test-trace",
                "source_hash": "fixture", "match_decision": "SELFTEST_PASS"})

test_fixture()

A green run proves four things at once: suffix stripping neutralises legal-entity noise, a single OCR substitution still clears the threshold, short names are protected by the strict ceiling, and the amount gate vetoes an otherwise perfect string match.

Troubleshooting

SHORT_NAME_FALSE_NEGATIVE — Legitimate three- and four-letter vendor codes (IBM, BP) never match. Root cause: strict_distance = 1 plus normalisation is too aggressive for tickers. Fix: maintain a small alias map for known short codes and bypass fuzzy scoring for them.
SUFFIX_OVER_STRIP — "CO-OP FOODS" collapses to "OP FOODS" because CO is stripped mid-name. Root cause: the suffix regex matches an internal word. Fix: anchor suffix removal to the end of the string (...\b$) rather than anywhere.
AMBIGUOUS_REVIEW flood — A large share of the batch lands in manual review. Root cause: vendor master contains near-duplicate records (the same supplier onboarded twice). Fix: deduplicate the master upstream; do not lower tie_break_delta to mask it.
DIACRITIC_MISMATCH — Cross-border names like "MÜLLER" vs "MULLER" score one edit per accented character. Root cause: no Unicode folding. Fix: NFKD-normalise and strip combining marks during Step 1 (see the Python unicodedata documentation).
THROUGHPUT_STALL — Batch latency spikes during close. Root cause: max_workers exceeds the DB connection pool, so threads block on connections. Fix: cap max_workers below the pool size and profile with cProfile; rapidfuzz sustains roughly 1–2M comparisons per second per worker.

Fuzzy String Matching Techniques — the parent stage covering Jaro-Winkler and token-set metrics alongside edit distance.
Exact Match & Hash Comparison — the deterministic gate that runs before any fuzzy scoring.
Date-Window & Amount Tolerance Rules — the temporal and monetary gates this matcher depends on.
Multi-Step Reconciliation Chains — how this stage is sequenced inside the full cascade.

Part of Fuzzy String Matching Techniques, within Transaction Matching Algorithms & Logic.