1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

def levenshtein_distance(s1: str, s2: str) -> int:
    """
    Classic Levenshtein distance using dynamic programming.
    
    Time: O(m × n)
    Space: O(m × n)
    
    The recurrence:
    dp[i][j] = min(
        dp[i-1][j] + 1,      # deletion from s1
        dp[i][j-1] + 1,      # insertion into s1
        dp[i-1][j-1] + cost  # substitution (cost=0 if chars match)
    )
    """
    m, n = len(s1), len(s2)
    
    # Create matrix
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: transforming empty string
    for i in range(m + 1):
        dp[i][0] = i  # i deletions needed
    for j in range(n + 1):
        dp[0][j] = j  # j insertions needed
    
    # Fill matrix
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                cost = 0
            else:
                cost = 1
            
            dp[i][j] = min(
                dp[i-1][j] + 1,      # delete
                dp[i][j-1] + 1,      # insert
                dp[i-1][j-1] + cost  # substitute/match
            )
    
    return dp[m][n]
 
 
# Examples:
print(levenshtein_distance("kitten", "sitting"))  # 3
# kitten → sitten (s→k) → sittin (i→e) → sitting (g insertion)
 
print(levenshtein_distance("hello", "hallo"))     # 1
# hello → hallo (a→e)
 
print(levenshtein_distance("abc", "abc"))         # 0
# No edits needed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

def levenshtein_optimized(s1: str, s2: str) -> int:
    """
    Space-optimized Levenshtein - O(min(m,n)) space.
    """
    # Ensure s1 is shorter for space efficiency
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    
    m, n = len(s1), len(s2)
    
    # Only need current and previous row
    prev_row = list(range(m + 1))
    curr_row = [0] * (m + 1)
    
    for j in range(1, n + 1):
        curr_row[0] = j
        
        for i in range(1, m + 1):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            
            curr_row[i] = min(
                prev_row[i] + 1,      # delete
                curr_row[i-1] + 1,    # insert
                prev_row[i-1] + cost  # substitute/match
            )
        
        prev_row, curr_row = curr_row, prev_row
    
    return prev_row[m]
 
 
def levenshtein_with_threshold(s1: str, s2: str, max_dist: int) -> int:
    """
    Early termination when distance exceeds threshold.
    Critical optimization for autocomplete where we only want
    matches within small distance (1-2 edits).
    
    Returns distance if ≤ max_dist, else returns max_dist + 1
    """
    if abs(len(s1) - len(s2)) > max_dist:
        return max_dist + 1  # Can't possibly be within threshold
    
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    
    m, n = len(s1), len(s2)
    prev_row = list(range(m + 1))
    curr_row = [0] * (m + 1)
    
    for j in range(1, n + 1):
        curr_row[0] = j
        row_min = j  # Track minimum in current row
        
        for i in range(1, m + 1):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            
            curr_row[i] = min(
                prev_row[i] + 1,
                curr_row[i-1] + 1,
                prev_row[i-1] + cost
            )
            row_min = min(row_min, curr_row[i])
        
        # Early termination: if entire row exceeds threshold,
        # the final result will too
        if row_min > max_dist:
            return max_dist + 1
        
        prev_row, curr_row = curr_row, prev_row
    
    return prev_row[m] if prev_row[m] <= max_dist else max_dist + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

def damerau_levenshtein(s1: str, s2: str) -> int:
    """
    Damerau-Levenshtein distance: edits + transpositions.
    
    Transposition: swapping two adjacent characters counts as
    one operation, not two substitutions.
    
    Time: O(m × n)
    Space: O(m × n)
    """
    m, n = len(s1), len(s2)
    
    # Need 2D array for transposition lookback
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            
            dp[i][j] = min(
                dp[i-1][j] + 1,      # deletion
                dp[i][j-1] + 1,      # insertion
                dp[i-1][j-1] + cost  # substitution
            )
            
            # Transposition: if current chars are swapped versions
            # of previous chars, we can transpose
            if (i > 1 and j > 1 and 
                s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]):
                dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)
    
    return dp[m][n]
 
# Examples:
print(damerau_levenshtein("ab", "ba"))  # 1 (transposition)
# Regular Levenshtein would be 2
 
