Struct crawdad::trie::Trie

pub struct Trie { /* private fields */ }

A standard trie form that often provides the fastest queries.

Implementations

impl Trie

pub fn from_keys<I, K>(keys: I) -> Result<Self> where
    I: IntoIterator<Item = K>,
    K: AsRef<str>, 

Creates a new Trie from input keys.

Values in [0..n-1] will be associated with keys in the lexicographical order, where n is the number of keys.

Arguments

• keys: Sorted list of string keys.

Errors

CrawdadError will be returned when

• keys is empty,
• keys contains empty strings,
• keys contains duplicate keys,
• the scale of keys exceeds the expected one, or
• the scale of the resulting trie exceeds the expected one.

Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(keys).unwrap();

assert_eq!(trie.num_elems(), 8);

pub fn from_records<I, K>(records: I) -> Result<Self> where
    I: IntoIterator<Item = (K, u32)>,
    K: AsRef<str>, 

Creates a new Trie from input records.

Arguments

• records: Sorted list of key-value pairs.

Errors

CrawdadError will be returned when

• records is empty,
• records contains empty strings,
• records contains duplicate keys,
• the scale of keys exceeds the expected one, or
• the scale of the resulting trie exceeds the expected one.

Examples

use crawdad::Trie;

let records = vec![("世界", 2), ("世界中", 3), ("国民", 2)];
let trie = Trie::from_records(records).unwrap();

assert_eq!(trie.num_elems(), 8);

pub fn serialize_to_vec(&self) -> Vec<u8>

Serializes the data structure into a Vec.

Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();
let bytes = trie.serialize_to_vec();

pub fn deserialize_from_slice(source: &[u8]) -> (Self, &[u8])

Deserializes the data structure from a given byte slice.

Arguments

• source - A source byte slice.

Returns

A tuple of the data structure and the slice not used for the deserialization.

Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();

let bytes = trie.serialize_to_vec();
let (other, _) = Trie::deserialize_from_slice(&bytes);

assert_eq!(trie.io_bytes(), other.io_bytes());

pub fn exact_match<I>(&self, key: I) -> Option<u32> where
    I: IntoIterator<Item = char>, 

Returns a value associated with an input key if exists.

Arguments

• key: Search key.

Examples

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();

assert_eq!(trie.exact_match("世界中".chars()), Some(1));
assert_eq!(trie.exact_match("日本中".chars()), None);

pub const fn common_prefix_search<I>(
    &self,
    haystack: I
) -> CommonPrefixSearchIter<'_, I>

Returns an iterator for common prefix search.

The iterator reports all occurrences of keys starting from an input haystack, where an occurrence consists of its associated value and ending positoin in characters.

Examples

You can find all occurrences of keys in a haystack by performing common prefix searches at all starting positions.

use crawdad::Trie;

let keys = vec!["世界", "世界中", "国民"];
let trie = Trie::from_keys(&keys).unwrap();

let haystack: Vec<char> = "国民が世界中にて".chars().collect();
let mut matches = vec![];

for i in 0..haystack.len() {
    for (v, j) in trie.common_prefix_search(haystack[i..].iter().copied()) {
        matches.push((v, i..i + j));
    }
}

assert_eq!(
    matches,
    vec![(2, 0..2), (0, 3..5), (1, 3..6)]
);

pub fn heap_bytes(&self) -> usize

Returns the total amount of heap used by this automaton in bytes.

pub fn io_bytes(&self) -> usize

Returns the total amount of bytes to serialize the data structure.

pub fn num_elems(&self) -> usize

Returns the number of reserved elements.

pub fn num_vacants(&self) -> usize

Returns the number of vacant elements.

Note

It takes O(num_elems) time.