Skip to main content

Crate pruning_radix_trie_rs

Crate pruning_radix_trie_rs 

Source
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§

PruningRadixTrie
Pruning radix trie for top-k prefix completion.