simstring_rust

A native Rust implementation of the CPMerge algorithm, designed for approximate string matching. This crate is particularly useful for natural language processing tasks that require the retrieval of strings/texts from very large corpora (big amounts of texts). Currently, this crate supports both character and word-based N-grams feature generation, with plans to allow custom user-defined feature generation methods.

Features

• ✅ Fast algorithm for string matching
• ✅ 100% exact retrieval
• ✅ Support for Unicode
• Support for building databases directly from text files
• Mecab-based tokenizer support

Supported String Similarity Measures

• ✅ Dice coefficient
• ✅ Jaccard coefficient
• ✅ Cosine coefficient
• ✅ Overlap coefficient
• ✅ Exact match

Installation

Requires Rust 1.89 or newer (edition 2024). Python bindings support Python 3.10+. See Rust API migration for the read-only query engine's trait changes.

Add simstring_rust to your Cargo.toml:

[dependencies]
simstring_rust = "0.3.0" # change version accordingly

For the latest features, you can add the master branch by specifying the Git repository:

[dependencies]
simstring_rust = { git = "https://github.com/PyDataBlog/simstring_rs.git", branch = "main" }

Note: Using the master branch may include experimental features and potential breakages. Use with caution!

To revert to a stable version, ensure your Cargo.toml specifies a specific version number instead of the Git repository.

Usage

Here is a basic example of how to use simstring_rs in your Rust project:

use simstring_rust::database::HashDb;
use simstring_rust::extractors::CharacterNgrams;
use simstring_rust::measures::Cosine;
use simstring_rust::Searcher;

use std::sync::Arc;

fn main() {
    // 1. Setup the database
    let feature_extractor = Arc::new(CharacterNgrams::new(2, "$"));
    let mut db = HashDb::new(feature_extractor);

    // 2. Index some strings
    db.insert("hello".to_string());
    db.insert("help".to_string());
    db.insert("halo".to_string());
    db.insert("world".to_string());

    // 3. Search for strings
    let measure = Cosine;
    let searcher = Searcher::new(&db, measure);
    let query = "hell";
    let alpha = 0.5;

    if let Ok(results) = searcher.ranked_search(query, alpha) {
        println!("Found {} results for query '{}'", results.len(), query);
        for (item, score) in results {
            println!("- Match: '{}', Score: {:.4}", item, score);
        }
    }
}

Saving and loading databases

Snapshots store the full index and its CharacterNgrams or WordNgrams configuration. Loading preserves insertion order and duplicates, and returns a mutable database without extracting corpus features again.

use simstring_rust::{CharacterNgrams, HashDb};
use std::sync::Arc;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut db = HashDb::new(Arc::new(CharacterNgrams::new(2, "$")));
    db.insert("hello".into());
    db.save_to_file(".", "names.ssdb")?;
    let mut restored = HashDb::load_from_file(".", "names.ssdb")?;
    restored.insert("help".into());
    Ok(())
}

from pathlib import Path
from simstring_rust.database import HashDb
from simstring_rust.extractors import CharacterNgrams

db = HashDb(CharacterNgrams(2, "$"))
db.insert("hello")
db.save_to_file(Path("."), "names.ssdb")
restored = HashDb.load_from_file(Path("."), "names.ssdb")
restored.insert("help")

The directory must exist and file_name must be a single filename. Saving atomically replaces an existing file after a successful write. Rust returns PersistenceError; Python raises OSError for filesystem errors, ValueError for invalid snapshots or filenames, and TypeError for unsupported extractors.

The v1 format uses a versioned header, CRC32 checksum, and Postcard payload with portable integer IDs. Rust and Python share the format across supported platforms. Unsupported format versions are rejected explicitly; v1 readers and extractor semantics are covered by shared compatibility fixtures. Loading temporarily holds the encoded payload and decoded data in memory.

Feature IDs use 32-bit Spur keys in memory and zero-based u32 values in v1 snapshots. The maximum feature ID is u32::MAX - 1, allowing up to 4,294,967,295 distinct interned features. This limit applies to the shared feature dictionary. String IDs and explicit sizes/counts use u64 in snapshots and are converted to native usize values with capacity checks when loaded.

Custom Rust extractors default to unsupported persistence. A wrapper that exactly matches a built-in extractor can delegate persistence_config(); arbitrary custom behavior and Python CustomExtractor objects cannot be saved.

See examples/persistence.rs and examples/python_persistence.py for runnable examples. Measure indexing, saving, and loading with cargo bench --bench persistence -- unigrams (medians of seven runs; warm file cache).

Releasing

Release Please manages stable releases from main. Its Rust strategy updates Cargo.toml, Cargo.lock, CHANGELOG.md, and .release-please-manifest.json in a release PR. Maturin derives the Python package version from Cargo, so crates.io and PyPI share one version.

Release process

