4 ms·

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 exam

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

leeoniya 4y 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 4y ago
  your comparisons table at the bottom is worth its weight in gold. ignore the haters, thank you OP
  - leeoniya 4y ago
    > ignore the haters i'm an OSS dev; how thin do you think my skin is? :D
  - llanowarelves 4y ago
    I wouldnt say the parent commenter is a hater. But thats a good general sentiment yeah
rjh29 4y 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.
- leeoniya 4y 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.
  - moralestapia 4y ago
    Sure, but then that's pretty much the core thing to solve on the fuzzy search problem. Anyway, not being a hater (as that other commenter suggested), if you could add support for this (even if it's limited, one or two typos at most) you will blow all other libs out of the way since what you have now is already quite good :D
    - leeoniya 4y ago
      maybe, something limited in scope like this could work...would be interesting to explore.
      - tbeseda 4y ago
        It might be a rare opinion in JS ecosystem, but I like the scope of this project. It solves the crux of the problem; I can compose the rest (like testing other strings alongside the input to account for typos)
        leeoniya 4y ago
        you're not gonna like the perf of doing this for all variations. it will be far faster to put together a regex with all variations and do a single pass. of course if you have specific known/common mistakes, it could be useful to only consider those. for example, spelling errors are less common at the start of words. and keyboard letter proximity limits which mistakes are likely.
molf 4y 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 https://github.com/lucaong/minisearch [1]: https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,MiniSearch&search=mario%20adventures https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...
- leeoniya 4y 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=uFuzzy,MiniSearch&outOfOrder&search=mario%20adventures https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...
  - molf 4y ago
    A blunt answer to your question is: I didn't take the time to read everything. Sorry for missing that feature. I stand by my overall point though. There is more to search than finding matches. Handling real world typing errors is one (try searching for "mario avdentures" or "mario adventutes"). Ordering results by relevance is not trivial either. And it does not appear this library intends to tackle that problem completely. Relevance scoring should take into account the term frequency and the document/field length, as well as average length. I don't mean to discount your project though. There are many distinct use cases related to searching and filtering, and power to you for solving it in a way that works for you (and I'm sure for others as well). I just wanted to share my experience in exploring the space of full text search libraries that handle long form text and typos gracefully.
leeoniya 4y ago
this has now been addressed :) https://news.ycombinator.com/item?id=33053180 https://news.ycombinator.com/item?id=33053180

leeoniya 4y 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 4y ago
your comparisons table at the bottom is worth its weight in gold. ignore the haters, thank you OP
- leeoniya 4y ago
  > ignore the haters i'm an OSS dev; how thin do you think my skin is? :D
- llanowarelves 4y ago
  I wouldnt say the parent commenter is a hater. But thats a good general sentiment yeah

rjh29 4y 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.

leeoniya 4y 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.
- moralestapia 4y ago
  Sure, but then that's pretty much the core thing to solve on the fuzzy search problem. Anyway, not being a hater (as that other commenter suggested), if you could add support for this (even if it's limited, one or two typos at most) you will blow all other libs out of the way since what you have now is already quite good :D
  - leeoniya 4y ago
    maybe, something limited in scope like this could work...would be interesting to explore.
    - tbeseda 4y ago
      It might be a rare opinion in JS ecosystem, but I like the scope of this project. It solves the crux of the problem; I can compose the rest (like testing other strings alongside the input to account for typos)
      - leeoniya 4y ago
        you're not gonna like the perf of doing this for all variations. it will be far faster to put together a regex with all variations and do a single pass. of course if you have specific known/common mistakes, it could be useful to only consider those. for example, spelling errors are less common at the start of words. and keyboard letter proximity limits which mistakes are likely.

molf 4y 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 https://github.com/lucaong/minisearch [1]: https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,MiniSearch&search=mario%20adventures https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

leeoniya 4y 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=uFuzzy,MiniSearch&outOfOrder&search=mario%20adventures https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...
- molf 4y ago
  A blunt answer to your question is: I didn't take the time to read everything. Sorry for missing that feature. I stand by my overall point though. There is more to search than finding matches. Handling real world typing errors is one (try searching for "mario avdentures" or "mario adventutes"). Ordering results by relevance is not trivial either. And it does not appear this library intends to tackle that problem completely. Relevance scoring should take into account the term frequency and the document/field length, as well as average length. I don't mean to discount your project though. There are many distinct use cases related to searching and filtering, and power to you for solving it in a way that works for you (and I'm sure for others as well). I just wanted to share my experience in exploring the space of full text search libraries that handle long form text and typos gracefully.

leeoniya 4y ago

this has now been addressed :) https://news.ycombinator.com/item?id=33053180 https://news.ycombinator.com/item?id=33053180