Show HN: uFuzzy.js – A tiny, efficient fuzzy search that doesn't suck

by leeoniya • 4 years ago

251 82 4 years ago

Hello HN!

I became frustrated with the unpredictible/poor match quality and opaqueness of "relevance scores" in existing fuzzy and fulltext search libs, so I tried something different and this is the result. The main selling point is the result quality / ordering, with best-in-class memory overhead and excellent performance being bonuses. The API is pretty stable at this point, but looking for feedback before committing to 1.0.

TL;DR

The test corpus is a 4MB json file with 162k words/phrases, so give it a second for initial download. You can also drag/drop your own text/json corpus into the UI to try it against your own dataset.

Live demo/compare with a few other libs (there are many more in the codebase, in various states of completion, WIP):

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

In isolation for perf assessment:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

To increase fuzziness and get broader results, try setting intraMax=1 (core) and enable outOfOrder (userland):

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

Also play with the sortPreset selector to swap out the default Array.sort() for one in userland that prioritizes typehead-ness (the resultset remains identical).

Still TODO:

  - Example of stripping diacritics
  - Example of using non-latin charsets
  - Example of prefix-caching to improve typeahead perf even further
  - Example of poor man's document search (matching multiple object properties)

That's all, thanks!

simonw• 4 years ago

I'm impressed. 3.54KB minified, great performance, good results.

throwaway143562• 4 years ago

nice!

for a language that evolved to manipulate text documents it is odd that it has no features of this kind. StartsWith endsWith and indexOf seems an amazingly unsophisticated set of tools.

autocomplete ui is also terrible compared to phones?

why?

aaaaaaaaaaab• 4 years ago

a language that evolved to manipulate text documents

Tell me you know nothing about JavaScript's history, without telling me you know nothing about JavaScript's history.

leeoniya32• 4 years ago

when Larry Ellison decided to generously author a free script version of Java...

throwaway143562• 4 years ago

Strange bug in my query. I was trying to say js, for a good while, did little more than manipulate html. After some uhhh inbreeding(?) it evolved to do wild crazy things like serverside stuff (read: insane) where it puts the entire document together. (hallelujah!) But before that it was just text?

We got arrow functions use strict template strings and even asm.js, countless truly insane things were added to the eco system like unicode symbols and css animations (madness!) all of a quality as~if a late Sunday night project - per www tradition.

Im simply suggesting the next weird thing should be fuzzy text matching. Even if the implementation is complete garbage, like a permanently frozen turd, say, string compare returning a value between 0 and 1 I could see myself use it often enough. If needed one can always wrap some enormous enterprise natural language processing api to keylog the user and beam their delicious data back to the mothership for advertisement and creditscores etc

I know we cant have nice things but I can dream and it doesn't have to be nice?

chiefalchemist2• 4 years ago

Nice. I didn't know it but I was about to be looking for something like this.

How difficult - or not - would it be to use it with https://bootstrap-table.com?

leeoniya32• 4 years ago

not familiar with it, but depends on what you need.

filtering one one column? easy.

filtering multiple columns via AND? also easy.

filtering multiple columns plus highlighting matched parts in each? will take more work, but shouldnt be daunting.

chiefalchemist2• 4 years ago

Ok. Thx. I'll give your's a go. If I stumble I'll open an issue.

Truth be told I'm working on a side project POC / MVP, found bootstrap table, and just dove in. I know 3 to 6 hrs more than you :)

forrestthewoods3• 4 years ago

Nice. Here’s the fuzzymatcher I wrote years ago. My main implementation was C++ but there’s a JS version and web demo.

https://www.forrestthewoods.com/blog/reverse_engineering_sub...

leeoniya32• 4 years ago

heh, think i have yours in my comparison demos (on phone currently, cannot verify)

you can make uFuzzy behave similarly by setting intraMax to Infinity (just remove 0 from the field). but the results are usually too fuzzy in this config, though it depends on the corpus and application (auto-complete vs search)

forrestthewoods3• 4 years ago

Skimming I don’t think you have my code. Also on phone so may have missed it.

Amusingly you do have Hearthstone cards and UE4 filenames whose data definitely comes from my post.

My code has been used in more than a few fuzzy matchers. Anytime I see one posted I always check to see if it’s related or not. =D

Mine was definitely tuned for filenames and matching CamelCaseWords.

moralestapia2• 4 years ago

Thank you for this!

I am also quite frustrated with the current state of full text search in the javascript world. All libs I've tried miss the most basic examples and their community seems to ignore it. Will give yours a try but it already looks much better from the comparison page.

Edit: Nope, your lib doesn't seem to handle substitution well (THE most common type of typo), so yep, we are back to square one ...

leeoniya32• 4 years ago

yep. the core is regexp based and there is no string distance assertion during initial pre-filtering, so this wont be a use case uFuzzy can accomodate.

the intro does caveat that it would make for a poor spellcheck :)

