HN Explorer

Show HN: Frontend Fuzzy Search (github.com)

120 points by kmschaal ↗ HN
I have spent several years working on search engines in the backend and have now utilized that experience to develop a fuzzy search library for the frontend. It's fast, accurate and can be used for all languages. It should be easy to integrate into your Javascript / Typescript projects. If you test it and find any edge cases that did not work for you please let me know.

The implementation is based on 3-grams by the book, augmented with a novel trick of sorting the characters within the 3-grams for enhanced accuracy. For a detailed explanation you may refer to my related blog post at https://www.m31coding.com/blog/fuzzy-search.html.

Happy Coding!

37 comments

[ 5.3 ms ] story [ 84.6 ms ] thread
[deleted]
(comment deleted)
tkcranny
Looks like a neat library.

I’m curious if there’s a tl;dr on how this is better or different to Fuse, which is a very popular established client side fuzzy searching library.

https://github.com/krisk/fuse

kmschaal
Hi, thank you for your interest! I believe that most fuzzy search implementations lack accuracy in one aspect or another. The primary goals of my library are accuracy and query performance. However, I haven't looked into Fuse yet. I'm highly interested in hearing feedback from people who have tried both libraries with their datasets.
LoganDark
What is your definition of "accuracy" within the context of fuzzy search?
kmschaal
It's subjective, I have to admit. I would say a search is accurate if most people find what they are looking for in their dataset in the first try.

Distance definitions such as the Levenshtein and Damerau-Levenshtein distances provide a solid basis for discussions on accuracy. However, they are costly to compute and hence not widely adopted in fuzzy search libraries.

I started by using the known filter equation for the Levenshtein distance and computed a quality score with a leightweight formula. Then, I realized that the filter equation can be extended to the Damerau-Levenshtein distance by sorting the characters of the 3-grams.

In my tests, this implementation worked well. Please let me know how it works for you if you test it.

LoganDark
> It's subjective, I have to admit. I would say a search is accurate if most people find what they are looking for in their dataset in the first try.

I'd say a search is accurate if it finds what most closely matches the query, for some definition of "matches". A search is useful if most people can find what they are looking for on the first try.

