Hey, Thanks for your work on this library. I was wondering whether you would be interested in adding Levenshtein distance as an option? I am recently working on accelerating bounded Levenshtein distance calculations with SIMD, which is around 20-30x faster than a normal scalar Levenshtein distance algorithm for medium length strings, and I thought that it would be nice and beneficial to use it in your library. The library is on crates.io: https://crates.io/crates/triple_accel.

However, there are some tradeoffs though: my library cannot handle unicode strings and null bytes due to the SIMD implementation. This could be addressed by allowing the user to opt in to using the SIMD implementation explicitly. Of course, my library supports automatically falling back to a scalar version if SIMD is not supported as a CPU feature.

If you are interested, we could discuss a little more about the implementation. I am probably able to work on this in the future.

I added support for Levenshtein distance by using the triple_accel library. Levenshtein distance can be optionally enabled by the user by using SearchOptions. I also edited the readme, documentation, and benchmarks to reflect this change. I tried to follow the existing code style. The code passes all tests on my laptop, and for reference, here is an overview of the benchmark results:

add books: ~1.4 ms
search_jaro_winkler: ~212 us
search_levenshtein: ~131 us

SIMD Levenshtein distance should be even faster with longer strings.

simsearch-rs totally fails on Korean text. How involved would it be to have it tokenize hangeul?

searching 던지(요) should match id 866 (name: -던지(요), but gives a top result of id 1527 (name: 에게로 【너에게로 다가간다】).

raw json

use std::{error::Error, fs};

use serde::{Deserialize, Serialize};
use simsearch::SimSearch;

#[derive(Debug, Deserialize, Serialize)]
struct Entry {
    id: i64,
    name: String,
    typical_example: String,
    translation: String,
    category_eng: String,
    category_kor: String,
}

fn main() -> Result<(), Box<dyn Error + 'static>> {
    let mut engine: SimSearch<i64> = SimSearch::new();

    let data = fs::read_to_string("./output.json")?;
    let entries: Vec<Entry> = serde_json::from_str(&data)?;

    for entry in &entries {
        engine.insert(entry.id, &entry.name);
    }

    let results = engine.search("던지(요)");
    let top_match = results[1];

    let entry = entries.iter().filter(|e| e.id == top_match).collect::<Vec<_>>();

    Ok(())
}

Hi Andy and thanks for you crate!

I wanted to implement a fuzzy search in rust for some time, and thanks to your post on reddit I've discovered that the work is already done ;)

I looked at your benches and found out that you're not using criterion, which can draw fancy plots for you and provide a comparison with a previous run (very helpful when you're trying to improve the performance), so here's a PR that migrates the benches. The only other thing apart from just migrating I've also made the add 100 bench to insert items into an empty engine on each benchmark iteration, which I believe made the bench to be more fair.

Hi! Please check this PR about fixing too slow insert. This solution based on two hashmaps:

• Id to id_num
• id_num to Id

SlotMap or slab may be better to use here, but hashmaps fine too.

Notes:

• it is breaking compatibility changes, because Id now have Eq + Hash trait bounds now
• one extra clone for Id on each insert

Try it on this example https://github.com/estin/simsearch-parse-cities

$ cargo run --release

Hi!

I will try to parse and build engine on cities500.text (196648 cities) from free data by http://download.geonames.org/export/dump/ And found it's very slow process...

https://github.com/andylokandy/simsearch-rs/blob/cade2652f78957b8f587ef0d731489000dae7f12/src/lib.rs#L136

It's really needed to delete key on each insert?

And delete is too slow by self https://github.com/andylokandy/simsearch-rs/blob/cade2652f78957b8f587ef0d731489000dae7f12/src/lib.rs#L262

Why not used HashMap to map id to id_num?

When insert many items to engine on each insert searching id_num on whole list of inserted keys before

And I can make PR to fix, but no sure, what I understand this behavior right

Sorry for my poor English.

I find that making a change to use the max score of a token improved the search output for me. Particularly, it returns exact matches on a particular token first which is what I want.

I changed the following line

https://github.com/andylokandy/simsearch-rs/blob/cade2652f78957b8f587ef0d731489000dae7f12/src/lib.rs#L239

To

    result_scores
        .entry(*id_num)
        .and_modify(|v| *v = v.max(score))
        .or_insert(score);

An option for this could be incorporated in SearchOptions? Maybe a field where you can specify:

enum TokenScoreMethod {
    Sum,
    Max
}

Running cargo update on dependent library caused compile errors in older triple_accel.

All tests (with cargo test --release) pass, seems like triple_accel didn't break compatibility.

Rather than storing a vec of tuples, we push the IDs into one vector.

In order to facilitate deletes, the vector stores options.

The drawback is a lot of deletes might create a sparse vector that occupies memory

The advantage, though, is 2x faster searches on large-ish (few tens of thousands) datasets, cause we eliminate a big iteration

Definitely seems worth it

In addition, when you don't do a lot of deletes, it's gonna be more memory efficient

First, thanks for the great library! I'm using it in a hobby password manager project of mine. It's the only Rust library I've found that actually works nicely for searching password items.

The current search functions, search and search_tokens, only return the result item ids. This is fine for most situations, as the results are already sorted by the score.

However, an ability to get the scores along with the ids would allow sorting items with equal scores in a custom way. For instance, in my password manager, I would want to sort items with equal scores alphabetically.

As a side note, the biggest issue I have right now is that search result order is not stable. Searching with the same term on the same data set multiple times returns items with equal scores in different orders:

use simsearch::SimSearch;

fn main() {
    // Generate items
    let items: Vec<_> = (1..=50).map(|n| format!("Sample item {}", n)).collect();

    let mut ss = SimSearch::new();
    for i in &items {
        ss.insert(i, i);
    }

    for i in 0..3 {
        println!("Run #{i}");
        let res = ss.search("sample item");
        for id in &res[0..2] {
            println!("  {id}");
        }
        println!("---");
    }
}

Running this prints out:

Run #0
  Sample item 28
  Sample item 21
---
Run #1
  Sample item 1
  Sample item 29
---
Run #2
  Sample item 37
  Sample item 38
---

I think the reason for this instability is the use of HashMap internally. Perhaps it could be fixed by changing the hasher implementation, but ultimately I think returning the scores is a more versatile solution.