3 ms·

"fuzzy" is a bit of an overstatement, all it does is match substrings with missing letters. If you type "orrange", it won't match. If you type "otange", it won'

"fuzzy" is a bit of an overstatement, all it does is match substrings with missing letters. If you type "orrange", it won't match. If you type "otange", it won't match. All it does is match the "oange" kind of typo (including "oe", which doesn't make any sense). This means that you'd get all kinds of weird suggestions that don't make sense as soon as your haystack has non-trivial size (like matching movie titles or artists), and might not find what you're looking for (no prioritization).

espadrine 11y ago
This is the usual meaning of "fuzzy search". It is most useful when accessing files on a file system; instead of writing out the full path, you can type pieces of the path that you know will get you the file you seek. For instance, finding an "ok" image from this location only requires to type "ok": https://thefiletree.com/lib/ https://thefiletree.com/lib/. (Note that it has scoring optimized for paths, which the library doesn't have; slashes have special meanings in paths.)
- lorenzhs 11y ago
  what you are describing is substring matching, which can be implemented much more efficiently using algorithms such as Knuth-Morris-Pratt [1]. Fuzzy matching is a different concept, and although the definition is a bit fuzzy (haha), it usually refers to Levenshtein distance (which the author specifically states he didn't implement) or Hamming distance. Note that Levenshtein distance on substrings is easy to implement, you only need to a) remember the maximum value encountered and what it matched (to match prefixes) b) not penalize gaps in the beginning (to match suffixes). Thus: M[0,j] = M[i,0] = 0 M[i,j] = max(0, M[i-1,j-1] + (needle[i] == haystack[j]), M[i-1,j] + 1, M[i,j-1] + 1) Additionally, store the highest value x and its position (i,j). When you've got the full matrix, return (x,i,j). In Bioinformatics, this is known as the Smith-Waterman algorithm [2] and the result would satisfy the requirements of fuzzy substring matching. [1] https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93P... [2] https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...
leecarraher 11y ago
furthermore its not even the dynamic implementation. m[i,j] = d(s1[1..i], s2[1..j]) m[0,0] = 0 m[i,0] = i, i=1..|s1| m[0,j] = j, j=1..|s2| m[i,j] = min(m[i-1,j-1] + if s1[i]=s2[j] then 0 else 1 fi, m[i-1, j] + 1, m[i, j-1] + 1 ), i=1..|s1|, j=1..|s2|
jaredmcateer 11y ago
It's an overstatement that other tools make as well, FZF & Ctrlp also claim to be fuzzy matches but really just deal with character omission (and optionally regex matching)

espadrine 11y ago

This is the usual meaning of "fuzzy search". It is most useful when accessing files on a file system; instead of writing out the full path, you can type pieces of the path that you know will get you the file you seek. For instance, finding an "ok" image from this location only requires to type "ok": https://thefiletree.com/lib/ https://thefiletree.com/lib/. (Note that it has scoring optimized for paths, which the library doesn't have; slashes have special meanings in paths.)

lorenzhs 11y ago
what you are describing is substring matching, which can be implemented much more efficiently using algorithms such as Knuth-Morris-Pratt [1]. Fuzzy matching is a different concept, and although the definition is a bit fuzzy (haha), it usually refers to Levenshtein distance (which the author specifically states he didn't implement) or Hamming distance. Note that Levenshtein distance on substrings is easy to implement, you only need to a) remember the maximum value encountered and what it matched (to match prefixes) b) not penalize gaps in the beginning (to match suffixes). Thus: M[0,j] = M[i,0] = 0 M[i,j] = max(0, M[i-1,j-1] + (needle[i] == haystack[j]), M[i-1,j] + 1, M[i,j-1] + 1) Additionally, store the highest value x and its position (i,j). When you've got the full matrix, return (x,i,j). In Bioinformatics, this is known as the Smith-Waterman algorithm [2] and the result would satisfy the requirements of fuzzy substring matching. [1] https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93P... [2] https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

leecarraher 11y ago

furthermore its not even the dynamic implementation. m[i,j] = d(s1[1..i], s2[1..j]) m[0,0] = 0 m[i,0] = i, i=1..|s1| m[0,j] = j, j=1..|s2| m[i,j] = min(m[i-1,j-1] + if s1[i]=s2[j] then 0 else 1 fi, m[i-1, j] + 1, m[i, j-1] + 1 ), i=1..|s1|, j=1..|s2|

jaredmcateer 11y ago

It's an overstatement that other tools make as well, FZF & Ctrlp also claim to be fuzzy matches but really just deal with character omission (and optionally regex matching)