#pruning #trie

pruning_radix_trie

Rust implementation of Pruning Radix Trie, originally by Wolf Garbe

4 releases (2 stable)

1.0.1 Sep 15, 2024
1.0.0 Feb 23, 2023
0.3.0 Sep 6, 2022
0.2.2 Sep 5, 2022

#1 in #pruning

Download history 2/week @ 2024-07-29 119/week @ 2024-09-09 70/week @ 2024-09-16 15/week @ 2024-09-23 8/week @ 2024-09-30

130 downloads per month

MIT license

28KB
672 lines

Pruning Radix Trie

Rust implementation of Pruning Radix Trie, originally by Wolf Garbe (see credits/PruningRadixTrieLicense.txt).

Usage

Add terms with payloads to the trie with:

pub fn add(&mut self, term: &str, payload: T, weight: U);

After which you can prefix match with:

pub fn find(&self, prefix: &str, top_k: usize) 
    -> Vec<Result<T,U>>

Results are returned in descending order based on weight.

Example

use pruning_radix_trie::PruningRadixTrie;

fn main() {
    let mut trie = PruningRadixTrie::new();
    trie.add("heyo", vec![1, 2, 3], 5);
    trie.add("hello", vec![4, 5, 6], 10);
    trie.add("hej", vec![7, 8, 9], 20);

    let results = trie.find("he", 10);

    for Result { term, payload, weight } in results {
        println!("{:10}{:?}{:>4}", term, payload, weight);
    }
    //hej       [7, 8, 9]  20
    //hello     [4, 5, 6]  10
    //heyo      [1, 2, 3]   5
}

Testing

Measuring code coverage

N.B.: At the moment, the nightly channel of Rust is required.

First of all, install grcov

cargo install grcov

Second, install the llvm-tools Rust component (llvm-tools-preview for now, it might become llvm-tools soon):

rustup component add llvm-tools-preview

To run tests with code coverage run

bash run_source_cov.sh

A html coverage report will be generated in ./target/debug/coverage/

See rust-code-coverage-sample for details.

Dependencies

~490KB