String Similarity

The foundational edit-distance metric that counts the minimum number of single-character operations—insertions, deletions, or substitutions—required to transform one string into another. For example, transforming 'kitten' into 'sitting' requires three edits (substitute 'k' for 's', substitute 'e' for 'i', insert 'g'), yielding a distance of 3.

• Time complexity: O(m × n) using dynamic programming with a matrix
• Best for: Short strings, spell-checking, and exact fuzzy matching
• Limitation: Treats all edit operations equally, ignoring character proximity on keyboards or phonetic similarity
• Variants: Damerau-Levenshtein adds transposition of adjacent characters as a single operation

A string comparator optimized for personal name matching that measures the proportion of common characters and transpositions between two strings, then applies a prefix bonus. The Jaro similarity score ranges from 0 to 1, while the Winkler modification boosts scores for strings that share a common prefix of up to 4 characters.

• Formula basis: Accounts for matching characters within a sliding window of half the longer string's length
• Prefix scaling: Winkler's adjustment multiplies the score by p × l × (1 - Jaro), where p is a constant (typically 0.1) and l is the common prefix length
• Best for: Record linkage in census data, CRM deduplication, and name-matching tasks
• Advantage over Levenshtein: Penalizes early mismatches less severely, reflecting real-world typo patterns

A vector-space metric that measures the cosine of the angle between two non-zero vectors in a multi-dimensional space, producing a value from -1 (opposite) to 1 (identical). In string matching, text is first converted to a numerical vector using techniques like TF-IDF or Bag-of-Words, then compared.

• Formula: cos(θ) = (A · B) / (||A|| × ||B||)
• Key property: Magnitude-invariant—focuses purely on orientation, making it robust to document length differences
• Best for: Long-form text comparison, document clustering, and semantic search when combined with embeddings
• Limitation: Ignores word order entirely; 'dog bites man' and 'man bites dog' yield identical cosine similarity

A set-based metric that computes the size of the intersection divided by the size of the union of two sample sets. For strings, the sets are typically constructed from character n-grams or tokenized words, making it effective for detecting near-duplicate documents and plagiarism.

• Formula: J(A, B) = |A ∩ B| / |A ∪ B|
• N-gram application: Splitting 'hello' into bigrams yields {he, el, ll, lo}, enabling fuzzy comparison via set overlap
• Best for: Duplicate detection in large corpora, shingling-based near-duplicate identification
• Efficiency: Can be approximated at scale using MinHash for sub-linear deduplication across millions of documents

The simplest edit-distance metric, defined as the number of positions at which two strings of equal length differ. It requires strings to be the same length and operates in O(n) time, making it the fastest string comparison algorithm available.

• Operation: Performs a character-by-character XOR comparison
• Best for: Error detection and correction codes, fixed-length identifiers, binary string comparison
• Example: Hamming distance between 'karolin' and 'kathrin' is 3 (positions 3, 4, and 6 differ)
• Limitation: Cannot handle insertions or deletions, restricting its use to fixed-length fields like hash codes or sensor readings

A dynamic programming algorithm for local sequence alignment that identifies the most similar substring regions between two sequences, rather than forcing a global match. Originally developed for bioinformatics, it applies a substitution matrix and gap penalties to find optimal partial matches.

• Key difference from Levenshtein: Allows segments of high similarity to be identified even when the overall strings diverge significantly
• Scoring: Uses positive scores for matches, negative scores for mismatches and gaps, with a floor of zero to reset alignment
• Best for: Plagiarism detection, identifying copied passages, and matching addresses with extraneous components
• Trade-off: O(m × n) time and space complexity, making it computationally expensive for long strings

The foundational edit distance metric that quantifies string dissimilarity by counting the minimum number of single-character operations—insertions, deletions, or substitutions—required to transform one string into another.

• Core Mechanism: Dynamic programming matrix of size (m+1) × (n+1)
• Cost Model: Each operation has a uniform cost of 1
• Use Case: Spell-checking, DNA sequence alignment, fuzzy record linkage
• Limitation: Does not account for transpositions (e.g., 'ab' to 'ba' costs 2)

A string similarity metric optimized for short strings like personal names, measuring the proportion of matching characters within a defined distance window, with a prefix bonus that rewards strings sharing a common prefix.

• Jaro Formula: Based on the number and order of matching characters and transpositions
• Winkler Modification: Applies a scaling factor (typically 0.1) for matching prefixes up to 4 characters
• Range: 0.0 (no similarity) to 1.0 (exact match)
• Ideal For: Record linkage in census data, duplicate name detection

A family of algorithms that encode words into a representation of their pronunciation rather than their spelling, enabling matching of homophones and similarly sounding terms despite orthographic differences.

• Soundex: Classic algorithm producing a letter-digit-digit-digit code; retains the first letter
• Metaphone: Improves on Soundex by using English pronunciation rules and handling consonant clusters
• Double Metaphone: Generates both a primary and alternate encoding for names with ambiguous pronunciation
• Application: Name matching in genealogy, voice-to-text error correction

A set-based similarity approach that decomposes strings into overlapping subsequences of length N (typically bigrams or trigrams) and computes the overlap coefficient between the resulting sets.

• Dice Coefficient: 2 × |intersection| / (|set A| + |set B|)
• Jaccard Index: |intersection| / |union|
• Advantage: Robust to word reordering and substring insertions
• Common N: Bigrams (N=2) and trigrams (N=3) for word-level; character trigrams for fuzzy string matching

Two distinct text normalization strategies that reduce inflectional and derivational forms to a common base, dramatically improving string similarity recall when comparing words with shared meaning but different surface forms.

• Stemming: Heuristic, rule-based suffix stripping (e.g., 'running' → 'run', 'studies' → 'studi'); fast but crude
• Lemmatization: Vocabulary-driven reduction to dictionary form using POS tagging and morphological analysis (e.g., 'better' → 'good', 'ran' → 'run')
• Impact on Similarity: Preprocessing with lemmatization converts lexical distance into semantic equivalence

The computational task of detecting and rectifying typographical errors by finding the most probable intended word from a candidate set, heavily reliant on string similarity metrics to rank alternatives.

• Noisy Channel Model: P(correct|typo) ∝ P(typo|correct) × P(correct)
• Candidate Generation: Words within a bounded edit distance (typically Levenshtein distance ≤ 2)
• Damerau-Levenshtein: Extends edit distance to include transposition of adjacent characters as a single operation
• Modern Approach: Contextual spell-checkers using transformer models that consider surrounding words