JS "Fuzzy" Search (sequential matching with gaps)
Back to javascript
Rather than a true "fuzzy" search based on edit distance, I really like partial string matching where the only requirement is that the sequence of characters be in the input order.
For example, "pcake" would match "pancake".
Scroll down for an example you can try out live to get an idea of how it works.
The fuzzmatch() function
The first time I saw this was in the form of a delighfully tiny function with a 4-line body in a Stack Overflow answer by a user who goes by the name "Dziad Borowy" (from Slavic folklore). I tried it and was very pleased with how well it works.
The original (see the bottom of this page) was "golfed down", so I’ve expanded it for readability here.
Live demo
If you’re not sure what to try, here’s some examples:
-
Type ".jpg" for all image files
-
Type "//.adoc" for all AsciiDoc files that are two directories deep
-
Type "slack/pb/" for the files in the slackware/pkgblog/ directory
Get creative!
Try me!
Live demo source
Note in the following example, I’m removing spaces (replace(/\s+/g,'')) from
the input search term so you can match "grace_hopper" with "gra hop", which
feels more natural to me in this instance.
There are lots of ways to do keyword searching and you could allow partial "fuzzy" searching for multiple input keywords appearing in any order by successively filtering the entire list for each partial keyword in the input. Experiment!
Note: I originally wrote this version of the fuzzy search for Faceclick: An Emoji picker with particular goals, but it turns out that fuzzy search in general is worse than useless when the things you’re searching for are short keywords!
Original "golfed" version
Here’s the original function ripped straight out of my HTML WARDen (a wiki).
(The difference between this and the original original is that Dziad Borowy’s answer added the fuzzy matching directly to the string prototype.)
++++
function fuzzy_match2(haystack, needle){
// Adapted from https://stackoverflow.com/a/15252131
var hay = haystack.toLowerCase(), i = 0, n = -1, l;
s = needle.toLowerCase();
for (; l = s[i++] ;) if (!~(n = hay.indexOf(l, n + 1))) return false;
return true;
}