Skip to main content

Introduction

Keyhammer is a typo-tolerant search engine for short strings (words, names, identifiers). Given a dictionary of weighted terms and a possibly misspelled query, it returns the top-k terms of lowest edit cost. Edit costs are keyboard-aware: hitting a neighbouring key on a QWERTY layout, or repeating a letter, costs less than an arbitrary substitution.

The core crate, keyhammer, is no_std (it needs alloc), forbids unsafe code and has no runtime dependencies.

Status​

Keyhammer is an unpublished M0 prototype. Please read the results before relying on it:

  • The search is exact: it returns the same top-k as a brute-force oracle, and the test suite checks this.
  • It was much faster than the previous engine in the M0 benchmark (one machine; see Results). Ranking quality versus a simple edit-distance-plus-frequency baseline is reported there too. Both are measured on one machine, 300 typo pairs and one corpus, with provisional costs, so read the caveats before drawing conclusions.
  • The cost table is provisional and has not been calibrated.
  • The project claims no novelty: the ingredients are published work (see prior art).
  • The engine currently expects lowercase ASCII (a-z) and compares other bytes verbatim. Unicode and case folding are not implemented yet.
  • Nothing is published to crates.io or npm, and the API is unstable.

You can try the engine in your browser on the live demo page, which runs the core compiled to WebAssembly on a small sample dictionary or on terms you paste.

Quick example​

This is the example from the crate documentation, which is compiled and run as a doc test.

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

let trie = Trie::build(&[
    ("javascript", 10),
    ("typescript", 10),
    ("python", 10),
    ("rust", 10),
    ("java", 10),
])
.unwrap();
let costs = CostModel::qwerty();
let mut searcher = Searcher::new();

// "javasript" skips the 'c' of "javascript".
let out = searcher
    .search(&trie, &costs, b"javasript", &SearchConfig::default())
    .unwrap();
let best = &out.hits[0];
assert_eq!(trie.term(best.id), "javascript");
assert_eq!(best.cost, 16);

Costs are fixed point: 16 is one ordinary edit, so the default budget of 32 allows about two edits. The subtree signature bound is on by default (tsb: true; set tsb: false to turn it off); it prunes work without changing the results (see How it works).

For higher recall at a latency cost, SearchConfig::high_recall() is the default with a budget of 48 and the subtree bound on. In the repository's benchmark (300 Birkbeck typo pairs, one machine, median of three runs) it found the right word more often. Compared with the default budget (bound on in both), it expanded about 4.6-5.2 times the nodes and had about 5.5-7.3 times the p95 latency (about 5.2-7.5 times with the bound off); measure it on your own dictionary. The largest accepted budget is 64.

Where to go next​