Module trie_rs::inc_search

Incremental search

Motivation

The motivation for this struct is for “online” or interactive use cases. One often accumulates input to match against a trie. Using the standard exact_match() faculties which has a time complexity of O(m log n) where m is the query string length and n is the number of entries in the trie. Consider this loop where we simulate accumulating a query.

use trie_rs::Trie;

let q = "appli"; // query string
let mut is_match: bool;
let trie = Trie::from_iter(vec!["appli", "application"]);
for i in 0..q.len() - 1 {
    assert!(!trie.exact_match(&q[0..i]));
}
assert!(trie.exact_match(q));

Building the query one “character” at a time and exact_match()ing each time, the loop has effectively complexity of O(m² log n).

Using the incremental search, the time complexity of each query is O(log n) which returns an Answer enum.

let q = "appli"; // query string
let inc_search = trie.inc_search();
let mut is_match: bool;
for i = 0..q.len() {
    is_match = inc_search.query(q[i]).unwrap().is_match();
}

This means the above code restores the time complexity of O(m log n) for the loop.

Structs

• IncSearch
  An incremental search of the trie.

Enums

• Answer
  A “matching” answer to an incremental search on a partial query.

Type Aliases

• Position
  Search position in the trie.