Fuzzy Matching

The Levenshtein Distance is a foundational metric that calculates the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. It provides a raw, character-level measure of dissimilarity.

• Mechanism: Computes a matrix where cell (i, j) holds the edit distance between the first i characters of string A and the first j characters of string B.
• Use Case: Ideal for typo correction and matching records with minor spelling variations (e.g., 'Jon' vs 'John', 'Kitten' vs 'Sitting').
• Limitation: Does not account for word transpositions; 'abc' to 'acb' requires two edits (delete 'b', insert 'b'), not one swap.

Jaro-Winkler Similarity is an algorithm optimized for matching person names and short strings. It favors strings that share a common prefix, making it highly effective for proper nouns.

• Jaro Component: Calculates similarity based on the number and order of matching characters, allowing for some transposition.
• Winkler Enhancement: Boosts the score for strings that start with the same characters (up to a prefix length of 4). This gives 'Martha' and 'Marhta' a higher similarity than a pure edit distance would.
• Typical Application: De-duplicating customer records, aligning author names in bibliographic databases, and U.S. Census data linkage.

This technique treats strings as vectors in a high-dimensional space based on character or word n-grams (contiguous subsequences of length n). Similarity is measured by the cosine of the angle between these vectors.

• Process: First, decompose strings into sets of n-grams (e.g., trigrams for 'apple': 'app', 'ppl', 'ple'). Then, vectorize and compute cosine similarity.
• Advantage: Robust to word reordering and minor local edits. 'The quick brown' and 'Brown quick the' have high cosine similarity.
• Common Use: Document similarity, plagiarism detection, and matching product descriptions where phrasing may vary.

Phonetic algorithms like Soundex, Metaphone, and Double Metaphone encode strings based on their English pronunciation. They are designed to match homophones—words that sound alike but are spelled differently.

• Soundex: Creates a 4-character code (one letter followed by three digits) representing the phonetic skeleton of a name. 'Robert' and 'Rupert' both encode to 'R163'.
• Metaphone/ Double Metaphone: More advanced than Soundex, they better handle non-English origins and produce more accurate phonetic codes.
• Primary Application: Matching surnames in historical records, genealogy, and customer databases where data may originate from verbal transcription.

These methods compare strings by first tokenizing them into sets or bags of words, then applying set or statistical similarity measures.

• Jaccard Index: Measures overlap as the size of the intersection divided by the size of the union of the token sets. Simple and effective for comparing short sets.
• TF-IDF Weighting: Assigns importance weights to tokens based on their frequency in the document (TF) and inverse frequency across the corpus (IDF). Similarity is then computed via cosine similarity on the weighted vectors.
• Best For: Matching longer text fields like addresses ('123 Maple St, Apt B' vs '123 Maple Street, Unit B'), product descriptions, or document titles.

The Ratcliff/Obershelp algorithm (also known as Gestalt Pattern Matching) uses a heuristic approach based on finding the longest common subsequence, then recursively matching the substrings to the left and right of this sequence.

• Mechanism: It computes similarity as 2.0 * (number of matching characters) / (total length of both strings). The matching characters are found via the recursive longest common substring search.
• Characteristic: It is inherently more forgiving of insertions and deletions within similar sequences than pure edit distance.
• Example Use: It is the algorithm behind Python's difflib.SequenceMatcher and is often used for bioinformatics sequence alignment and natural language text comparison.

Entity resolution is the overarching process of determining whether multiple data records refer to the same real-world entity. It is a critical step in building a clean, unified knowledge graph.

• Core Task: Disambiguating, linking, and merging duplicate or overlapping records.
• Techniques: Employs a pipeline often involving fuzzy matching, deterministic rules, and machine learning classifiers.
• Example: Identifying that "J. Smith Corp," "J Smith Corporation," and "Smith Co." in different supplier databases all refer to the same legal entity.

Canonicalization is the process of converting data with multiple possible representations into a single, standard, authoritative form (the canonical form). It is a key post-matching transformation.

• Purpose: Ensures consistency after entities are resolved.
• Process: Applies rules to standardize values like names, addresses, and product codes.
• Example: After fuzzy matching confirms identity, transforming all variations ("NYC," "New York City," "N.Y.") into the canonical form "New York, New York."

Levenshtein distance (or edit distance) is a foundational string metric for fuzzy matching. It quantifies the minimum number of single-character edits (insertions, deletions, substitutions) required to change one string into another.

• Algorithm: A dynamic programming algorithm that calculates this distance.
• Use Case: Effective for detecting typos and minor spelling variations (e.g., "Kitten" → "Sitting" has a distance of 3).
• Limitation: Computationally intensive for long strings and does not account for semantic similarity.

Jaccard similarity is a set-based similarity measure used in fuzzy matching, particularly for tokenized text. It is defined as the size of the intersection divided by the size of the union of two sets.

• Formula: J(A, B) = |A ∩ B| / |A ∪ B|
• Application: Often used with n-grams (shingling). The strings are broken into sets of overlapping character sequences, and their overlap is measured.
• Example: Useful for matching product descriptions or document titles where word order may vary.

Deduplication is the process of identifying and removing duplicate records within a single dataset. It is a specific application of entity resolution and relies heavily on fuzzy matching techniques.

• Scope: Intra-dataset cleansing vs. inter-dataset linking (which is identity resolution).
• Process: Typically involves blocking (to reduce comparisons) followed by pairwise matching using fuzzy algorithms.
• Business Impact: Eliminates redundant data, reduces storage costs, and prevents skewed analytics.

Schema alignment is the process of establishing semantic correspondences between the attributes, tables, or classes of two or more heterogeneous data schemas. It enables the integration of structurally different data.

• Relationship to Fuzzy Matching: While fuzzy matching operates on instance data (values), schema alignment operates on metadata (structure). Both are required for full semantic integration.
• Techniques: Can use linguistic matching (fuzzy matching on column names), constraint-based analysis, or instance-based matching using the data itself.
• Output: A mapping that dictates how data from source A transforms to fit the schema of target B.