Project 2: Autocomplete Engine with Trie Data Structure
Problem Statement
Build a high-performance autocomplete search engine using Trie (prefix tree) data structures. The engine must support fast prefix matching, ranked suggestions, spell checking with edit distance, and handle millions of words efficiently.
Your autocomplete system should:
- Insert words with frequency/popularity scores
- Find all words matching a prefix in O(M) where M = prefix length
- Return top-K suggestions ranked by popularity
- Provide spell check with edit distance ≤ 2
- Support deletion and updates
- Compare performance against HashMap prefix scanning
Example:
Insert: "apple" (freq: 1000), "application" (freq: 500), "apply" (freq: 300)
Query: "app" → Returns: ["apple", "application", "apply"]
Top 3: ["apple", "application", "apply"] (sorted by frequency)
Why It Matters
HashMap prefix search requires checking every word O(N). Trie provides O(M) prefix search independent of dictionary size. For 1M word dictionary with “app” prefix:
- HashMap: 1M string comparisons
- Trie: ~3 character comparisons (10,000× faster!)
This is fundamental to: search engines, IDE code completion, spell checkers, DNS/IP routing, text prediction.
Use Cases
- Search engine autocomplete (Google, Amazon product search)
- IDE code completion (variable/function suggestions)
- Spell checkers with suggestions
- Phone contact search
- Command-line completion
- DNS and IP routing tables
Milestone 1: Basic Trie with Insert and Search
Introduction
Implement a character-by-character trie where each node has 26 children (for lowercase letters). Establish insert and exact match operations.
Architecture
Structs:
-
TrieNode- Single node in trie- Field
children: [Option<Box<TrieNode>>; 26]- Child nodes (a-z) - Field
is_end: bool- True if word ends here - Field
frequency: usize- Word popularity/count
- Field
-
Trie- Root and operations- Field
root: TrieNode - Field
size: usize- Total words stored
- Field
Key Functions:
new() -> Self- Create empty trieinsert(word: &str, frequency: usize)- Add wordsearch(word: &str) -> bool- Exact matchstarts_with(prefix: &str) -> bool- Check if prefix exists
Role Each Plays:
- Array of 26 children maps ‘a’-‘z’ to indices 0-25
is_endmarks word boundaries (needed for prefixes that are also words)- Path from root spells word character-by-character
Checkpoint Tests
#![allow(unused)]
fn main() {
#[test]
fn test_insert_and_search() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("app", 50);
assert!(trie.search("apple"));
assert!(trie.search("app"));
assert!(!trie.search("application"));
}
#[test]
fn test_prefix_checking() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("apply", 80);
assert!(trie.starts_with("app"));
assert!(trie.starts_with("appl"));
assert!(!trie.starts_with("ban"));
}
#[test]
fn test_overlapping_words() {
let mut trie = Trie::new();
trie.insert("car", 100);
trie.insert("card", 80);
trie.insert("cards", 60);
assert!(trie.search("car"));
assert!(trie.search("card"));
assert!(trie.search("cards"));
}
}Starter Code
#![allow(unused)]
fn main() {
const ALPHABET_SIZE: usize = 26;
#[derive(Debug)]
struct TrieNode {
children: [Option<Box<TrieNode>>; ALPHABET_SIZE],
is_end: bool,
frequency: usize,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: Default::default(),
is_end: false,
frequency: 0,
}
}
}
pub struct Trie {
root: TrieNode,
size: usize,
}
impl Trie {
pub fn new() -> Self {
Trie {
root: TrieNode::new(),
size: 0,
}
}
pub fn insert(&mut self, word: &str, frequency: usize) {
// TODO: Traverse/create nodes for each character
// Set is_end = true and frequency at last node
// Increment size if new word
// Hint: word.chars() → char_to_index() → navigate children array
unimplemented!()
}
pub fn search(&self, word: &str) -> bool {
// TODO: Traverse trie following characters
// Return is_end of final node (or false if path doesn't exist)
unimplemented!()
}
pub fn starts_with(&self, prefix: &str) -> bool {
// TODO: Traverse trie following characters
// Return true if path exists (don't check is_end)
unimplemented!()
}
fn char_to_index(c: char) -> usize {
(c as usize) - ('a' as usize)
}
fn index_to_char(i: usize) -> char {
(b'a' + i as u8) as char
}
}
}Why previous step is not enough: N/A - Foundation.
What’s the improvement: Trie insert/search is O(M) where M = word length, independent of dictionary size:
- HashMap: O(N) for prefix search (check all words)
- Trie: O(M) for prefix search (follow path)
For 1M words, average length 7:
- HashMap prefix search: 1M comparisons
- Trie prefix search: 7 character checks (140,000× faster!)
Milestone 2: Collect All Words with Prefix
Introduction
Implement prefix search that returns all matching words. This is the core autocomplete operation.
Architecture
New Functions:
find_words_with_prefix(prefix: &str) -> Vec<String>- All matchescollect_words(&self, node: &TrieNode, prefix: String, results: &mut Vec<String>)- Recursive helper
Role Each Plays:
- Navigate to prefix node
- DFS from prefix node collecting all is_end words
- Accumulate characters during recursion to build words
Checkpoint Tests
#![allow(unused)]
fn main() {
#[test]
fn test_prefix_collection() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("application", 90);
trie.insert("apply", 80);
trie.insert("banana", 70);
let results = trie.find_words_with_prefix("app");
assert_eq!(results.len(), 3);
assert!(results.contains(&"apple".to_string()));
assert!(results.contains(&"application".to_string()));
assert!(results.contains(&"apply".to_string()));
}
#[test]
fn test_no_matches() {
let mut trie = Trie::new();
trie.insert("apple", 100);
let results = trie.find_words_with_prefix("ban");
assert!(results.is_empty());
}
}Starter Code
#![allow(unused)]
fn main() {
impl Trie {
pub fn find_words_with_prefix(&self, prefix: &str) -> Vec<String> {
// TODO: Navigate to prefix node
// If node exists, collect all words from that subtree
// Hint: Use recursive helper
unimplemented!()
}
fn collect_words(&self, node: &TrieNode, mut current: String, results: &mut Vec<String>) {
// TODO: If node.is_end, add current to results
// For each child:
// - Append child's character to current
// - Recursively collect from child
unimplemented!()
}
}
}Why previous step is not enough: Checking prefix existence isn’t enough - autocomplete needs actual word suggestions.
What’s the improvement: Collecting words is O(M + K) where M = prefix length, K = results:
- HashMap: O(N) scan all words, filter by prefix
- Trie: O(M) navigate to prefix + O(K) collect results
For prefix “app” with 100 matches from 1M words:
- HashMap: 1M comparisons
- Trie: 3 navigation + 100 collection = 103 operations (10,000× faster!)
Milestone 3: Ranked Suggestions by Frequency
Introduction
Return top-K suggestions sorted by frequency/popularity. High-frequency words appear first.
Architecture
Enhanced Return:
find_top_k(prefix: &str, k: usize) -> Vec<(String, usize)>- Top suggestions with frequencies
Implementation:
- Collect all prefix matches with frequencies
- Sort by frequency descending
- Take top K
Checkpoint Tests
#![allow(unused)]
fn main() {
#[test]
fn test_ranked_suggestions() {
let mut trie = Trie::new();
trie.insert("apple", 1000);
trie.insert("application", 500);
trie.insert("apply", 300);
trie.insert("app", 100);
let top3 = trie.find_top_k("app", 3);
assert_eq!(top3[0].0, "apple");
assert_eq!(top3[0].1, 1000);
assert_eq!(top3[1].0, "application");
assert_eq!(top3[2].0, "apply");
}
#[test]
fn test_k_larger_than_results() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("app", 50);
let top10 = trie.find_top_k("app", 10);
assert_eq!(top10.len(), 2); // Only 2 matches
}
}Starter Code
#![allow(unused)]
fn main() {
impl Trie {
pub fn find_top_k(&self, prefix: &str, k: usize) -> Vec<(String, usize)> {
// TODO: Collect all words with frequencies
// Sort by frequency descending
// Take first k elements
// Hint: modify collect_words to also collect frequency
unimplemented!()
}
fn collect_words_with_freq(
&self,
node: &TrieNode,
current: String,
results: &mut Vec<(String, usize)>,
) {
// TODO: Similar to collect_words but include frequency
unimplemented!()
}
}
}Why previous step is not enough: Unranked results aren’t useful for autocomplete. Users expect most popular/relevant suggestions first.
What’s the improvement: Top-K with frequency enables real autocomplete UX. Google search shows popular queries first, improving click-through rates by 40%.
Milestone 4: Spell Checking with Edit Distance
Introduction
Add fuzzy matching to suggest words within edit distance ≤ 2 of a query. This enables “did you mean?” suggestions for typos.
Architecture
New Functions:
find_similar(word: &str, max_distance: usize) -> Vec<(String, usize)>- Find words within edit distanceedit_distance(a: &str, b: &str) -> usize- Calculate Levenshtein distancefind_candidates_dfs(&self, node: &TrieNode, ...)- Recursive search with distance tracking
Role Each Plays:
- Edit distance: minimum insertions/deletions/substitutions to transform one word to another
- DFS explores trie while tracking accumulated distance
- Prune branches when distance exceeds threshold (optimization)
Checkpoint Tests
#![allow(unused)]
fn main() {
#[test]
fn test_edit_distance_calculation() {
assert_eq!(Trie::edit_distance("cat", "cat"), 0);
assert_eq!(Trie::edit_distance("cat", "hat"), 1); // Substitution
assert_eq!(Trie::edit_distance("cat", "cats"), 1); // Insertion
assert_eq!(Trie::edit_distance("cat", "at"), 1); // Deletion
assert_eq!(Trie::edit_distance("kitten", "sitting"), 3);
}
#[test]
fn test_fuzzy_search() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("apply", 90);
trie.insert("ample", 80);
trie.insert("maple", 70);
// "appl" → distance 1 to "apple" and "apply"
let results = trie.find_similar("appl", 1);
assert!(results.iter().any(|(w, _)| w == "apple"));
assert!(results.iter().any(|(w, _)| w == "apply"));
}
#[test]
fn test_distance_threshold() {
let mut trie = Trie::new();
trie.insert("hello", 100);
trie.insert("help", 90);
// "hello" → "help" is distance 2 (delete 'lo', add 'p')
let results = trie.find_similar("hello", 1);
assert!(!results.iter().any(|(w, _)| w == "help"));
let results = trie.find_similar("hello", 2);
assert!(results.iter().any(|(w, _)| w == "help"));
}
}Starter Code
#![allow(unused)]
fn main() {
impl Trie {
pub fn find_similar(&self, word: &str, max_distance: usize) -> Vec<(String, usize)> {
// TODO: DFS through trie collecting words within max_distance
// Hint: Track current position in target word and accumulated distance
// Prune when distance exceeds max_distance
unimplemented!()
}
pub fn edit_distance(a: &str, b: &str) -> usize {
// TODO: Implement Levenshtein distance using dynamic programming
// Create matrix[len(a)+1][len(b)+1]
// dp[i][j] = min edit distance between a[..i] and b[..j]
// Base case: dp[0][j] = j, dp[i][0] = i
// Recurrence:
// if a[i] == b[j]: dp[i+1][j+1] = dp[i][j]
// else: dp[i+1][j+1] = 1 + min(dp[i][j], dp[i+1][j], dp[i][j+1])
unimplemented!()
}
fn find_similar_dfs(
&self,
node: &TrieNode,
target: &str,
current: String,
current_distance: usize,
max_distance: usize,
results: &mut Vec<(String, usize)>,
) {
// TODO: If node.is_end, calculate distance and add to results if <= max
// For each child, recursively search
// Prune if current_distance already > max_distance
unimplemented!()
}
}
}Why previous step is not enough: Exact prefix matching can’t handle typos. Users make mistakes: “appl” instead of “apple”. Spell check with fuzzy matching improves UX significantly.
What’s the improvement: Fuzzy search enables typo correction:
- Exact match: 0 results for “aple”
- Fuzzy (distance ≤ 1): Returns “apple”
Google autocorrects 15% of queries. For e-commerce, this recovers 10-20% of failed searches.
Milestone 5: Word Deletion and Updates
Introduction
Support removing words from trie and updating frequencies. This enables dynamic dictionaries that evolve with usage patterns.
Architecture
New Functions:
delete(word: &str) -> bool- Remove word from trieupdate_frequency(word: &str, new_freq: usize) -> bool- Update word’s frequencyprune_empty_nodes(&mut self)- Clean up nodes with no children after deletion
Role Each Plays:
- Deletion: Mark is_end = false, optionally remove empty branches
- Update: Navigate to word and modify frequency
- Pruning: Remove nodes that become childless (memory optimization)
Checkpoint Tests
#![allow(unused)]
fn main() {
#[test]
fn test_word_deletion() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("app", 50);
assert!(trie.delete("apple"));
assert!(!trie.search("apple"));
assert!(trie.search("app")); // Prefix still exists
}
#[test]
fn test_delete_nonexistent() {
let mut trie = Trie::new();
trie.insert("apple", 100);
assert!(!trie.delete("banana"));
assert!(trie.search("apple")); // Unchanged
}
#[test]
fn test_frequency_update() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.update_frequency("apple", 500);
let results = trie.find_top_k("app", 5);
assert_eq!(results[0].1, 500);
}
#[test]
fn test_pruning_after_deletion() {
let mut trie = Trie::new();
trie.insert("test", 100);
trie.delete("test");
// Implementation-specific: verify memory is reclaimed
// Could track node count or memory usage
}
}Starter Code
#![allow(unused)]
fn main() {
impl Trie {
pub fn delete(&mut self, word: &str) -> bool {
// TODO: Navigate to word's end node
// If found and is_end == true:
// - Set is_end = false
// - Decrement size
// - Optionally prune empty nodes
// - Return true
// Else return false
unimplemented!()
}
pub fn update_frequency(&mut self, word: &str, new_frequency: usize) -> bool {
// TODO: Navigate to word's end node
// If found and is_end == true:
// - Update frequency
// - Return true
// Else return false
unimplemented!()
}
fn delete_recursive(
node: &mut TrieNode,
word: &str,
chars: &[char],
index: usize,
) -> bool {
// TODO: Recursive deletion with pruning
// Base case: if index == chars.len():
// - Mark is_end = false
// - Return true if node has no children (can be pruned)
// Recursive case:
// - Get child for current char
// - Recursively delete
// - If child returns true and is not is_end, remove child
unimplemented!()
}
}
}Why previous step is not enough: Real dictionaries are dynamic. User preferences change, product catalogs update, trending terms appear. Static trie can’t adapt.
What’s the improvement: Dynamic updates enable:
- Remove obsolete terms (free memory)
- Boost trending searches (better relevance)
- Personalize per user (update frequencies based on history)
For e-commerce: updating “face mask” frequency during COVID increased relevance by 1000×.
Milestone 6: Performance Comparison vs HashMap
Introduction
Benchmark Trie against HashMap for prefix search to validate performance claims. Measure operations/second at different dictionary sizes.
Architecture
Benchmarks:
- Build dictionary (N words)
- Prefix search (various prefix lengths)
- Top-K ranking
- Memory usage comparison
Checkpoint Tests
#![allow(unused)]
fn main() {
#[test]
fn test_trie_scales_with_prefix_length() {
let mut trie = Trie::new();
for i in 0..10000 {
trie.insert(&format!("word{}", i), i);
}
// Short prefix
let start = std::time::Instant::now();
let _ = trie.find_words_with_prefix("wo");
let short_time = start.elapsed();
// Long prefix
let start = std::time::Instant::now();
let _ = trie.find_words_with_prefix("word123");
let long_time = start.elapsed();
// Should be similar (both O(M))
assert!(long_time < short_time * 10);
}
}Starter Code
#![allow(unused)]
fn main() {
use std::time::Instant;
use std::collections::HashMap;
pub struct AutocompleteBenchmark;
impl AutocompleteBenchmark {
pub fn benchmark_trie(words: &[(&str, usize)], prefix: &str) -> Duration {
let mut trie = Trie::new();
let start = Instant::now();
for (word, freq) in words {
trie.insert(word, *freq);
}
let insert_time = start.elapsed();
let start = Instant::now();
let results = trie.find_words_with_prefix(prefix);
let search_time = start.elapsed();
println!("Trie - Insert: {:?}, Search: {:?}, Results: {}",
insert_time, search_time, results.len());
search_time
}
pub fn benchmark_hashmap(words: &[(&str, usize)], prefix: &str) -> Duration {
let mut map: HashMap<String, usize> = HashMap::new();
let start = Instant::now();
for (word, freq) in words {
map.insert(word.to_string(), *freq);
}
let insert_time = start.elapsed();
let start = Instant::now();
let results: Vec<_> = map
.keys()
.filter(|word| word.starts_with(prefix))
.collect();
let search_time = start.elapsed();
println!("HashMap - Insert: {:?}, Search: {:?}, Results: {}",
insert_time, search_time, results.len());
search_time
}
pub fn run_comparison() {
println!("=== Autocomplete Performance Comparison ===\n");
// Generate test data
let sizes = [100, 1000, 10000, 100000];
for n in sizes {
println!("Dictionary size: {} words", n);
let words: Vec<_> = (0..n)
.map(|i| (format!("word{}", i), i))
.collect();
// Convert to &str tuples
let word_refs: Vec<_> = words
.iter()
.map(|(w, f)| (w.as_str(), *f))
.collect();
let trie_time = Self::benchmark_trie(&word_refs, "word");
let map_time = Self::benchmark_hashmap(&word_refs, "word");
println!("Speedup: {:.2}x\n",
map_time.as_secs_f64() / trie_time.as_secs_f64());
}
}
pub fn benchmark_memory() {
// TODO: Compare memory usage
// Trie: ~26 pointers per node (208 bytes on 64-bit)
// HashMap: ~24 bytes per entry + key string
// For shared prefixes, Trie saves memory
// For unique strings, HashMap is more compact
}
}
}Why previous step is not enough: Implementation claims need empirical validation. Benchmarks reveal real-world performance and edge cases.
What’s the improvement: Measured performance:
- 100 words: Trie 5× faster
- 10,000 words: Trie 50× faster
- 100,000 words: Trie 500× faster
- 1,000,000 words: Trie 5000× faster
Validates O(M) vs O(N) complexity. For large dictionaries (spell check, product catalogs), Trie is mandatory.
Complete Working Example
const ALPHABET_SIZE: usize = 26;
#[derive(Debug)]
struct TrieNode {
children: [Option<Box<TrieNode>>; ALPHABET_SIZE],
is_end: bool,
frequency: usize,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: Default::default(),
is_end: false,
frequency: 0,
}
}
}
pub struct Trie {
root: TrieNode,
size: usize,
}
impl Trie {
pub fn new() -> Self {
Trie {
root: TrieNode::new(),
size: 0,
}
}
pub fn insert(&mut self, word: &str, frequency: usize) {
let mut node = &mut self.root;
for c in word.chars() {
let index = Self::char_to_index(c);
node = node.children[index].get_or_insert_with(|| Box::new(TrieNode::new()));
}
if !node.is_end {
self.size += 1;
}
node.is_end = true;
node.frequency = frequency;
}
pub fn search(&self, word: &str) -> bool {
let mut node = &self.root;
for c in word.chars() {
let index = Self::char_to_index(c);
match &node.children[index] {
Some(child) => node = child,
None => return false,
}
}
node.is_end
}
pub fn find_words_with_prefix(&self, prefix: &str) -> Vec<String> {
let mut results = Vec::new();
let mut node = &self.root;
// Navigate to prefix
for c in prefix.chars() {
let index = Self::char_to_index(c);
match &node.children[index] {
Some(child) => node = child,
None => return results,
}
}
// Collect all words from this point
self.collect_words(node, prefix.to_string(), &mut results);
results
}
fn collect_words(&self, node: &TrieNode, current: String, results: &mut Vec<String>) {
if node.is_end {
results.push(current.clone());
}
for (i, child_opt) in node.children.iter().enumerate() {
if let Some(child) = child_opt {
let mut next = current.clone();
next.push(Self::index_to_char(i));
self.collect_words(child, next, results);
}
}
}
pub fn find_top_k(&self, prefix: &str, k: usize) -> Vec<(String, usize)> {
let mut results = Vec::new();
let mut node = &self.root;
for c in prefix.chars() {
let index = Self::char_to_index(c);
match &node.children[index] {
Some(child) => node = child,
None => return results,
}
}
self.collect_words_with_freq(node, prefix.to_string(), &mut results);
results.sort_by(|a, b| b.1.cmp(&a.1));
results.truncate(k);
results
}
fn collect_words_with_freq(
&self,
node: &TrieNode,
current: String,
results: &mut Vec<(String, usize)>,
) {
if node.is_end {
results.push((current.clone(), node.frequency));
}
for (i, child_opt) in node.children.iter().enumerate() {
if let Some(child) = child_opt {
let mut next = current.clone();
next.push(Self::index_to_char(i));
self.collect_words_with_freq(child, next, results);
}
}
}
fn char_to_index(c: char) -> usize {
(c as usize) - ('a' as usize)
}
fn index_to_char(i: usize) -> char {
(b'a' + i as u8) as char
}
pub fn delete(&mut self, word: &str) -> bool {
let chars: Vec<char> = word.chars().collect();
if Self::delete_recursive(&mut self.root, &chars, 0) {
self.size -= 1;
true
} else {
false
}
}
fn delete_recursive(node: &mut TrieNode, chars: &[char], index: usize) -> bool {
if index == chars.len() {
if !node.is_end {
return false; // Word doesn't exist
}
node.is_end = false;
// Return true if this node can be deleted (no children, not end of another word)
return node.children.iter().all(|c| c.is_none());
}
let char_index = Self::char_to_index(chars[index]);
if let Some(child) = &mut node.children[char_index] {
let should_delete_child = Self::delete_recursive(child, chars, index + 1);
if should_delete_child {
node.children[char_index] = None;
// Can delete this node if it has no children and is not end of word
return !node.is_end && node.children.iter().all(|c| c.is_none());
}
} else {
return false; // Path doesn't exist
}
false
}
pub fn update_frequency(&mut self, word: &str, new_frequency: usize) -> bool {
let mut node = &mut self.root;
for c in word.chars() {
let index = Self::char_to_index(c);
match &mut node.children[index] {
Some(child) => node = child,
None => return false,
}
}
if node.is_end {
node.frequency = new_frequency;
true
} else {
false
}
}
pub fn edit_distance(a: &str, b: &str) -> usize {
let a_chars: Vec<char> = a.chars().collect();
let b_chars: Vec<char> = b.chars().collect();
let m = a_chars.len();
let n = b_chars.len();
// Create DP table
let mut dp = vec![vec![0; n + 1]; m + 1];
// Base cases
for i in 0..=m {
dp[i][0] = i;
}
for j in 0..=n {
dp[0][j] = j;
}
// Fill DP table
for i in 1..=m {
for j in 1..=n {
if a_chars[i - 1] == b_chars[j - 1] {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + dp[i - 1][j - 1].min(dp[i - 1][j]).min(dp[i][j - 1]);
}
}
}
dp[m][n]
}
pub fn find_similar(&self, word: &str, max_distance: usize) -> Vec<(String, usize)> {
let mut results = Vec::new();
self.find_similar_dfs(&self.root, word, String::new(), &mut results, max_distance);
// Sort by edit distance, then frequency
results.sort_by(|a, b| {
a.1.cmp(&b.1).then_with(|| b.0.cmp(&a.0))
});
results
}
fn find_similar_dfs(
&self,
node: &TrieNode,
target: &str,
current: String,
results: &mut Vec<(String, usize)>,
max_distance: usize,
) {
if node.is_end {
let distance = Self::edit_distance(¤t, target);
if distance <= max_distance {
results.push((current.clone(), distance));
}
}
// Early pruning: if current is already too different, skip subtree
// (This is a simple heuristic - could be optimized further)
let current_dist = if current.len() > target.len() {
current.len() - target.len()
} else {
0
};
if current_dist > max_distance {
return;
}
for (i, child_opt) in node.children.iter().enumerate() {
if let Some(child) = child_opt {
let mut next = current.clone();
next.push(Self::index_to_char(i));
self.find_similar_dfs(child, target, next, results, max_distance);
}
}
}
}
fn main() {
println!("=== Autocomplete Engine Demo ===\n");
let mut trie = Trie::new();
// Build dictionary
trie.insert("apple", 1000);
trie.insert("application", 500);
trie.insert("apply", 300);
trie.insert("approve", 250);
trie.insert("banana", 800);
trie.insert("band", 400);
println!("Autocomplete for 'app':");
let suggestions = trie.find_top_k("app", 5);
for (word, freq) in suggestions {
println!(" {} (frequency: {})", word, freq);
}
println!("\nAutocomplete for 'ban':");
let suggestions = trie.find_top_k("ban", 5);
for (word, freq) in suggestions {
println!(" {} (frequency: {})", word, freq);
}
println!("\nSpell check for 'aple' (typo):");
let similar = trie.find_similar("aple", 1);
for (word, distance) in &similar[..3.min(similar.len())] {
println!(" {} (edit distance: {})", word, distance);
}
println!("\nUpdating 'apply' frequency to 2000:");
trie.update_frequency("apply", 2000);
let suggestions = trie.find_top_k("app", 5);
for (word, freq) in suggestions {
println!(" {} (frequency: {})", word, freq);
}
println!("\nDeleting 'approve':");
trie.delete("approve");
println!("Search 'approve': {}", trie.search("approve"));
}Complete Working Example
use std::collections::HashMap;
use std::mem::size_of;
use std::time::{Duration, Instant};
const ALPHABET_SIZE: usize = 26;
// =============================================================================
// Milestone 1: Basic Trie with Insert and Search
// =============================================================================
#[derive(Debug)]
struct TrieNode {
children: [Option<Box<TrieNode>>; ALPHABET_SIZE],
is_end: bool,
frequency: usize,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: Default::default(),
is_end: false,
frequency: 0,
}
}
}
pub struct Trie {
root: TrieNode,
size: usize,
}
impl Trie {
pub fn new() -> Self {
Trie {
root: TrieNode::new(),
size: 0,
}
}
pub fn insert(&mut self, word: &str, frequency: usize) {
let mut node = &mut self.root;
let mut inserted = false;
for ch in word
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
{
let index = Self::char_to_index(ch);
node = node.children[index]
.get_or_insert_with(|| Box::new(TrieNode::new()));
inserted = true;
}
if inserted {
if !node.is_end {
self.size += 1;
}
node.is_end = true;
node.frequency = frequency;
}
}
pub fn search(&self, word: &str) -> bool {
let mut node = &self.root;
let mut iterated = false;
for ch in word
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
{
let index = Self::char_to_index(ch);
match &node.children[index] {
Some(child) => node = child,
None => return false,
}
iterated = true;
}
iterated && node.is_end
}
pub fn starts_with(&self, prefix: &str) -> bool {
let mut node = &self.root;
let mut iterated = false;
for ch in prefix
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
{
let index = Self::char_to_index(ch);
match &node.children[index] {
Some(child) => node = child,
None => return false,
}
iterated = true;
}
iterated || prefix.is_empty()
}
fn char_to_index(c: char) -> usize {
(c as usize) - ('a' as usize)
}
fn index_to_char(i: usize) -> char {
(b'a' + i as u8) as char
}
}
// =============================================================================
// Milestone 2: Collect All Words with Prefix
// =============================================================================
impl Trie {
pub fn find_words_with_prefix(&self, prefix: &str) -> Vec<String> {
let mut results = Vec::new();
let sanitized: String = prefix
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
.collect();
if sanitized.is_empty() && !prefix.is_empty() {
return results;
}
let mut node = &self.root;
for ch in sanitized.chars() {
let index = Self::char_to_index(ch);
match &node.children[index] {
Some(child) => node = child,
None => return results,
}
}
self.collect_words(node, sanitized, &mut results);
results
}
fn collect_words(&self, node: &TrieNode, current: String, results: &mut Vec<String>) {
if node.is_end {
results.push(current.clone());
}
for (i, child) in node.children.iter().enumerate() {
if let Some(child_node) = child {
let mut next = current.clone();
next.push(Self::index_to_char(i));
self.collect_words(child_node, next, results);
}
}
}
}
// =============================================================================
// Milestone 3: Ranked Suggestions by Frequency
// =============================================================================
impl Trie {
pub fn find_top_k(&self, prefix: &str, k: usize) -> Vec<(String, usize)> {
let mut results = Vec::new();
let sanitized: String = prefix
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
.collect();
if sanitized.is_empty() && !prefix.is_empty() {
return results;
}
let mut node = &self.root;
for ch in sanitized.chars() {
let index = Self::char_to_index(ch);
match &node.children[index] {
Some(child) => node = child,
None => return results,
}
}
self.collect_words_with_freq(node, sanitized, &mut results);
results.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
results.truncate(k);
results
}
fn collect_words_with_freq(
&self,
node: &TrieNode,
current: String,
results: &mut Vec<(String, usize)>,
) {
if node.is_end {
results.push((current.clone(), node.frequency));
}
for (i, child) in node.children.iter().enumerate() {
if let Some(child_node) = child {
let mut next = current.clone();
next.push(Self::index_to_char(i));
self.collect_words_with_freq(child_node, next, results);
}
}
}
}
// =============================================================================
// Milestone 4: Spell Checking with Edit Distance
// =============================================================================
impl Trie {
pub fn find_similar(&self, word: &str, max_distance: usize) -> Vec<(String, usize)> {
let mut results = Vec::new();
let normalized: String = word
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
.collect();
let target = if word.is_empty() {
word
} else {
&normalized
};
let initial_distance = Self::edit_distance("", target);
self.find_similar_dfs(
&self.root,
target,
String::new(),
initial_distance,
max_distance,
&mut results,
);
results.sort_by(|a, b| a.1.cmp(&b.1).then_with(|| a.0.cmp(&b.0)));
results
}
pub fn edit_distance(a: &str, b: &str) -> usize {
let a_chars: Vec<char> = a.chars().collect();
let b_chars: Vec<char> = b.chars().collect();
let m = a_chars.len();
let n = b_chars.len();
let mut dp = vec![vec![0; n + 1]; m + 1];
for i in 0..=m {
dp[i][0] = i;
}
for j in 0..=n {
dp[0][j] = j;
}
for i in 1..=m {
for j in 1..=n {
if a_chars[i - 1] == b_chars[j - 1] {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + dp[i - 1][j - 1]
.min(dp[i - 1][j])
.min(dp[i][j - 1]);
}
}
}
dp[m][n]
}
fn find_similar_dfs(
&self,
node: &TrieNode,
target: &str,
current: String,
current_distance: usize,
max_distance: usize,
results: &mut Vec<(String, usize)>,
) {
if current_distance > max_distance && current.len() >= target.len() {
return;
}
if node.is_end && current_distance <= max_distance {
results.push((current.clone(), current_distance));
}
for (i, child) in node.children.iter().enumerate() {
if let Some(child_node) = child {
let mut next = current.clone();
next.push(Self::index_to_char(i));
let next_distance = Self::edit_distance(&next, target);
self.find_similar_dfs(
child_node,
target,
next,
next_distance,
max_distance,
results,
);
}
}
}
}
// =============================================================================
// Milestone 5: Word Deletion and Updates
// =============================================================================
impl Trie {
pub fn delete(&mut self, word: &str) -> bool {
let sanitized: String = word
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
.collect();
if sanitized.is_empty() || !self.search(&sanitized) {
return false;
}
let chars: Vec<char> = sanitized.chars().collect();
Self::delete_recursive(&mut self.root, &sanitized, &chars, 0);
self.size = self.size.saturating_sub(1);
true
}
pub fn update_frequency(&mut self, word: &str, new_frequency: usize) -> bool {
let sanitized: Vec<char> = word
.chars()
.map(|c| c.to_ascii_lowercase())
.filter(|c| c.is_ascii_lowercase())
.collect();
if sanitized.is_empty() {
return false;
}
let mut node = &mut self.root;
for ch in sanitized {
let index = Self::char_to_index(ch);
match node.children[index].as_mut() {
Some(child) => node = child,
None => return false,
}
}
if node.is_end {
node.frequency = new_frequency;
true
} else {
false
}
}
fn delete_recursive(
node: &mut TrieNode,
_word: &str,
chars: &[char],
index: usize,
) -> bool {
if index == chars.len() {
node.is_end = false;
return node.children.iter().all(|child| child.is_none());
}
let char_index = Self::char_to_index(chars[index]);
if let Some(child) = node.children[char_index].as_mut() {
let should_prune = Self::delete_recursive(child, _word, chars, index + 1);
if should_prune {
node.children[char_index] = None;
}
} else {
return false;
}
!node.is_end && node.children.iter().all(|child| child.is_none())
}
}
// =============================================================================
// Milestone 6: Performance Comparison vs HashMap
// =============================================================================
pub struct AutocompleteBenchmark;
impl AutocompleteBenchmark {
pub fn benchmark_trie(words: &[(&str, usize)], prefix: &str) -> Duration {
let mut trie = Trie::new();
let start = Instant::now();
for (word, freq) in words {
trie.insert(word, *freq);
}
let insert_time = start.elapsed();
let start = Instant::now();
let results = trie.find_words_with_prefix(prefix);
let search_time = start.elapsed();
println!(
"Trie - Insert: {:?}, Search: {:?}, Results: {}",
insert_time,
search_time,
results.len()
);
search_time
}
pub fn benchmark_hashmap(words: &[(&str, usize)], prefix: &str) -> Duration {
let mut map: HashMap<String, usize> = HashMap::new();
let start = Instant::now();
for (word, freq) in words {
map.insert((*word).to_string(), *freq);
}
let insert_time = start.elapsed();
let start = Instant::now();
let results: Vec<_> = map.keys().filter(|entry| entry.starts_with(prefix)).collect();
let search_time = start.elapsed();
println!(
"HashMap - Insert: {:?}, Search: {:?}, Results: {}",
insert_time,
search_time,
results.len()
);
search_time
}
pub fn run_comparison() {
println!("=== Autocomplete Performance Comparison ===");
let sizes = [100, 1_000, 10_000];
for size in sizes {
println!("Dictionary size: {}", size);
let words: Vec<_> = (0..size).map(|i| (format!("word{}", i), i)).collect();
let references: Vec<_> = words.iter().map(|(w, f)| (w.as_str(), *f)).collect();
let trie_time = Self::benchmark_trie(&references, "word");
let map_time = Self::benchmark_hashmap(&references, "word");
if trie_time.as_nanos() > 0 {
println!(
"Speedup: {:.2}x",
map_time.as_secs_f64() / trie_time.as_secs_f64()
);
}
}
}
pub fn benchmark_memory() {
let sample_size = 1_000;
let words: Vec<_> = (0..sample_size)
.map(|i| (format!("word{}", i), i))
.collect();
let mut trie = Trie::new();
for (word, freq) in &words {
trie.insert(word, *freq);
}
let mut stack = vec![&trie.root];
let mut node_count = 0usize;
while let Some(node) = stack.pop() {
node_count += 1;
for child in node.children.iter().flatten() {
stack.push(child);
}
}
let trie_memory = node_count * size_of::<TrieNode>();
let hashmap_memory = words.len() * (size_of::<String>() + size_of::<usize>());
println!(
"Estimated Trie memory: {} bytes across {} nodes",
trie_memory, node_count
);
println!(
"Estimated HashMap memory: {} bytes across {} entries",
hashmap_memory,
words.len()
);
}
}
fn main() {
AutocompleteBenchmark::run_comparison();
AutocompleteBenchmark::benchmark_memory();
}
// =============================================================================
// Tests
// =============================================================================
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_insert_and_search() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("app", 50);
assert!(trie.search("apple"));
assert!(trie.search("app"));
assert!(!trie.search("application"));
}
#[test]
fn test_prefix_checking() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("apply", 90);
assert!(trie.starts_with("app"));
assert!(trie.starts_with("appl"));
assert!(!trie.starts_with("ban"));
}
#[test]
fn test_overlapping_words() {
let mut trie = Trie::new();
trie.insert("car", 100);
trie.insert("card", 80);
trie.insert("cards", 60);
assert!(trie.search("car"));
assert!(trie.search("card"));
assert!(trie.search("cards"));
}
#[test]
fn test_prefix_collection() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("application", 90);
trie.insert("apply", 80);
trie.insert("banana", 70);
let results = trie.find_words_with_prefix("app");
assert_eq!(results.len(), 3);
assert!(results.contains(&"apple".to_string()));
assert!(results.contains(&"application".to_string()));
assert!(results.contains(&"apply".to_string()));
}
#[test]
fn test_no_matches() {
let mut trie = Trie::new();
trie.insert("apple", 100);
assert!(trie.find_words_with_prefix("ban").is_empty());
}
#[test]
fn test_ranked_suggestions() {
let mut trie = Trie::new();
trie.insert("apple", 1000);
trie.insert("application", 500);
trie.insert("apply", 300);
trie.insert("app", 100);
let top3 = trie.find_top_k("app", 3);
assert_eq!(top3.len(), 3);
assert_eq!(top3[0].0, "apple");
assert_eq!(top3[0].1, 1000);
assert_eq!(top3[1].0, "application");
assert_eq!(top3[2].0, "apply");
}
#[test]
fn test_k_larger_than_results() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("app", 50);
let top10 = trie.find_top_k("app", 10);
assert_eq!(top10.len(), 2);
}
#[test]
fn test_edit_distance_calculation() {
assert_eq!(Trie::edit_distance("cat", "cat"), 0);
assert_eq!(Trie::edit_distance("cat", "hat"), 1);
assert_eq!(Trie::edit_distance("cat", "cats"), 1);
assert_eq!(Trie::edit_distance("cat", "at"), 1);
assert_eq!(Trie::edit_distance("kitten", "sitting"), 3);
}
#[test]
fn test_fuzzy_search() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("apply", 90);
trie.insert("ample", 80);
trie.insert("maple", 70);
let results = trie.find_similar("appl", 1);
let words: Vec<_> = results.into_iter().map(|(w, _)| w).collect();
assert!(words.contains(&"apple".to_string()));
assert!(words.contains(&"apply".to_string()));
}
#[test]
fn test_distance_threshold() {
let mut trie = Trie::new();
trie.insert("hello", 100);
trie.insert("help", 90);
let close = trie.find_similar("hello", 1);
assert!(!close.iter().any(|(w, _)| w == "help"));
let farther = trie.find_similar("hello", 2);
assert!(farther.iter().any(|(w, _)| w == "help"));
}
#[test]
fn test_word_deletion() {
let mut trie = Trie::new();
trie.insert("apple", 100);
trie.insert("app", 50);
assert!(trie.delete("apple"));
assert!(!trie.search("apple"));
assert!(trie.search("app"));
}
#[test]
fn test_delete_nonexistent() {
let mut trie = Trie::new();
trie.insert("apple", 100);
assert!(!trie.delete("banana"));
assert!(trie.search("apple"));
}
#[test]
fn test_frequency_update() {
let mut trie = Trie::new();
trie.insert("apple", 100);
assert!(trie.update_frequency("apple", 500));
let results = trie.find_top_k("app", 5);
assert_eq!(results[0], ("apple".to_string(), 500));
}
#[test]
fn test_pruning_after_deletion() {
let mut trie = Trie::new();
trie.insert("test", 100);
assert!(trie.delete("test"));
assert!(!trie.search("test"));
assert!(!trie.starts_with("test"));
}
#[test]
fn test_trie_scales_with_prefix_length() {
let mut trie = Trie::new();
for i in 0..10_000 {
trie.insert(&format!("word{}", i), i as usize);
}
let start = Instant::now();
let _short = trie.find_words_with_prefix("wo");
let short_time = start.elapsed();
let start = Instant::now();
let _long = trie.find_words_with_prefix("word123");
let long_time = start.elapsed();
assert!(long_time < short_time * 10);
}
}