如何避免姓名相似度匹配中的O(n²)时间复杂度？

Great question—dealing with fuzzy name duplicates like the ones you listed (Tom Riddle vs Tom M. Riddle vs tom riddle) is such a common data cleaning headache, and you’re totally right that brute-force pairwise Levenshtein comparisons get impossible fast with large datasets. Let’s break down practical, actionable ways to avoid that O(n²) complexity:

Before even thinking about similarity checks, standardize the names to eliminate obvious differences that don’t change the identity. For your examples, this would fix most of the low-hanging fruit:

• Normalize case: Convert all names to lowercase (tom riddle) or title case—no more worrying about Tom vs tom.
• Strip suffixes/titles: Use regex to remove things like PhD., MD, Jr., etc. For your example, Tom Riddle, PhD. becomes Tom Riddle. A quick regex snippet for this could be something like re.sub(r'\s*(PhD\.|MD|Jr\.|Sr\.|,\s*PhD\.)$', '', name).
• Handle middle names: Either expand known abbreviations (if you have a lookup table) or strip middle initials entirely (e.g., Tom M. Riddle → Tom Riddle)—whichever makes sense for your use case.
• Remove special characters: Ditch commas, periods, and extra spaces to clean up the strings.

This is the biggest win for cutting complexity. Instead of comparing every name to every other name, split your dataset into "blocks" of entries that are already likely to be duplicates, then only run similarity checks within each block. For names, common blocking strategies include:

• Last name + first initial: Group all entries where the standardized last name is riddle and first name starts with t—this puts all your Tom Riddle variants in one block, and you only compare within that small group.
• Full standardized last name: If last names are reliable, group everyone with the same last name. For larger datasets, you can even combine this with first name prefixes (e.g., first 3 characters of the first name) to make blocks smaller.
• N-gram blocking: Split names into character n-grams (e.g., 2-grams for tom riddle are to, om, m , r, ri, id, dd, dl, le) and group entries that share a certain number of n-grams. This catches cases where last names might be slightly misspelled, but still similar.

With blocking, your complexity drops from O(n²) to O(k * m²), where k is the number of blocks and m is the average size of each block. If you split your data well, m will be way smaller than n.

If blocking isn’t enough (or you need to catch cross-block duplicates), use algorithms designed to find similar items without pairwise comparisons:

• Locality Sensitive Hashing (LSH): LSH hashes similar strings into the same buckets. For names, you can generate n-grams of the standardized string, hash each n-gram, and then group entries that share multiple hashes. This way, you only compare entries in the same hash bucket, avoiding full pairwise checks.
• Vector-based ANN: Convert each name into a numerical vector (using character embeddings, for example) and use an ANN library to find vectors that are close to each other. Libraries like FAISS or Annoy can do this in O(n log n) time, which is way better than O(n²) for large datasets.

For name data, you can often write targeted rules to catch duplicates without full similarity checks. For your examples:

• If two entries have the same standardized last name, and their first names have a Levenshtein distance ≤ 2 (or are exact matches after stripping middle initials), mark them as duplicates.
• If one entry has a middle initial and the other doesn’t, but the rest of the name is identical, flag them as duplicates.

These rules are fast and can handle most of the common cases you’re seeing, reducing the number of similarity checks you need to run.

Putting it all together: Start with preprocessing to eliminate trivial variations, use blocking to narrow down your comparison pool, then use either rule-based checks or targeted similarity algorithms within blocks. This approach keeps your runtime manageable while still catching those tricky fuzzy duplicates.

内容的提问来源于stack exchange，提问作者boysimple dimple