1. Squash-merge changes into main using Conventional Commit PR titles. After CI passes, Release Please creates or updates the pending release PR.
2. Review the proposed version and release notes after the release PR passes CI. Merging this PR is the approval to release.
3. After CI passes, Release Please creates the vMAJOR.MINOR.PATCH tag and GitHub release. The shared build/test workflow runs against that exact release commit, producing separately named release wheel artifacts.
4. The crate is verified and published to crates.io, followed by the tested release wheels to PyPI. TestPyPI receives the same wheels independently of production publishing. Publication is automatic after the release tests pass.

Ordinary merges update the proposed release and run CI. Registry publishing is driven by Release Please's release_created output.

The configuration and manifest start from v0.3.5-beta.1. The prerelease versioning strategy with prerelease: false promotes beta/RC versions to stable versions. With the pending feature changes, the first release is 0.4.0. Subsequent versions follow Conventional Commits: fix and perf bump the patch, feat bumps the minor, and breaking changes bump the minor while the project is below 1.0.0. Include the Rust API migration when reviewing the first release notes.

Repository setup

• Install a release GitHub App on this repository with Contents, Issues, and Pull requests read/write permissions. Add its App ID and private key as repository secrets RELEASE_APP_ID and RELEASE_APP_PRIVATE_KEY. The App token allows CI to run on the release PR that it creates.
• Configure main to require the CI and PR title checks before merging. Enable squash merging and use the PR title as the squash commit title so Release Please can determine the version from the merged history.
• Configure trusted publishers for PyDataBlog/simstring_rs, workflow CI.yml, and environment testpypi on TestPyPI / pypi on PyPI. These environments use automatic publishing, with no required reviewers.
• Provide CARGO_REGISTRY_TOKEN with permission to publish simstring_rust.

Retrying publication

Use Re-run failed jobs on the original release workflow run. This reuses Release Please's outputs and the successful build artifacts. Already-published crate versions and wheel files are skipped. Check the publishing jobs to confirm that the packages are available in their registries.

Rust API migration

Version 0.4.0 introduces breaking changes for custom Rust trait implementations. The read-only query engine preserves the usual HashDb and Searcher calls, as well as Python method signatures. Custom Rust implementations need these updates:

• FeatureExtractor: implement visit_features(&self, text: &str, visitor: &mut dyn FnMut(&str)), emitting occurrence-qualified features. The default features method interns, sorts, and deduplicates them for insertion; search visits them without interning.
• Database: interner() returns &Rodeo rather than a locked Arc. lookup_strings() returns sorted, unique Option<&[StringId]> postings, and get_features() returns Option<&[Spur]>. Implement feature_sizes() as a sorted, unique slice of populated sizes. Each ID belongs to exactly one size bucket; stored features must be sorted and unique, using the same interner. Optionally override visit_postings() to enumerate one feature's postings across a size range directly; the default calls lookup_strings() once per size.
• Measure: implement similarity_from_counts(x_len, y_len, common) -> f64. The default similarity intersects sorted feature sets and delegates to it. Search uses counts directly, so this method must agree with the pruning bounds.

Unknown query features still contribute to similarity denominators. Duplicate insertions remain distinct results, and queries with no features return no results. Both search methods now apply exact score filtering at threshold boundaries.

Search performance

Most search time goes to gathering postings and counting overlaps. cargo bench --bench micro measures end-to-end search (100 queries over benches/data/company_names.txt, Cosine, minimum of 30 runs). Measured on one x86_64 machine, before and after the ScanCount and per-feature posting index changes:

Contributing

Contributions are welcome! Please open an issue or submit a pull request on GitHub.

Use Conventional Commits for PR titles, for example fix(search): handle empty queries or feat(bindings): add an extractor. Mark breaking changes with !, such as refactor(api)!: change the Database trait, and describe the migration in the PR. PR titles are checked automatically and become the squash commit titles used by Release Please.

License

This project is licensed under the MIT License.

Benchmarks

The benches/run_benches.py harness compares several language bindings (Rust, Python, Julia, Ruby, C++).

The CI job summary and benchmark PR comment also report Rust and Python database build, save, and load medians, snapshot sizes, and sample counts for both corpora with 2-, 3-, and 4-grams. Run cargo bench --bench persistence -- --json (Rust) or python benches/bench_persistence.py (Python bindings) for the persistence measurements in machine-readable form.

CI also checks insert and unranked Cosine search against the latest stable published crate, rebuilding release and PR sources with matching settings for Rust and Python. It uses company names, character/word 2–4 grams, and thresholds 0.6/0.9. After three paired runs, cases slower by more than 5% are rechecked: confirmed >5% warns and confirmed >10% fails. The median and every recheck pair must exceed the threshold. Correctness mismatches and benchmark errors fail immediately. Raw samples and build metadata are uploaded as the release-regression artifact, with results in the existing benchmark comment. Run .venv/bin/python benches/check_release.py --baseline 0.5.0 locally; Maturin must be installed, and each run needs a fresh --output directory.

• git, autoconf, automake, libtool, make, python, uv and a C++ compiler (g++) to build the C++ CLI.

The C++ sources are cloned into benches/.simstring_cpp/ and a local copy of the simstring binary is installed under that directory. If you need to rebuild from scratch, remove benches/.simstring_cpp/ before re-running the benchmark suite.

Acknowledgements

Inspired by the SimString project.