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.
- The method returns an
- Exact match search
- The method finds a value associated with an exact match key as a
Option
.
- The method finds a value associated with an exact match key as a
Requirements
- Rust version >= 1.46.0
Usage
See also example code for more details.
Build a double-array trie
use DoubleArrayBuilder;
// make a keyset which have key-value pairs
let keyset = &;
// build a double-array trie binary
let da_bytes: = build;
Search entries by keys
use DoubleArray;
// create a double-array trie instance
let da = new;
// exact match search
for in keyset
assert_eq!;
assert_eq!;
// common prefix search
assert_eq!;
assert_eq!;
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 29 bits wide, so it can represent up to
~536M nodes.
- It means this limitation results in the size upper bound ~2GB 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.