#string-search #trie #double-array #cedar #text-search #ported #tested

cedarwood

efficiently-updatable double-array trie in Rust (ported from cedar)

15 releases

0.4.6 Oct 4, 2022
0.4.5 Sep 23, 2021
0.4.4 Dec 29, 2019
0.4.3 Nov 20, 2019
0.1.2 Jul 11, 2019

#230 in Data structures

Download history 3558/week @ 2023-11-20 3414/week @ 2023-11-27 3093/week @ 2023-12-04 2995/week @ 2023-12-11 3283/week @ 2023-12-18 2812/week @ 2023-12-25 2963/week @ 2024-01-01 3112/week @ 2024-01-08 3113/week @ 2024-01-15 3014/week @ 2024-01-22 3368/week @ 2024-01-29 2897/week @ 2024-02-05 3212/week @ 2024-02-12 2855/week @ 2024-02-19 2825/week @ 2024-02-26 2948/week @ 2024-03-04

12,147 downloads per month
Used in 22 crates (4 directly)

BSD-2-Clause

53KB
1K SLoC

cedarwood

Efficiently-updatable double-array trie in Rust (ported from cedar). This library is tested with reasonably enough of randomized tests, but it is considered as beta since it is not yet tested in high-pressured production environment. Please let me know if you have good use cases to prove its stability.

Build Status codecov Crates.io docs.rs

Installation

Add it to your Cargo.toml:

[dependencies]
cedarwood = "0.4"

then you are good to go. If you are using Rust 2015 you have to extern crate cedarwood to your crate root as well.

Example

let dict = vec![
    "a",
    "ab",
    "abc",
    "アルゴリズム",
    "データ",
    "構造",
    "",
    "网球",
    "网球拍",
    "",
    "中华",
    "中华人民",
    "中华人民共和国",
];
let key_values: Vec<(&str, i32)> = dict.into_iter().enumerate().map(|(k, s)| (s, k as i32)).collect();
let mut cedar = Cedar::new();
cedar.build(&key_values);

let result: Vec<i32> = cedar.common_prefix_search("abcdefg").iter().map(|x| x.0).collect();
assert_eq!(vec![0, 1, 2], result);

let result: Vec<i32> = cedar
    .common_prefix_search("网球拍卖会")
    .iter()
    .map(|x| x.0)
    .collect();
assert_eq!(vec![6, 7, 8], result);

let result: Vec<i32> = cedar
    .common_prefix_search("中华人民共和国")
    .iter()
    .map(|x| x.0)
    .collect();
assert_eq!(vec![9, 10, 11, 12], result);

let result: Vec<i32> = cedar
    .common_prefix_search("データ構造とアルゴリズム")
    .iter()
    .map(|x| x.0)
    .collect();
assert_eq!(vec![4], result);

To run benchmark tests

cargo bench 

License

This work is released under the BSD-2 license, following the original license of C++ cedar. A copy of the license is provided in the LICENSE file.

Reference

Dependencies

~76KB