🎄 前缀 Trie

PTrie 是一个无依赖项的泛型前缀树数据结构实现，适用于在字符串等对象集合中快速高效地搜索前缀和后缀。

结构定义为 Trie<K, V>，其中 K 表示每个节点中的键类型（索引链的迭代器），而 V 是相关值类型（键指向的任何对象）。

💭 动机

前缀树特别适用于涉及公共前缀识别和检索的操作，使其成为需要快速高效前缀搜索功能的应用的理想选择。

🚀 使用方法

结果按长度升序排序。

✨ 查找前缀

您可以返回与给定字符串匹配的所有前缀，或直接检索最长的前缀。

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());

🔍 查找后缀

您还可以在前缀树中查找所有后缀，例如，所有以给定字符串为前缀并扩展的字符串。

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"]);

🔑 基于键的检索函数

该库提供检查键是否存在、检索相关值或迭代前缀树节点的函数。

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);
}

🏷️ 功能

添加了 serde 功能，将 Serde Serialize 和 Deserialize 特性添加到 Trie 和 TrieNode 结构。

ptrie = { version = "0.6", features = ["serde"] }

🛠️ 贡献

欢迎贡献，请查阅 CONTRIBUTING.md 了解如何运行开发中的项目。

📜 变更日志

变更日志可在 CHANGELOG.md 中查看。

⚖️ 许可协议

MIT 许可协议