Typeahead and Autocomplete Systems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def naive_prefix_search(corpus: List[str], prefix: str) -> List[str]:
    """
    Linear scan through entire corpus.
    Time: O(n * m) where n = corpus size, m = average string length
    Space: O(k) where k = number of matches
    """
    matches = []
    for term in corpus:
        if term.startswith(prefix):
            matches.append(term)
    return matches
 
# Real-world performance:
# - 1M terms, 10-char average: ~100ms per query
# - 100M terms: ~10 seconds per query
# - 1B terms: ~100 seconds per query
# 
# Verdict: Catastrophically slow at scale

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import bisect
 
def binary_prefix_search(sorted_corpus: List[str], prefix: str) -> List[str]:
    """
    Binary search to find range boundaries, then collect matches.
    Time: O(log n + k) where k = number of matches
    Space: O(k) for results
    """
    # Find leftmost position where prefix could exist
    left = bisect.bisect_left(sorted_corpus, prefix)
    
    # Create upper bound by incrementing last character
    # e.g., "app" -> "apq" (character after 'p')
    prefix_upper = prefix[:-1] + chr(ord(prefix[-1]) + 1) if prefix else ""
    right = bisect.bisect_left(sorted_corpus, prefix_upper)
    
    return sorted_corpus[left:right]
 
# Performance analysis:
# - Finding boundaries: O(log n) = ~30 comparisons for 1B terms
# - Collecting results: O(k) where k << n for specific prefixes
# 
# Better! But still has problems...

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

def is_prefix(prefix: str, target: str) -> bool:
    """
    Check if prefix is a prefix of target.
    Demonstrates character-by-character matching.
    """
    if len(prefix) > len(target):
        return False
    
    for i, char in enumerate(prefix):
        if target[i] != char:
            return False
    return True
 
def common_prefix_length(s1: str, s2: str) -> int:
    """
    Find the length of the longest common prefix.
    This is the key insight behind trie efficiency.
    """
    min_len = min(len(s1), len(s2))
    for i in range(min_len):
        if s1[i] != s2[i]:
            return i
    return min_len
 
# Example:
# "application", "apple", "apply", "appetite"
# All share prefix "app" (length 3)
# Processing "app" once instead of 4 times is 4x more efficient
# At scale with millions of "app*" words, this savings is massive

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

