Struct Searcher 

pub struct Searcher { /* private fields */ }

A reusable search context. It keeps its priority queue and scratch buffers across queries; the returned Output is still allocated per query.

Implementations

impl Searcher

pub fn new() -> Self

Creates an empty context.

pub fn search( &mut self, trie: &Trie, cm: &CostModel, q: &[u8], cfg: &SearchConfig, ) -> Result<Output, SearchError>

Returns the cfg.k best terms within cfg.budget, best first, in the order set by cfg.ranking.

q is UTF-8 and is compared per code point with the terms, as it is: it must already be in the form the terms are stored in (lowercase for a dictionary of lowercase terms). Searcher::search_text normalises it for a trie built with Trie::build_normalized. A byte that is not part of valid UTF-8 is a symbol of its own that matches no term.

pub fn search_text( &mut self, trie: &Trie, cm: &CostModel, q: &str, cfg: &SearchConfig, ) -> Result<Output, SearchError>

Searcher::search for text: q is normalised with the normaliser of trie (Trie::build_normalized) first, so terms and queries are folded identically. For a trie built with Trie::build this is search(trie, cm, q.as_bytes(), cfg). MAX_QUERY_LEN applies to the normalised query.

use keyhammer::cost::CostModel;
use keyhammer::search::{SearchConfig, Searcher};
use keyhammer::text::Normalizer;
use keyhammer::trie::Trie;

let items = [("São Paulo", 10), ("Straße", 5), ("Crème brûlée", 7)];
let trie = Trie::build_normalized(&items, &Normalizer::new()).unwrap();
let mut s = Searcher::new();
let cm = CostModel::qwerty();
let cfg = SearchConfig::default();
let first = |s: &mut Searcher, q: &str| {
    let out = s.search_text(&trie, &cm, q, &cfg).unwrap();
    (trie.input_index(out.hits[0].id), out.hits[0].cost)
};
assert_eq!(first(&mut s, "SAO PAULO"), (0, 0));
assert_eq!(first(&mut s, "strasse"), (1, 0));
assert_eq!(first(&mut s, "creme brulee"), (2, 0));
assert_eq!(first(&mut s, "sao paolo"), (0, 16)); // one typo

pub fn search_prefix_text( &mut self, trie: &Trie, cm: &CostModel, q: &str, cfg: &SearchConfig, ) -> Result<Output, SearchError>

Searcher::search_prefix for text, with the query normalised as by Searcher::search_text.

use keyhammer::cost::CostModel;
use keyhammer::search::{SearchConfig, Searcher};
use keyhammer::text::Normalizer;
use keyhammer::trie::Trie;

let items = [("Ação", 10), ("Acapulco", 5)];
let trie = Trie::build_normalized(&items, &Normalizer::new()).unwrap();
let out = Searcher::new()
    .search_prefix_text(&trie, &CostModel::qwerty(), "AÇÃ", &SearchConfig::default())
    .unwrap();
assert_eq!(trie.term(out.hits[0].id), "acao");
assert_eq!(out.hits[0].cost, 0);

pub fn highlight( &mut self, trie: &Trie, cm: &CostModel, q: &[u8], hit: &Hit, source: &str, mode: HighlightMode, ) -> Result<Highlight, HighlightError>

The characters of a hit that the query matched, as ranges of source in code points, UTF-8 bytes and UTF-16 units (see crate::highlight and docs/design/highlighting.md).

q is the query exactly as given to Searcher::search (HighlightMode::Whole) or Searcher::search_prefix (HighlightMode::Prefix), and hit one of the hits that search returned. source is the string the caller inserted for the term: for a trie from Trie::build_normalized, the entry items[trie.input_index(hit.id)]; for a trie from Trie::build, the term itself (Trie::term(hit.id)). It must normalise, with the trie’s normaliser if it has one, to the hit’s term.

The alignment is recomputed on the full matrix and walked back; its cost always equals hit.cost (Highlight::cost). The search itself does no highlighting work: call this only for the hits you show. The work per hit is at most (m + 1) * (m + 9) matrix cells for a query of m symbols (Highlight::cells), plus a pass over source.

Errors

HighlightError::QueryTooLong as for the search, HighlightError::UnknownTerm if hit.id is not a term of trie, HighlightError::SourceMismatch if source does not normalise to the term, HighlightError::CostMismatch if the alignment does not cost hit.cost (a hit of another query, cost model or mode).

Panics

Never, for any input.

Examples

