3 ms·

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

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.
      - magicalhippo 4y ago
        > for example, spelling errors are less common at the start of words At least on mobile, I find I make just as many first letter mistakes by hitting the wrong "key" on the on-screen keyboard, as I do in any other position of the word. Very annoyingly the predictive text engine assumes like you mention and it takes a lot for it to consider the first letter being wrong.
- magicalhippo 4y ago
  > even if it's limited, one or two typos at most This would help a lot I think. When I'm on mobile, the most common error is "keyboard offset error", where I hit a "key" next to the one I intended. So it's not completely arbitrary, and it only happens once or twice in 99% of the cases. On a physical keyboard this also happens, but the more likely error is synchronization error, where I hit a left-hand key before a right-hand key or vice versa, the classic teh vs the. Again usually only a single such error per word and not arbitrary. Finally there's also the common case of simply missing a letter. Again, limited and not arbitrary. So at least for my sake, anything that can handle the above errors would go a long way.
rjh29 4y ago
https://pypi.org/project/regex/ https://pypi.org/project/regex/ search for 'fuzzy' The regex library builds the NFA, so it probably bakes the fuzzy stuff into the NFA itself rather than changing the pattern. Another option is something like word2vec where you cluster words of similar meaning together, as a bonus this usually handles typos as well. Not really in scope for your library, but I find it cool!

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.
    - magicalhippo 4y ago
      > for example, spelling errors are less common at the start of words At least on mobile, I find I make just as many first letter mistakes by hitting the wrong "key" on the on-screen keyboard, as I do in any other position of the word. Very annoyingly the predictive text engine assumes like you mention and it takes a lot for it to consider the first letter being wrong.
magicalhippo 4y ago
> even if it's limited, one or two typos at most This would help a lot I think. When I'm on mobile, the most common error is "keyboard offset error", where I hit a "key" next to the one I intended. So it's not completely arbitrary, and it only happens once or twice in 99% of the cases. On a physical keyboard this also happens, but the more likely error is synchronization error, where I hit a left-hand key before a right-hand key or vice versa, the classic teh vs the. Again usually only a single such error per word and not arbitrary. Finally there's also the common case of simply missing a letter. Again, limited and not arbitrary. So at least for my sake, anything that can handle the above errors would go a long way.

rjh29 4y ago

https://pypi.org/project/regex/ https://pypi.org/project/regex/ search for 'fuzzy' The regex library builds the NFA, so it probably bakes the fuzzy stuff into the NFA itself rather than changing the pattern. Another option is something like word2vec where you cluster words of similar meaning together, as a bonus this usually handles typos as well. Not really in scope for your library, but I find it cool!