class LexicographicRangeIndex:
    """
    Prefix search using range queries on sorted data.
    Useful when data is already in sorted structures (B-trees, SSTables).
    """
    
    def __init__(self, terms: List[str]):
        self.sorted_terms = sorted(terms)
    
    def prefix_to_range(self, prefix: str) -> Tuple[str, str]:
        """
        Convert prefix to [inclusive_start, exclusive_end) range.
        
        Examples:
            "app" -> ["app", "apq")   # Everything starting with "app"
            "z"   -> ["z", "{")       # '{' is char after 'z' in ASCII
            ""    -> ["", "￿")        # Empty prefix matches all
        """
        if not prefix:
            return ("", "￿")  # Unicode max char
        
        # Increment last character for exclusive upper bound
        last_char = prefix[-1]
        next_char = chr(ord(last_char) + 1)
        upper = prefix[:-1] + next_char
        
        return (prefix, upper)
    
    def search(self, prefix: str, limit: int = 10) -> List[str]:
        """
        Find terms matching prefix using binary search.
        """
        lower, upper = self.prefix_to_range(prefix)
        
        # Find boundaries
        import bisect
        left = bisect.bisect_left(self.sorted_terms, lower)
        right = bisect.bisect_left(self.sorted_terms, upper)
        
        # Return limited results
        return self.sorted_terms[left:min(right, left + 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

class FSAPrefixMatcher:
    """
    Prefix matching using Finite State Automata.
    Useful for complex patterns combining prefix, infix, and suffix.
    """
    
    def __init__(self):
        self.states = {}  # state_id -> {char -> next_state}
        self.accepting = set()  # states that represent complete words
        self.start_state = 0
        self.next_state_id = 1
    
    def add_word(self, word: str):
        """Build FSA incrementally by adding words."""
        state = self.start_state
        
        for char in word:
            if state not in self.states:
                self.states[state] = {}
            
            if char not in self.states[state]:
                self.states[state][char] = self.next_state_id
                self.next_state_id += 1
            
            state = self.states[state][char]
        
        self.accepting.add(state)
    
    def prefix_match(self, prefix: str) -> Tuple[bool, int]:
        """
        Check if prefix exists and return the state reached.
        Returns (exists, state_id)
        """
        state = self.start_state
        
        for char in prefix:
            if state not in self.states:
                return (False, -1)
            if char not in self.states[state]:
                return (False, -1)
            state = self.states[state][char]
        
        return (True, state)
    
    def collect_completions(self, state: int, current: str, 
                           results: List[str], limit: int):
        """DFS to collect all completions from a state."""
        if len(results) >= limit:
            return
        
        if state in self.accepting:
            results.append(current)
        
        if state in self.states:
            for char, next_state in self.states[state].items():
                self.collect_completions(
                    next_state, current + char, 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

class RollingHashPrefixFilter:
    """
    Use rolling hashes to quickly filter prefix candidates.
    Especially useful for UTF-8/Unicode where char comparison is expensive.
    """
    
    def __init__(self, base: int = 31, mod: int = 10**9 + 7):
        self.base = base
        self.mod = mod
        self.prefix_hashes = {}  # hash -> list of (term, full_hash)
    
    def compute_prefix_hash(self, s: str, length: int) -> int:
        """Compute hash of first 'length' characters."""
        h = 0
        for i in range(min(length, len(s))):
            h = (h * self.base + ord(s[i])) % self.mod
        return h
    
    def index_term(self, term: str, max_prefix_len: int = 10):
        """Index a term with all its prefix hashes."""
        for length in range(1, min(len(term) + 1, max_prefix_len + 1)):
            prefix_hash = self.compute_prefix_hash(term, length)
            if prefix_hash not in self.prefix_hashes:
                self.prefix_hashes[prefix_hash] = []
            self.prefix_hashes[prefix_hash].append(term)
    
    def search(self, prefix: str) -> List[str]:
        """Find terms matching prefix using hash lookup."""
        prefix_hash = self.compute_prefix_hash(prefix, len(prefix))
        candidates = self.prefix_hashes.get(prefix_hash, [])
        
        # Verify candidates (hash collision possible)
        return [term for term in candidates 
                if term.startswith(prefix)]
 
# Note: This trades space for time
# Good for: expensive comparisons, very large alphabets
# Bad for: memory-constrained environments

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

def calculate_memory_requirements():
    """
    Calculate memory for 100M terms, avg 15 chars each.
    """
    n_terms = 100_000_000
    avg_length = 15
    alphabet_size = 27
    pointer_size = 8  # bytes on 64-bit
    
    # Raw string storage
    raw_strings = n_terms * avg_length
    print(f"Raw strings: {raw_strings / 1e9:.2f} GB")
    # Output: ~1.5 GB
    
    # Sorted array (strings + pointers)
    sorted_array = raw_strings + (n_terms * pointer_size)
    print(f"Sorted array: {sorted_array / 1e9:.2f} GB")
    # Output: ~2.3 GB
    
    # Array trie (worst case: each char = new node)
    # Each node: alphabet_size pointers + metadata
    node_size = alphabet_size * pointer_size + 16  # 16 bytes metadata
    max_nodes = n_terms * avg_length  # worst case
    array_trie = max_nodes * node_size
    print(f"Array trie (worst): {array_trie / 1e9:.2f} GB")
    # Output: ~360 GB (!!)
    
    # Compressed trie (realistic: ~10% unique prefixes)
    unique_prefix_ratio = 0.10
    compressed_nodes = n_terms * avg_length * unique_prefix_ratio
    # Use hash children: avg 2 children per node, 16 bytes each entry
    compressed_trie = compressed_nodes * (16 * 2 + 16 + avg_length)
    print(f"Compressed trie (realistic): {compressed_trie / 1e9:.2f} GB")
    # Output: ~8 GB
    
calculate_memory_requirements()

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

class LimitedPrefixIndex:
    """
    Index with prefix length cap for predictable performance.
    """
    MAX_PREFIX_LENGTH = 12
    
    def __init__(self):
        # Direct hash lookup: prefix -> sorted list of (score, term)
        self.prefix_to_terms: Dict[str, List[Tuple[float, str]]] = {}
    
    def index_term(self, term: str, score: float):
        """Add term with all its capped prefixes."""
        normalized = term.lower().strip()
        
        for length in range(1, min(len(normalized) + 1, 
                                   self.MAX_PREFIX_LENGTH + 1)):
            prefix = normalized[:length]
            
            if prefix not in self.prefix_to_terms:
                self.prefix_to_terms[prefix] = []
            
            # Insert maintaining sort by score (descending)
            import bisect
            bisect.insort(
                self.prefix_to_terms[prefix], 
                (-score, term)  # Negative for descending order
            )
    
    def search(self, prefix: str, limit: int = 10) -> List[str]:
        """O(1) lookup + O(limit) result extraction."""
        normalized = prefix.lower().strip()[:self.MAX_PREFIX_LENGTH]
        
        if normalized not in self.prefix_to_terms:
            return []
        
        results = self.prefix_to_terms[normalized][:limit]
        return [term for (neg_score, term) in results]

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

class PrefixShardRouter:
    """
    Route prefix queries to appropriate shards.
    Enables horizontal scaling across machines.
    """
    
    def __init__(self, num_shards: int = 26):
        """
        Default: one shard per first letter (a-z).
        Production: finer granularity based on traffic distribution.
        """
        self.num_shards = num_shards
        self.shard_boundaries = self._compute_boundaries()
    
    def _compute_boundaries(self) -> List[str]:
        """
        Compute shard boundaries for even distribution.
        In practice, use traffic analysis for optimal splits.
        """
        # Simple: split by first character
        return [chr(ord('a') + i) for i in range(26)]
    
    def route_query(self, prefix: str) -> int:
        """Determine which shard handles this prefix."""
        if not prefix:
            return -1  # Broadcast to all shards
        
        first_char = prefix[0].lower()
        if 'a' <= first_char <= 'z':
            return ord(first_char) - ord('a')
        return self.num_shards - 1  # Special characters shard
    
    def route_term(self, term: str) -> int:
        """Determine which shard stores this term."""
        return self.route_query(term)
 
# Example deployment:
# - 26 shards for letters a-z
# - Each shard: ~4M terms (100M / 26)
# - Per-shard memory: ~300 MB
# - Query touches exactly 1 shard (no scatter-gather)

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

import unicodedata
 
class UnicodeNormalizer:
    """Handle Unicode complexities in prefix matching."""
    
    @staticmethod
    def normalize(text: str) -> str:
        """
        Normalize text for consistent matching.
        
        Steps:
        1. Unicode normalization (NFC/NFKC)
        2. Case folding
        3. Diacritic removal (optional)
        4. Whitespace normalization
        """
        # NFC normalization: compose characters
        # e.g., 'é' as single char vs 'e' + combining accent
        normalized = unicodedata.normalize('NFC', text)
        
        # Case fold (better than lower() for Unicode)
        normalized = normalized.casefold()
        
        # Optional: remove diacritics for accent-insensitive search
        # 'café' -> 'cafe'
        normalized = ''.join(
            c for c in unicodedata.normalize('NFD', normalized)
            if unicodedata.category(c) != 'Mn'  # Mn = Mark, Nonspacing
        )
        
        # Normalize whitespace
        normalized = ' '.join(normalized.split())
        
        return normalized
    
    @staticmethod
    def generate_variants(text: str) -> List[str]:
        """
        Generate searchable variants for a term.
        Essential for matching user queries to canonical terms.
        """
        variants = set()
        
        # Original (normalized)
        normalized = UnicodeNormalizer.normalize(text)
        variants.add(normalized)
        
        # Without diacritics
        ascii_only = normalized.encode('ascii', 'ignore').decode()
        variants.add(ascii_only)
        
        # Common transliterations
        # e.g., 'ü' -> 'ue' in German
        transliterations = {
            'ü': 'ue', 'ö': 'oe', 'ä': 'ae',
            'ß': 'ss', 'ñ': 'n', 'ç': 'c'
        }
        transliterated = normalized
        for src, dst in transliterations.items():
            transliterated = transliterated.replace(src, dst)
        variants.add(transliterated)
        
        return list(variants)

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

class GracefulFallbackSearch:
    """Handle no-results scenarios with intelligent fallbacks."""
    
    def __init__(self, index: PrefixIndex):
        self.index = index
        self.popular_terms = []  # Pre-computed popular terms
    
    def search_with_fallback(self, prefix: str, limit: int = 10) -> dict:
        """
        Search with multiple fallback strategies.
        Returns results + metadata about match quality.
        """
        # Try exact prefix match first
        results = self.index.search(prefix, limit)
        
        if results:
            return {
                'results': results,
                'match_type': 'prefix_exact',
                'confidence': 1.0
            }
        
        # Fallback 1: Try shorter prefix
        for length in range(len(prefix) - 1, 0, -1):
            shorter_prefix = prefix[:length]
            results = self.index.search(shorter_prefix, limit)
            if results:
                return {
                    'results': results,
                    'match_type': 'prefix_truncated',
                    'original_prefix': prefix,
                    'matched_prefix': shorter_prefix,
                    'confidence': length / len(prefix)
                }
        
        # Fallback 2: Suggest popular terms
        return {
            'results': self.popular_terms[:limit],
            'match_type': 'popular_fallback',
            'message': f'No matches for "{prefix}"',
            'confidence': 0.0
        }