use keyhammer::cost::CostModel;
use keyhammer::highlight::HighlightMode;
use keyhammer::search::{SearchConfig, Searcher};
use keyhammer::trie::Trie;

let trie = Trie::build(&[("javascript", 10), ("java", 30)]).unwrap();
let cm = CostModel::qwerty();
let mut s = Searcher::new();
let cfg = SearchConfig::default();

// "javasript" skips the "c": everything else is highlighted.
let out = s.search(&trie, &cm, b"javasript", &cfg).unwrap();
let hit = &out.hits[0];
let term = trie.term(hit.id);
let h = s
    .highlight(&trie, &cm, b"javasript", hit, term, HighlightMode::Whole)
    .unwrap();
let spans: Vec<&str> = h.ranges.iter().map(|r| &term[r.utf8.clone()]).collect();
assert_eq!(spans, ["javas", "ript"]);
assert_eq!(h.cost, hit.cost);

// Prefix mode: only the typed prefix is highlighted.
let out = s.search_prefix(&trie, &cm, b"jav", &cfg).unwrap();
for hit in &out.hits {
    let term = trie.term(hit.id);
    let h = s
        .highlight(&trie, &cm, b"jav", hit, term, HighlightMode::Prefix)
        .unwrap();
    assert_eq!(h.ranges[0].chars, 0..3);
    assert_eq!(h.aligned.chars, 0..3);
}

pub fn highlight_text( &mut self, trie: &Trie, cm: &CostModel, q: &str, hit: &Hit, source: &str, mode: HighlightMode, ) -> Result<Highlight, HighlightError>

Searcher::highlight for a hit of Searcher::search_text (HighlightMode::Whole) or Searcher::search_prefix_text (HighlightMode::Prefix): q is normalised with the trie’s normaliser first, as those searches do.

Errors

As for Searcher::highlight.

Panics

Never, for any input.

Examples

use keyhammer::cost::CostModel;
use keyhammer::highlight::HighlightMode;
use keyhammer::search::{SearchConfig, Searcher};
use keyhammer::text::Normalizer;
use keyhammer::trie::Trie;

let items = [("Straße", 1)];
let trie = Trie::build_normalized(&items, &Normalizer::new()).unwrap();
let cm = CostModel::qwerty();
let mut s = Searcher::new();
let out = s.search_text(&trie, &cm, "STRASE", &SearchConfig::default()).unwrap();
let hit = &out.hits[0];
let h = s
    .highlight_text(&trie, &cm, "STRASE", hit, items[0].0, HighlightMode::Whole)
    .unwrap();
// One of the two "s" of "ß" was typed: "ß" counts as typed.
assert_eq!(h.ranges.len(), 1);
assert_eq!(h.ranges[0].chars, 0..6);
assert_eq!(h.ranges[0].utf8, 0..7);

pub fn search_prefix( &mut self, trie: &Trie, cm: &CostModel, q: &[u8], cfg: &SearchConfig, ) -> Result<Output, SearchError>

Prefix (autocomplete) search: returns the cfg.k best terms that start with something within cfg.budget of the query, best first.

The cost of a term is the smallest weighted edit cost between the whole query and any prefix of the term (the empty prefix included), so the typed text may have typos while the rest of the term is free. The order is the one of Searcher::search: Ranking cost, then higher weight, then lower term id, and Hit::cost is that exact prefix cost. A hit is the full term; the length of the matched prefix is not reported. An empty query matches every term at cost 0, so the result is the k heaviest terms.

Configuration fields keep their meaning: budget bounds the prefix cost, tsb selects the subtree bound (results never change with it), max_nodes limits expanded trie nodes, including nodes expanded without a row (see docs/design/prefix-mode.md); Stats::truncated tells if it stopped the search, and the hits returned are then still the first ones of the exact order.

q is read as for Searcher::search.

use keyhammer::cost::CostModel;
use keyhammer::search::{SearchConfig, Searcher};
use keyhammer::trie::Trie;

let trie = Trie::build(&[("javascript", 10), ("java", 30), ("python", 50)]).unwrap();
let mut s = Searcher::new();
// "javs" types "s" for "a" (neighbouring keys); "java" starts both terms.
let out = s
    .search_prefix(&trie, &CostModel::qwerty(), b"javs", &SearchConfig::default())
    .unwrap();
let terms: Vec<&str> = out.hits.iter().map(|h| trie.term(h.id)).collect();
assert_eq!(terms, ["java", "javascript"]);

Trait Implementations

impl Default for Searcher

fn default() -> Searcher

Returns the “default value” for a type.