print(damerau_levenshtein("teh", "the"))  # 1
# Common typo, fixed with one transposition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

def soundex(word: str) -> str:
    """
    Generate Soundex code for a word.
    
    Phonetic groups:
    1: B, F, P, V (labials)
    2: C, G, J, K, Q, S, X, Z (gutturals/sibilants)
    3: D, T (dentals)
    4: L (liquids)
    5: M, N (nasals)
    6: R (semivowel)
    0: A, E, I, O, U, H, W, Y (ignored except first letter)
    """
    if not word:
        return ""
    
    # Mapping table
    mapping = {
        'B': '1', 'F': '1', 'P': '1', 'V': '1',
        'C': '2', 'G': '2', 'J': '2', 'K': '2', 
        'Q': '2', 'S': '2', 'X': '2', 'Z': '2',
        'D': '3', 'T': '3',
        'L': '4',
        'M': '5', 'N': '5',
        'R': '6',
        'A': '0', 'E': '0', 'I': '0', 'O': '0', 
        'U': '0', 'H': '0', 'W': '0', 'Y': '0',
    }
    
    word = word.upper()
    
    # Keep first letter
    result = word[0]
    prev_code = mapping.get(word[0], '0')
    
    for char in word[1:]:
        code = mapping.get(char, '')
        
        if code and code != '0' and code != prev_code:
            result += code
            prev_code = code
        elif code == '0':
            # Vowels act as separators for repeated consonants
            prev_code = '0'
    
    # Pad or truncate to 4 characters
    result = result[:4].ljust(4, '0')
    
    return result
 
 
# Examples demonstrating phonetic matching:
print(soundex("Robert"))    # R163
print(soundex("Rupert"))    # R163 - Same code!
 
print(soundex("Smith"))     # S530
print(soundex("Smyth"))     # S530 - Same code!
 
print(soundex("phone"))     # P500
print(soundex("fone"))      # F500 - Different first letter, but close
 
# Use case: Match people with similar-sounding names
# "John Smith" matches "Jon Smyth"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

def simple_metaphone(word: str) -> str:
    """
    Simplified Metaphone implementation.
    Full implementation handles 100+ rules.
    
    Key improvements over Soundex:
    - Handles more letter combinations
    - Drops silent letters
    - Language-aware transformations
    """
    if not word:
        return ""
    
    word = word.upper()
    result = []
    i = 0
    
    # Skip silent initial letters
    if word[:2] in ('KN', 'GN', 'PN', 'AE', 'WR'):
        i = 1
    
    while i < len(word):
        char = word[i]
        next_char = word[i+1] if i+1 < len(word) else ''
        
        # Apply transformation rules (simplified)
        if char in 'AEIOU':
            if i == 0:  # Only code vowels at start
                result.append(char)
        elif char == 'B':
            if not (i == len(word) - 1 and word[i-1:i] == 'M'):
                result.append('B')
        elif char == 'C':
            if next_char in 'EIY':
                result.append('S')
            elif next_char == 'H':
                result.append('X')
                i += 1
            else:
                result.append('K')
        elif char == 'D':
            if next_char == 'G' and word[i+2:i+3] in 'EIY':
                result.append('J')
                i += 1
            else:
                result.append('T')
        elif char in 'FJLMNR':
            result.append(char)
        elif char == 'G':
            if next_char == 'H':
                i += 1  # Silent GH
            elif next_char in 'EIY':
                result.append('J')
            else:
                result.append('K')
        elif char == 'H':
            if i > 0 and word[i-1] not in 'AEIOU':
                pass  # Silent after consonant
            elif next_char in 'AEIOU':
                result.append('H')
        elif char == 'K':
            if i == 0 or word[i-1] != 'C':
                result.append('K')
        elif char == 'P':
            if next_char == 'H':
                result.append('F')
                i += 1
            else:
                result.append('P')
        elif char == 'Q':
            result.append('K')
        elif char == 'S':
            if next_char == 'H':
                result.append('X')
                i += 1
            else:
                result.append('S')
        elif char == 'T':
            if next_char == 'H':
                result.append('0')  # θ sound
                i += 1
            else:
                result.append('T')
        elif char == 'V':
            result.append('F')
        elif char == 'W':
            if next_char in 'AEIOU':
                result.append('W')
        elif char == 'X':
            result.append('KS')
        elif char == 'Y':
            if next_char in 'AEIOU':
                result.append('Y')
        elif char == 'Z':
            result.append('S')
        
        i += 1
    
    return ''.join(result)
 
 
