Levenshtein Distance

The Levenshtein distance is defined by three atomic single-character edit operations:

• Insertion: Adding a character (e.g., 'cat' → 'cats')
• Deletion: Removing a character (e.g., 'cats' → 'cat')
• Substitution: Replacing one character with another (e.g., 'cat' → 'bat') Each operation carries a uniform cost of 1, making the distance the minimum total cost required to transform one string into the other.

The standard dynamic programming solution for computing Levenshtein distance with O(mn) time and space complexity, where m and n are the lengths of the two strings.

• Constructs a matrix where cell (i,j) represents the distance between the first i characters of string A and the first j characters of string B
• Fills the matrix using recurrence relation: if characters match, inherit diagonal value; otherwise, take 1 + minimum of left, top, and diagonal cells
• The final distance is found in the bottom-right cell

Levenshtein distance satisfies all formal metric axioms:

• Non-negativity: Distance is always ≥ 0
• Identity of indiscernibles: Distance equals 0 if and only if the strings are identical
• Symmetry: The distance from A to B equals the distance from B to A
• Triangle inequality: The distance from A to C is ≤ the distance from A to B plus the distance from B to C These properties make it mathematically well-behaved for clustering and nearest-neighbor search.

Raw edit distance is sensitive to string length, making cross-pair comparisons difficult. A normalized Levenshtein distance scales the result to a 0–1 range:

• Formula: Normalized Distance = Levenshtein(A, B) / max(len(A), len(B))
• A value of 0 indicates identical strings
• A value of 1 indicates completely different strings requiring maximum edits This normalization is essential for setting consistent similarity thresholds in identity matching pipelines.

An extension that adds adjacent character transposition as a fourth edit operation with unit cost (e.g., 'teh' → 'the').

• Addresses a common class of typographical errors where two characters are swapped
• The optimal string alignment distance restricts edits so no substring is edited more than once
• True Damerau-Levenshtein distance allows unlimited edits but is computationally more expensive This variant is particularly valuable for name matching where transposition errors are frequent.

Several techniques reduce the practical memory footprint from O(mn) to O(min(m,n)):

• Two-row optimization: Only the current and previous rows of the matrix are stored, as each cell depends only on adjacent cells
• Hirschberg's algorithm: Achieves linear space while maintaining O(mn) time, useful for very long sequences
• Early termination: If only determining whether distance exceeds a threshold k, the algorithm can prune cells where the value exceeds k, reducing effective complexity to O(k * min(m,n))

A string edit distance algorithm optimized for short strings like personal names. It gives a higher similarity score to strings that match from the beginning, making it superior to Levenshtein for detecting typographical variations in first and last names.

• Prefix scale: Boosts scores when the first 4 characters match
• Range: 0.0 (no match) to 1.0 (exact match)
• Use case: Comparing "Johnathan" vs. "Jonathan" yields a higher score than raw edit distance

An extension of Levenshtein that includes transposition of two adjacent characters as a single edit operation. This is critical for identity matching where 80% of human typing errors are transpositions.

• Edit operations: Insertion, deletion, substitution, and transposition
• Real-world example: "Micheal" vs. "Michael" costs 1 edit (transposition) instead of 2 (substitution + insertion)
• Computational cost: O(n*m) time complexity, slightly higher than standard Levenshtein

A broader string comparison technique that calculates the probability of two text strings being a match, tolerating typographical errors, abbreviations, and formatting inconsistencies. Levenshtein distance is one of many underlying algorithms.

• Threshold tuning: Match scores above 0.85 are typically considered high-confidence
• Common libraries: FuzzyWuzzy, RapidFuzz, and TheFuzz use Levenshtein ratios
• Application: Matching "123 Main St." against "123 Main Street" in identity records

A phonetic algorithm that indexes names by their English pronunciation, converting homophones to the same alphanumeric code. Unlike Levenshtein, which measures orthographic distance, Soundex captures phonetic similarity.

• Encoding format: First letter followed by 3 digits (e.g., "Smith" → S530)
• Limitation: Designed for English surnames; performs poorly on non-Anglophone names
• Synthetic fraud relevance: Detects identity variants where fraudsters alter spelling but preserve pronunciation (e.g., "Smyth" vs. "Smith")

A metric measuring the cosine of the angle between two non-zero vectors in a multi-dimensional space. When identity attributes are embedded as vectors (via TF-IDF or neural encoders), cosine similarity quantifies semantic closeness beyond character-level edits.

• Range: -1.0 to 1.0, where 1.0 indicates identical orientation
• Advantage over Levenshtein: Captures semantic equivalence ("Robert" ≈ "Bob") that edit distance misses
• Threshold: Scores above 0.8 typically indicate high semantic similarity in identity matching

A space-efficient probabilistic data structure used in privacy-preserving record linkage to encode sensitive identity attributes into irreversible bit arrays. It enables approximate matching without exposing plaintext PII.

• Mechanism: Maps q-grams (substrings) of identity fields into bit vectors using multiple hash functions
• Similarity computation: Jaccard or Dice coefficient on Bloom filters approximates string similarity
• Security property: One-way encoding prevents reconstruction of original names while preserving edit-distance-like comparisons