Skip to content
/ ptrie Public
forked from aserebryakov/trie-rs

πŸŽ„ Generic trie data structure (prefix tree) in Rust, with functions to search for common prefixes and postfixes

License

Notifications You must be signed in to change notification settings

vemonet/ptrie

This branch is 45 commits ahead of aserebryakov/trie-rs:master.

Folders and files

NameName
Last commit message
Last commit date

Latest commit

3666728 Β· Dec 9, 2024
Dec 9, 2024
Dec 23, 2023
Dec 9, 2024
Aug 22, 2024
Dec 21, 2023
Dec 21, 2023
Dec 23, 2023
Dec 9, 2024
Aug 22, 2024
Dec 9, 2024
Jul 9, 2018
Aug 22, 2024
Dec 21, 2023

Repository files navigation

πŸŽ„ Prefix Trie

Crates.io Test Release Documentation Codecov status MIT license

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

// Find all potential prefixes
let prefixes = trie.find_prefixes("abcd".bytes());
assert_eq!(prefixes, vec![&"A", &"AB", &"ABC"]);

// Find the longest prefix
let longest = trie.find_longest_prefix("abcd".bytes());
assert_eq!(longest, Some("ABC").as_ref());

// Find longest with length
if let Some((length, prefix)) = trie.find_longest_prefix_len("abcd".bytes()) {
    println!("Longest prefix: {} {}", prefix, length);
}

πŸ” 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");

// Get a key
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());

// Iterate the trie
for (k, v) in &trie {
    println!("kv: {:?} {}", k, v);
}

// Remove a key
trie.remove("app".bytes());
assert!(!trie.contains_key("app".bytes()));

🏷️ 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

MIT License

About

πŸŽ„ Generic trie data structure (prefix tree) in Rust, with functions to search for common prefixes and postfixes

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Rust 100.0%