# Examples:
print(simple_metaphone("knight"))  # NT (silent K)
print(simple_metaphone("night"))   # NT (same!)
 
print(simple_metaphone("phone"))   # FN
print(simple_metaphone("fone"))    # FN (same!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

from typing import Set
 
def get_ngrams(s: str, n: int = 2) -> Set[str]:
    """
    Extract all n-grams from a string.
    
    Padding with special characters helps match prefixes/suffixes:
    "$hello$" → ["$h", "he", "el", "ll", "lo", "o$"]
    """
    # Pad with boundary markers
    padded = "$" + s.lower() + "$"
    
    ngrams = set()
    for i in range(len(padded) - n + 1):
        ngrams.add(padded[i:i+n])
    
    return ngrams
 
 
def jaccard_similarity(s1: str, s2: str, n: int = 2) -> float:
    """
    Jaccard similarity: |intersection| / |union|
    
    Range: [0, 1] where 1 = identical n-gram sets
    """
    ngrams1 = get_ngrams(s1, n)
    ngrams2 = get_ngrams(s2, n)
    
    intersection = len(ngrams1 & ngrams2)
    union = len(ngrams1 | ngrams2)
    
    return intersection / union if union > 0 else 0.0
 
 
def dice_coefficient(s1: str, s2: str, n: int = 2) -> float:
    """
    Dice coefficient: 2 × |intersection| / (|set1| + |set2|)
    
    Similar to Jaccard but gives more weight to matches.
    Also called Sørensen–Dice coefficient.
    """
    ngrams1 = get_ngrams(s1, n)
    ngrams2 = get_ngrams(s2, n)
    
    intersection = len(ngrams1 & ngrams2)
    total = len(ngrams1) + len(ngrams2)
    
    return (2 * intersection) / total if total > 0 else 0.0
 
 
# Examples:
print(f"'hello' vs 'hallo': {jaccard_similarity('hello', 'hallo'):.3f}")
# 0.500 - share "al", "lo" out of many
 
print(f"'hello' vs 'hello': {jaccard_similarity('hello', 'hello'):.3f}")
# 1.000 - identical
 
print(f"'programming' vs 'programing': {dice_coefficient('programming', 'programing'):.3f}")
# 0.870 - very similar despite missing 'm'
 
 
class NGramIndex:
    """
    Index documents/terms by n-grams for fuzzy search.
    
    Key insight: instead of computing similarity against all terms,
    we retrieve candidates that share n-grams with the query.
    """
    
    def __init__(self, n: int = 2):
        self.n = n
        self.ngram_to_terms: Dict[str, Set[str]] = {}
        self.all_terms: Set[str] = set()
    
    def add_term(self, term: str) -> None:
        """Index a term by its n-grams."""
        self.all_terms.add(term)
        
        for ngram in get_ngrams(term, self.n):
            if ngram not in self.ngram_to_terms:
                self.ngram_to_terms[ngram] = set()
            self.ngram_to_terms[ngram].add(term)
    
    def search(self, query: str, min_similarity: float = 0.3, 
               limit: int = 10) -> List[Tuple[str, float]]:
        """
        Find terms similar to query using n-gram overlap.
        
        Algorithm:
        1. Get n-grams from query
        2. Find all terms sharing any n-gram (candidates)
        3. Compute exact similarity for candidates
        4. Filter by threshold and return top results
        """
        query_ngrams = get_ngrams(query, self.n)
        
        # Gather candidates (terms sharing any n-gram)
        candidates: Set[str] = set()
        for ngram in query_ngrams:
            if ngram in self.ngram_to_terms:
                candidates.update(self.ngram_to_terms[ngram])
        
        # Score candidates
        results = []
        for term in candidates:
            sim = dice_coefficient(query, term, self.n)
            if sim >= min_similarity:
                results.append((term, sim))
        
        # Sort by similarity descending, return top
        results.sort(key=lambda x: -x[1])
        return results[:limit]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

