Yada: Yet Another Double-Array

Yada is a yet another double-array trie library aiming for fast search and compact data representation.

Features

Build static double-array tries
- Yada adopts the compact binary representation of double-array nodes like Darts-clone.
Common prefix search
- The method returns an Iterator that is an effective way to find multiple values without heap allocation.
Exact match search
- The method finds a value associated with an exact match key as a Option.

Requirements

Rust version >= 1.46.0

Usage

Build a double-array trie

```rust use yada::builder::DoubleArrayBuilder;

// make a keyset which have key-value pairs let keyset = &[ ("a".asbytes(), 0), ("ab".asbytes(), 1), ("abc".asbytes(), 2), ("b".asbytes(), 3), ("bc".asbytes(), 4), ("c".asbytes(), 5), ];

// build a double-array trie binary let da_bytes: Option> = DoubleArrayBuilder::build(keyset); ```

Search entries by keys

```rust use yada::DoubleArray;

// create a double-array trie instance let da = DoubleArray::new(da_bytes.unwrap());

// exact match search for (key, value) in keyset { asserteq!(da.exactmatchsearch(key), Some(*value as u32)); } asserteq!(da.exactmatchsearch("abc".asbytes()), Some(2)); asserteq!(da.exactmatchsearch("abcd".as_bytes()), None);

// common prefix search asserteq!( da.commonprefixsearch("abcd".asbytes()) .collect::>(), vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc", value and key length ); asserteq!( da.commonprefixsearch("d".asbytes()).collect::>(), vec![] // don't match ); ```

Limitations

The value must be represented as a 31 bit unsigned integer, typed u32.
- Yada uses the most significant bit (MSB) as a flag to distinguish between a value node and others.
The offset of an double-array node is 23 bit wide, so it can only represent up to ~8.3M nodes.
- It means this limitation results in the size upper bound ~33 MB of double-arrays.

License

Licensed under either of

Apache License, Version 2.0 (LICENSE-APACHE)
MIT license (LICENSE-MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.