simsearch

simsearch is a small, dependency-light Rust crate that builds an in-memory fuzzy search index for embedding directly into applications. It combines a positional inverted index with Jaro-Winkler typo tolerance and prefix matching, then ranks results with a composite relevance score that weighs match quality, term coverage, proximity, exactness, position, and specificity.

The crate is designed for embedded use cases such as autocomplete, command palettes, and small-dataset search, where standing up an external search service is overkill. Version 0.4 reworked the public API around a single Index<Id> type, insert_parts for multi-field entries, and scored Hit<Id> results, with optional serde support for persisting the index.

What You Get

• A dependency-light Index<Id> type with insert, insert_parts, search, remove, and clear methods.
• Configurable Options for result limit, prefix search, typo tolerance, case sensitivity, and custom token separators.
• Scored Hit<Id> results in a normalized 0.0-1.0 range, sorted by relevance with insertion order as a tie-breaker.
• An interactive books example demonstrating live search over a real dataset.

Common Use Cases

• Autocomplete and search-as-you-type inputs
• Command palette / fuzzy command matching
• Client-side or embedded document/title search
• Fuzzy matching over small in-memory datasets such as contacts, tags, or items

Under The Hood

Architecture The crate is a single-file core (src/lib.rs) built around an Index<Id> struct holding a positional inverted index (reverse_map: term to a per-document posting list of positions), a forward_map (document id to its tokens) for re-ranking, and a BTreeSet<String> of terms enabling ordered prefix range queries. A search tokenizes the query, expands each token into candidate terms (exact match, prefix range via terms.range(), and typo-tolerant scan of all terms via Jaro-Winkler), collects per-document token matches, then runs select_best_matches — a pruned beam search over AssignmentState combinations bounded by prune_assignment_states — to choose a non-overlapping, ordered subset of matches per document before computing a weighted composite score and truncating to Options::limit. There are no layered abstractions or dependency injection; it is a flat, self-contained algorithmic core, and the assignment-state pruning heuristic and scoring weights are the highest-leverage points for behavior changes.

Tech Stack Pure Rust, 2024 edition, MSRV 1.85, with a single runtime dependency (strsim for Jaro-Winkler similarity) and an optional serde feature (derive, no default features) for serializing the index, options, and hits. Dev-dependencies include quickcheck/quickcheck_macros for property-based tests, divan as the benchmark harness, and inquire/serde_json for the interactive example. It ships purely as a library crate with docs.rs-generated documentation, no async runtime, and no I/O beyond what the caller provides.

Code Quality The test suite combines conventional #[test] functions with #[quickcheck] property tests run against a shared engine populated from a bundled fixture, covering removal/reverse-map pruning and randomized query fuzzing. A separate divan benchmark suite measures insertion and search throughput, and CI runs cargo test on stable and cargo bench on nightly for every push and pull request to main. Internal types stay private and are composed from small, descriptively named methods, with comparisons centralized in dedicated compare_* functions rather than scattered inline logic; the one place an invariant is assumed, it is documented with an explicit .expect(...) message rather than an unchecked unwrap.

What Makes It Unique Rather than the common approach of scoring each query token independently and averaging, simsearch treats matching as a constrained assignment problem: it searches for the best non-overlapping ordering of query-token-to-document-position matches while tracking proximity cost and match composition, then blends match quality, term coverage, token proximity, exactness, first-match position, and specificity into a single normalized score. That is a more deliberate ranking model than the typical small fuzzy-search crate, though the underlying techniques (inverted index plus Jaro-Winkler) are established rather than novel.