class BKTreeNode:
    """Node in a BK-Tree."""
    
    def __init__(self, word: str):
        self.word = word
        # Children indexed by distance from this node
        self.children: Dict[int, 'BKTreeNode'] = {}
 
 
class BKTree:
    """
    Burkhard-Keller Tree for efficient fuzzy string search.
    
    Structure:
    - Each node stores a word
    - Children are indexed by edit distance to parent
    - Child at distance d contains words where d(parent, child) = d
    
    Query:
    - Given query q and max distance k
    - If d(q, node) = n, only search children with distance in [n-k, n+k]
    - Triangle inequality guarantees no valid matches outside this range
    
    Time: O(log n) average for small k, O(n) worst case
    Space: O(n) - stores all words
    """
    
    def __init__(self, distance_fn=None):
        self.root: Optional[BKTreeNode] = None
        self.distance = distance_fn or levenshtein_distance
        self.size = 0
    
    def insert(self, word: str) -> None:
        """Insert word into BK-tree."""
        if self.root is None:
            self.root = BKTreeNode(word)
            self.size = 1
            return
        
        node = self.root
        while True:
            dist = self.distance(word, node.word)
            
            if dist == 0:
                return  # Duplicate, ignore
            
            if dist in node.children:
                node = node.children[dist]
            else:
                node.children[dist] = BKTreeNode(word)
                self.size += 1
                return
    
    def search(self, query: str, max_distance: int) -> List[Tuple[str, int]]:
        """
        Find all words within max_distance of query.
        
        Returns list of (word, distance) tuples.
        """
        if self.root is None:
            return []
        
        results = []
        candidates = [(self.root, self.distance(query, self.root.word))]
        
        while candidates:
            node, dist = candidates.pop()
            
            # Check if this node matches
            if dist <= max_distance:
                results.append((node.word, dist))
            
            # Determine range of children to search
            low = dist - max_distance
            high = dist + max_distance
            
            for child_dist, child_node in node.children.items():
                if low <= child_dist <= high:
                    child_query_dist = self.distance(query, child_node.word)
                    candidates.append((child_node, child_query_dist))
        
        return results
 
 
# Example usage:
bk = BKTree()
 
# Build tree with vocabulary
vocabulary = [
    "hello", "hallo", "hullo", "help", "helm",
    "world", "word", "work", "worm", "worry",
    "programming", "programing", "program", "progress"
]
 
for word in vocabulary:
    bk.insert(word)
 
# Query with tolerance
results = bk.search("helo", max_distance=1)
print(results)
# [('hello', 1), ('help', 1)]
 
results = bk.search("programing", max_distance=1)
print(results)
# [('programing', 0), ('programming', 1)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