That is, a search being accurate doesn't necessarily translate to usefulness, if people don't (or can't) know how to write those accurate queries.

I'd imagine this is why fuzzy searches exist. Fuzzier queries allow for a larger spectrum of possible matches, which means a larger set of queries can turn up those results someone is looking for. Queries do not have to be as precise, and writing useful queries is easier.

But to me it seems diametrically opposed to accuracy. Usefulness is a much more intuitive measure, because the query does not have to be perfectly accurate in order to find the right result.

Alternatively, you could focus on the quality of ranking of the returned matches: how often the correct result is near the top (and how near) when the user finds what they are looking for. Ideally you want this as high as possible.

kmschaal
Thank you for your explanation, I get your point. Regarding your last suggestion: I think it would be great to measure how often the correct result is near the top. However, don't we face the same issue as before? What is the correct result? Is it the term the user has in mind when writing the query? But what if they make a typo, and the term with the typo also exists in the dataset? Or they just type half of the term they are thinking of, but there are many terms in the dataset with the same prefix?

So, in the end, I believe it's worthwhile to try different implementations and share our subjective experiences.

si1entstill
I had a similar question. I've been using fuse for years and have had almost no qualms with the data it returns after some light tuning.
kmschaal
Glad to hear that it works well, will look into it.
henio
Very nice lib, with proper documentation!
RoyalSloth
Good job, this looks really well done. One thing I am wondering, however, is how easy it would be to integrate a pre-generated inverted index file into this fuzzy searcher?

Context: Say I have a bunch of blog posts from which I create an inverted index at "export to html" time, in order to avoid indexing the blog content at runtime on every page visit. Is there a way to persist the internal state of the fuzzy search across different page requests (e.g, /blog-post-1, /blog-post-2), so it only builds its internal state/index once?

The pre-generated inverted index could be quite large and I would like to avoid parsing it on every page request.

kmschaal
Thank you for your kind feedback! That's a great idea. I have implemented a memento object that can be used for transferring the serialized state of the searcher. The intent of the implementation was to transfer the searcher between a web worker and the main thread. You could try to serve the Memento from the server and store it in an index db. You may have a look at the web worker example I provide in the repository.
RoyalSloth
> You could try to serve the Memento from the server and store it in an index db

I am not sure what you mean by "store it in an index db", but I was thinking about using the searcher on a static website (no real backend, only a fileserver serving pre-generated html files). So if I understand you correctly, in order for this to work I would have to cache Memento via a local storage and load it on every page load/search request.

Unfortunately the index would change over time, thus one would have to detect this somehow and regenerate Memento as well.

kmschaal
Sorry for the confusion. I think you could generate the memento each time you compile your blog into HTML. The memento can be stored as a json file and served statically by your fileserver. When a user visits your page, retrieve the memento from the server. Then, initialize the searcher with it. In this way you avoid indexing content at runtime.

As a bonus you could cache the memento in the local storage or session storage.

Kalabasa
When i did my static site search function some time ago, I used Elasticlunr. I was able to pregenerate the index file as a big json file that is loaded at the client.

http://elasticlunr.com/

_heimdall
Nice to see this as a framework-agnostic library!

I have always been a bit unsure when to reach for client-side code for festures like search, filtering, and pagination though. The features are powerful for sure and if the site is otherwise static I can see some value there, but it means having to ship all searchable data to the browser. It feels like an easy security risk to avoid, and offloading that work to a backend where the state lives feels more straightforward (as long as you have a hosted backend at all).

metayrnc
Almost all frontend fuzzy search libraries I tried fail in correcting small typos (whoch is pretty common when searching). From the demo it seems this library can handle it. I will definitely be trying it out on my own project. Thanks for sharing it!
trescenzi
Have you considered building the search piece in wasm for performance? A few years back I was looking for a library like this and couldn’t find one that seemed fast enough for what I wanted. I ended up building one in rust and it’s easily 2x as fast as the js code I started with.

It’s not nearly as good a fuzzy search as this is as I just kinda tinkered with it till it felt ok for the purpose but it could be way better.

Source: https://github.com/trescenzi/brainstorm Site: https://brainstorm.tcrez.xyz/

kmschaal
Hi, thanks for sharing! No, I haven't taken wasm into consideration. It would be interesting to see the performance gain, in particular for indexing.
jwr
I should probably post the code for my n-gram fuzzy search with an inverted index. Without tests, the entire code fits on a single screen (I love ClojureScript). It works on the backend (JVM) and the frontend (Javascript) and has been in production use for the last [checks notes] 8 years.
terpimost
Thank you. We need more libs like that. I just researched the field yesterday and https://github.com/leeoniya/uFuzzy looked pretty good. But there is a gap in the market of such libs. Just few allow to send the whole html document, serialize and deserialize index to be used in browser, highlighting the matches is desired feature.

Most importantly very few fuzzy search libs can get a simple substring match as a priority, which is understandable but not helpful. Imagine searching for “xample” and not having “example” among the results.

kmschaal
Thank you for your comment! It is indeed a problem in plain fuzzy search libraries (like this one) that substring matches can have a lower quality than unequal strings of similar length. A solution to that is to implement a higher level search controller that queries the fuzzy searcher, as well as a suffix array searcher. The controller than mixes the matches and returns the best matches across the two searchers. One can even add more searchers, e.g. a phonetic one. With the correct parameters this approach works well.
giovannibonetti
Great library, thanks for sharing it. As someone else mentioned, perhaps looking into WASM if you have time might be interesting. One DB that has been getting in this space is DuckDB, which recently announced WASM support for extensions like full-text search [1]. On the other hand, I haven't seen it in practice to check if it is a good benchmark or if it has different use cases.

[1] https://duckdb.org/2023/12/18/duckdb-extensions-in-wasm.html

lacoolj
oh very cool. would love to see the comparison/benchmark against the library I've used in projects for years (Fuse - https://github.com/krisk/Fuse).

Keep up the great work!

kmschaal
Thank you! I will do a comparison in the near future and update the readme.
newusertoday
Any comparison data with https://github.com/nextapps-de/flexsearch? Also what player are using to play/pause gif in your readme?
kmschaal
Hi, thank you for your questions. Unfortunately there are no comparisons yet. The gif is simply a looped screen recording created with Camtasia. Best regards!
efilife
I've always used Minisearch for stuff like this. Would be cool to see comparisons on this project's github page
leeoniya
neat!

i will add it to the uFuzzy benchmarks :)