FlexSearch actually does pretty well and can work for you, though can get quite memory hungry depending on your tokenization settings. try other libs in my compare demo, too. there are a lot of options!

swyx• 4 years ago

your comparisons table at the bottom is worth its weight in gold. ignore the haters, thank you OP

rjh292• 4 years ago

Interesting that uFuzzy depends on regexps. Python's regex library can handle fuzzy matching (up to a given number of insert/delete/substitutions) - if JavaScript had that, it would be a relatively simple change.

leeoniya32• 4 years ago

i'm curious how a regexp can handle arbitrary substitutions. afaik you need to be explicit about what alterations can occur for each character, but if that list is arbitray, then the regexp will simply match everything.

e.g.

/^cat$/ will match cat

/^ca[tr]$/ will match cat and car

/^ca\w$/ will match any 3 letter word with 'ca' prefix. (any substitution for third letter)

/^\w\w\w$/ will allow alterations for any letter, making it useless.

you can make a more complex regex that allows a single substitution in any char position

/^(?:ca\w|c\wt|\wat)$/

but this gets out of hand very quickly, especially with possible insertions, deletions, transpositions, etc.

molf3• 4 years ago

I have spent many days searching for the best JavaScript implementation of full text search that handles typos (substitutions) well. Implementing a good indexing algorithm for this is not easy. In particular if you are indexing large amounts of text (documents) instead of short strings.

I settled on MiniSearch. [0] It is fast & small enough and fairly feature complete.

Afterwards I made a few contributions to improve performance and implement a better scoring algorithm. So I'm probably a bit biased now. Take my recommendation with a grain of salt.

Personally I think that OP's library does not perform searches, fuzzy or otherwise. It's much more similar to 'grep'. Try searching for "mario adventures". It won't actually find the most obvious results, because the order of the keywords in the search string must match the order of the keywords in the indexed text.

[0] https://github.com/lucaong/minisearch

[1] https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

leeoniya32• 4 years ago

It won't actually find the most obvious results, because the order of the keywords in the search string must match the order of the keywords in the indexed text.

i'm really confused why people dont bother actually reading anything i spent so much time distilling (both in the readme and the short instructions in this submission itself), which explicitly spell out how to adjust the necessary options precisely for what you're asking.

simply toggling outOfOrder returns perfectly good results:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

leeoniya32• 4 years ago

this has now been addressed :)

https://news.ycombinator.com/item?id=33053180

jaitaiwan• 4 years ago

Out of curiosity, how does this compare with fuse.js?

leeoniya32• 4 years ago

quality:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

perf:

https://github.com/leeoniya/uFuzzy#benchmark

91edec• 4 years ago

Christ that demo is laggy. Can you move the search to a web worker so the UI doesn't lag whilst typing?

modzu2• 4 years ago

its hard to compare directly because by default they return different results; so any comparison should control for that. that said the initial numbers for ufuzzy are tiny, so im quite curious

leeoniya32• 4 years ago

it's very hard to compare. definitely eval each lib's results before accepting any bench numbers as valid!

and also please submit any improvements to the codebase to get the results better/closer. i'm only an expert in one lib (mine).

encryptluks2• 4 years ago

JSON search should be a web standard not reliant on JavaScript. Why not just have a way to include a link element that can be used as part of the search.

leeoniya32• 4 years ago

you could probably say the same about declarative ui frameworks, but given how many opinions there are for what the "right" way is in both cases, i doubt this will ever happen.

brycewray• 4 years ago

Also possibly of interest in this regard: Pagefind [0].

[0] https://github.com/cloudcannon/pagefind

trinovantes2• 4 years ago

It doesn't seem to handle missing spaces

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

leeoniya32• 4 years ago

set intraMax to something big, or Infinity (delete the 0). this will allow arbitrary amount of junk between each char

trinovantes2• 4 years ago

I see some results when intraMax is set to Inf but it doesn't seem to pick up "Llanowar Elves" despite the other libs hitting it first or second. If I narrow the list to only mtg_16000, I get 0 results.

bhl• 4 years ago

best-in-class memory overhead

Was using indexeddb considered? I've yet to see an easy to use library that allows you to store simple but large json in indexeddb, and then query against that. Useful for something as simple as an emoji picker which needs to store keywords or aliases.

leeoniya32• 4 years ago

not sure this would be less overhead than having all strings in memory. you gotta get them into memory anyhow, right?

i mean, you can store it in localstorage or wherever to save net transfer for repeated use, but i dont think it would be faster to use indexdb directly at runtime.

netghost• 4 years ago

I think indexeddb is somewhat orthogonal to this library.

