4 ms·

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

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