Autocomplete

Autocomplete Algorithms

This module provides high-level autocomplete functionality using different underlying data structures and strategies. It demonstrates the practical applications of Trie, Suffix Tree, and Suffix Array data structures for building efficient autocomplete systems.

Strategies Implemented:

1. Trie-based autocomplete (fastest for prefix matching)
2. Suffix Tree-based autocomplete (supports substring matching)
3. Suffix Array-based autocomplete (memory efficient)
4. Hybrid approach combining multiple strategies
5. Weighted/ranked autocomplete with popularity scores

Performance Characteristics:

• Trie: O(p) search, O(p + k) suggestions where p=prefix length, k=results
• Suffix Tree: O(p) search, O(p + k) suggestions, supports substring matching
• Suffix Array: O(p log n) search, O(p log n + k) suggestions where n=text length
• Memory usage: Trie > Suffix Tree > Suffix Array

Use Cases:

• Search engines
• Code editors (IDE autocomplete)
• Command line interfaces
• Form field suggestions
• Text messaging apps

autocomplete_search(query, words, max_suggestions=10, strategy=AutocompleteStrategy.TRIE, substring_match=False)

Simple autocomplete search function.

Parameters:

Name	Type	Description	Default
query	str	Search query	required
words	List[str]	List of words to search in	required
max_suggestions	int	Maximum number of suggestions	10
strategy	AutocompleteStrategy	Strategy to use	TRIE
substring_match	bool	Whether to allow substring matching	False

Returns:

Type	Description
List[str]	List of suggested words

autocomplete_with_scores(query, word_score_pairs, max_suggestions=10, strategy=AutocompleteStrategy.HYBRID)

Autocomplete search with popularity scoring.

Parameters:

Name	Type	Description	Default
query	str	Search query	required
word_score_pairs	List[Tuple[str, float]]	List of (word, score) tuples	required
max_suggestions	int	Maximum number of suggestions	10
strategy	AutocompleteStrategy	Strategy to use	HYBRID

Returns:

Type	Description
List[Tuple[str, float]]	List of (word, score) tuples sorted by relevance

create_autocomplete(words, scores=None, strategy=AutocompleteStrategy.TRIE, case_sensitive=False)

Create an autocomplete instance with the specified strategy.

Parameters:

Name	Type	Description	Default
words	List[str]	List of words for autocomplete	required
scores	Optional[List[float]]	Optional popularity scores	None
strategy	AutocompleteStrategy	Autocomplete strategy to use	TRIE
case_sensitive	bool	Whether matching should be case-sensitive	False

Returns:

Type	Description
Union[TrieAutocomplete, SuffixTreeAutocomplete, SuffixArrayAutocomplete, HybridAutocomplete]	Configured autocomplete instance

demo_autocomplete()

Demonstrate different autocomplete strategies.