Show HN: Frontend Fuzzy Search

[kmschaal]

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!

[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.

[zodvik]

Please do, that would be awesome.

[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.

[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/

[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.

[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!

[kmschaal]

Thank you, sounds great!

[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!

[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.

[swyx]

for those looking for options i found ufuzzy a lightweight and good enough version of fuse: https://swyxkit.netlify.app/ufuzzy-search

[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.

[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

[_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).

[jdthedisciple]

Nice work- Hats off!

[efilife]

I've always used Minisearch for stuff like this. Would be cool to see comparisons on this project's github page

[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.

[henio]

Very nice lib, with proper documentation!

[kmschaal]

Thank you!

[leeoniya]

neat!

i will add it to the uFuzzy benchmarks :)