class HybridFuzzySearch:
    """
    Production-grade fuzzy search combining multiple techniques.
    """
    
    def __init__(self):
        self.trie = Trie()               # Exact prefix matching
        self.ngram_index = NGramIndex(n=2)  # Candidate generation
        self.bk_tree = BKTree()           # Precise distance filtering
        self.phonetic_index: Dict[str, List[str]] = {}  # Phonetic lookup
        self.term_scores: Dict[str, float] = {}  # Popularity scores
    
    def add_term(self, term: str, score: float = 1.0) -> None:
        """Index term across all structures."""
        normalized = term.lower().strip()
        
        self.trie.insert(normalized)
        self.ngram_index.add_term(normalized)
        self.bk_tree.insert(normalized)
        self.term_scores[normalized] = score
        
        # Phonetic indexing
        phonetic_code = simple_metaphone(normalized)
        if phonetic_code:
            if phonetic_code not in self.phonetic_index:
                self.phonetic_index[phonetic_code] = []
            self.phonetic_index[phonetic_code].append(normalized)
    
    def search(self, query: str, limit: int = 10) -> List[Dict]:
        """
        Multi-stage fuzzy search with relevance scoring.
        """
        query = query.lower().strip()
        candidates: Dict[str, Dict] = {}
        
        # Stage 1: Exact prefix matches (highest confidence)
        prefix_matches = self.trie.get_all_words_with_prefix(query)
        for term in prefix_matches[:limit * 2]:
            candidates[term] = {
                'term': term,
                'match_type': 'prefix',
                'distance': 0,
                'similarity': 1.0,
            }
        
        # Stage 2: N-gram similar terms (medium confidence)
        if len(candidates) < limit:
            ngram_matches = self.ngram_index.search(
                query, 
                min_similarity=0.4,
                limit=limit * 3
            )
            for term, sim in ngram_matches:
                if term not in candidates:
                    # Verify with edit distance
                    dist = levenshtein_with_threshold(query, term, 2)
                    if dist <= 2:
                        candidates[term] = {
                            'term': term,
                            'match_type': 'fuzzy',
                            'distance': dist,
                            'similarity': sim,
                        }
        
        # Stage 3: Phonetic matches (for sound-alike)
        if len(candidates) < limit:
            query_phonetic = simple_metaphone(query)
            if query_phonetic in self.phonetic_index:
                for term in self.phonetic_index[query_phonetic]:
                    if term not in candidates:
                        dist = levenshtein_with_threshold(query, term, 3)
                        candidates[term] = {
                            'term': term,
                            'match_type': 'phonetic',
                            'distance': dist,
                            'similarity': 0.5,  # Lower base similarity
                        }
        
        # Final scoring and ranking
        results = list(candidates.values())
        for r in results:
            # Combined score: base similarity + popularity boost
            base_score = r['similarity']
            popularity = self.term_scores.get(r['term'], 0)
            distance_penalty = r['distance'] * 0.2
            
            # Boost exact prefix matches
            type_boost = 0.3 if r['match_type'] == 'prefix' else 0
            
            r['final_score'] = (
                base_score * 0.4 +
                popularity * 0.3 +
                type_boost -
                distance_penalty
            )
        
        # Sort by final score
        results.sort(key=lambda x: -x['final_score'])
        
        return results[:limit]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

def adaptive_distance_threshold(query: str) -> int:
    """
    Determine max edit distance based on query length.
    
    Short queries: strict matching (avoid noise)
    Long queries: more tolerance (more room for typos)
    """
    length = len(query)
    
    if length <= 3:
        return 0  # Exact or prefix only for very short queries
    elif length <= 5:
        return 1  # Single edit tolerance
    elif length <= 10:
        return 2  # Common for most queries
    else:
        return 3  # Long queries can have more typos
 
 
def weighted_edit_distance(s1: str, s2: str) -> float:
    """
    Edit distance with operation-specific weights.
    
    Rationale:
    - Transpositions are very common (typing speed)
    - Substitutions depend on keyboard layout
    - Insertions/deletions vary by input method
    """
    # Weight matrix for keyboard-adjacent substitutions
    keyboard_neighbors = {
        'q': 'wa', 'w': 'qe', 'e': 'wr', 'r': 'et', 't': 'ry',
        'a': 'sz', 's': 'ad', 'd': 'sf', 'f': 'dg', 
        # ... complete keyboard layout
    }
    
    def substitution_cost(c1: str, c2: str) -> float:
        """Lower cost for keyboard-adjacent keys."""
        if c1 == c2:
            return 0.0
        if c2 in keyboard_neighbors.get(c1, ''):
            return 0.5  # Adjacent key typo
        return 1.0  # Different key
    
    # Modified Levenshtein with custom costs
    m, n = len(s1), len(s2)
    dp = [[0.0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i * 1.0  # Deletion cost
    for j in range(n + 1):
        dp[0][j] = j * 1.0  # Insertion cost
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = substitution_cost(s1[i-1], s2[j-1])
            
            dp[i][j] = min(
                dp[i-1][j] + 1.0,      # Deletion
                dp[i][j-1] + 1.0,      # Insertion
                dp[i-1][j-1] + cost    # Substitution
            )
            
            # Transposition (lower cost: 0.7)
            if (i > 1 and j > 1 and
                s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]):
                dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 0.7)
    
    return dp[m][n]