Expand description
§Pruning Radix Trie
A radix trie for top-k prefix completion over a term -> frequency dictionary.
Every node stores the maximum frequency found in its subtree, and children are
kept in descending order of their bound (own count or subtree maximum). During
lookup, whole branches are skipped (pruned) as soon as they cannot beat the
current k-th best result. The trie is mutable: terms can be added at any time
and queried immediately.
use pruning_radix_trie::PruningRadixTrie;
let mut trie = PruningRadixTrie::new();
trie.add_term("the", 100);
trie.add_term("their", 70);
trie.add_term("there", 50);
let (top, prefix_count) = trie.get_top_k_terms_for_prefix("the", 2, true);
assert_eq!(top, vec![("the".to_string(), 100), ("their".to_string(), 70)]);
assert_eq!(prefix_count, 100);Structs§
- Pruning
Radix Trie - Pruning radix trie for top-k prefix completion.