Expand description
π Prefix Trie
PTrie
is a generic implementation of the trie data structure with no dependencies, tailored for easy and efficient prefix and postfix search within a collection of objects, such as strings.
The structure is defined as Trie<K, V>
, where K
represents the type of keys in each node (an iterator of the chain to index), and V
is the type of the associated values (any object to which the key points to).
Β§π Motivation
The trie is particularly effective for operations involving common prefix identification and retrieval, making it a good choice for applications that require fast and efficient prefix-based search functionalities.
Β§π Usage
Results are sorted in ascending order of their length.
Β§β¨ Find prefixes
You can return all prefixes in the trie that matches a given string, or directly retrieve the longest prefix.
use ptrie::Trie;
let mut trie = Trie::new();
trie.insert("a".bytes(), "A");
trie.insert("ab".bytes(), "AB");
trie.insert("abc".bytes(), "ABC");
trie.insert("abcde".bytes(), "ABCDE");
let prefixes = trie.find_prefixes("abcd".bytes());
assert_eq!(prefixes, vec![&"A", &"AB", &"ABC"]);
let longest = trie.find_longest_prefix("abcd".bytes());
assert_eq!(longest, Some("ABC").as_ref());
Β§π Find postfixes
You can also find all postfixes in the trie, e.g. all strings which have the given string as a prefix, and extends it.
use ptrie::Trie;
let mut trie = Trie::new();
trie.insert("app".bytes(), "App");
trie.insert("apple".bytes(), "Apple");
trie.insert("applet".bytes(), "Applet");
trie.insert("apricot".bytes(), "Apricot");
let strings = trie.find_postfixes("app".bytes());
assert_eq!(strings, vec![&"App", &"Apple", &"Applet"]);
Β§π Key-based retrieval functions
The crate provides functions to check for the existence of a key, to retrieve the associated value, or iterate the trie nodes.
use ptrie::Trie;
let mut trie = Trie::new();
trie.insert("app".bytes(), "App");
trie.insert("applet".bytes(), "Applet");
assert!(trie.contains_key("app".bytes()));
assert!(!trie.contains_key("not_existing_key".bytes()));
assert_eq!(trie.get("app".bytes()), Some("App").as_ref());
assert_eq!(trie.get("none".bytes()), None.as_ref());
for (k, v) in trie.iter() {
println!("kv: {:?} {}", k, v);
}
Β§π·οΈ Features
The serde
feature adds Serde Serialize
and Deserialize
traits to the Trie
and TrieNode
struct.
ptrie = { version = "0.6", features = ["serde"] }
Β§π οΈ Contributing
Contributions are welcome, checkout the CONTRIBUTING.md
for instructions to run the project in development.
Β§π Changelog
Changelog available in the CHANGELOG.md
.
Β§βοΈ License
Re-exportsΒ§
pub use trie::Trie;