The memory efficiency you might get would be that you don't need to hold the whole dataset in memory while running the filter step though at the moment it looks like it assumes you're working with an array in memory (https://github.com/leeoniya/uFuzzy/blob/main/src/uFuzzy.js#L...). That said I suspect there distance between this and something that could search against a stream of data is pretty short.

modzu2• 4 years ago

im happy with fuse js - in my case i need to match against messy data sets (typos, underscores for spaces, etc) and it works quite well; in this dataset it's hard to compare how ufuzzy would fare. what algorithm does it implement?

leeoniya32• 4 years ago

if you need solid typo tolerance uFuzzy won't work well since it's based on regexps.

tonto• 4 years ago

have you considered any search methods that are too big for memory or at least want to avoid making the user wait to download, but doesn't require a dynamic server backend?

leeoniya32• 4 years ago

no, and definitely outside the scope of a micro-lib!

phist_mcgee2• 4 years ago

Amazing job on this!

I see that your heap is incredibly small, how do you keep such a small working set of memory while keeping the library so fast?

leeoniya32• 4 years ago

ask the V8/Spidermonkey/JavaScriptCore devs how they have such fast regexp interfaces :)

other than that, nothing special. the stats-gathering pass works with large columnar arrays rather than thousands of objects. and it only does this when the pre-filtered resultset is small enough (default threshold is 1000). there's no string distance checks done, so there's no need to heap-allocate thousands of M*N matricies.

davedx• 4 years ago

Nice! Where I work we need to look at how we want to implement search and I’ve been putting it off. Will put this in our list to evaluate!

mo_po22• 4 years ago

From the README: > This is my fuzzy . There are many like it, but this one is mine.

Another new better package in the JavaScript world just for the sake of pride.

leeoniya32• 4 years ago

congratulations on reading nothing else. best time saving technique!

in case you're still confused:

https://web.archive.org/web/20070310183121/http://www.lejeun...

mo_po22• 4 years ago

I didnt mean to be disrespectful. I just suffered so much the pain of what I highlighted of the introduction that I reacted too fast. I apologize to the author of the package.

PS: leeoniya, your link makes no sense in this context.

hrdwdmrbl• 4 years ago

This reminds me of my dream of a decent desktop search product

dvh• 4 years ago

How does it compare to levenstein?

leeoniya32• 4 years ago

levenstein by itself isnt really anything so this question is unanswerable. string distance is only a part of a search algo. generally i expect that it will be significantly slower, but more tolerant to typos. the rest heavily depends on many other implementation details.

lloydatkinson2• 4 years ago

Looks interesting - I would like to try this library out to compare it with Fuse that I wrote about here https://www.lloydatkinson.net/posts/2022/writing-a-fuzzy-sea...

Also as this is a new library I highly recommend either fully dropping commonjs support or at least creating a ES module version and showing how to use that instead.

leeoniya32• 4 years ago

to compare it with Fuse, click the provided compare link in this post :)

at least creating a ES module version

that exists

lloydatkinson2• 4 years ago

Document it then!

systemz• 4 years ago

From fuzzy search I expected that entering "super meet boy" or "super maet boy" will return "Super Meat Boy" but unfortunately currently it doesn't work this way and it's quite disappointing.

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

leeoniya32• 4 years ago

this is answered in other parts of the thread here [1], but there might be some hope for it still!

https://github.com/leeoniya/uFuzzy/issues/2

however, it's probably infeasible to accomodate more than single-char-per-term substitution tolerance. thankfully, both your examples have 1-char substitutions :)

[1] https://news.ycombinator.com/item?id=33042665

tomtomtom777• 4 years ago

It is explained, but than why is it fuzzy? Isn't the fuzziness part exactly what's missing?

leeoniya32• 4 years ago

this has now been addressed by 3 additional options that handle all variations of single substitution, single transposition or single deletion. (they're not exposed in the demo form controls yet, but can be enabled via url params):

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

commit:

https://github.com/leeoniya/uFuzzy/commit/63dc67b8bdb7577f85...

eurasiantiger3• 4 years ago

The example ”spac ca” doesn’t take advantage of fuzziness (no typos/swaps), a simple inverted index of term prefixes/n-grams would produce a good enough search there.

toombowoombo• 4 years ago

Bzzzz, unrelated comment:

Some weeks ago (86 days ago) you commented on a post with this: <<

”Dammit, Jack, we got another one.” ”Another awakening?”

”Yeah.”

”Just do what we always do, make their argument look nihilist or absurdist. Remember to avoid mentioning capitalism and neoconservatism!”

>

and then said that you plan on becoming a professional author. I remembered of your existence and it crossed my mind that I'm curious about how that is going for you.

eurasiantiger3• 4 years ago

That was a joke. I have become a professional joke author.

leeoniya32• 4 years ago

can you clarify what you mean by "doesn’t take advantage of fuzziness"?

what results are you expecting but not getting back? or what results are you getting back that you are not expecting?

eurasiantiger3• 4 years ago

I tend to think of fuzzy search as having specific leniency: for example, ”xemaple” would find ”example” and ”exmaple”

easytiger• 4 years ago

"doesn't suck" - why is this in the title? What does one hope to achieve by this phrase?

Show HN: uFuzzy.js – A tiny, efficient fuzzy search that doesn't suck

Related Stories