March 5, 2015 will

Sublime Text like fuzzy matching in Javascript

I recently implemented a Sublime Text like fuzzy matching for my encrypted notes app. Fuzzy matching is a really nice feature that I haven't seen used outside of code editors.

If you haven't used Sublime Text, the fuzzy matching is used to quickly open files. Rather than navigate directories in the UI – which can laborious – the open file dialogue uses the characters you type to filter a list of paths. Each character you type must match a character in the file path exactly once and and in the same order as they appear in the path. For instance the search “abgvi” would match “/application/blog/views”, as would “blgview”. The basic idea should work with any text, not just paths.

I fully expect a real Javascript programmer to do this in two lines (I'm a Python guy that has been faking Javascript proficiency for years).

My first thought in implementing this was regular expressions, but as well as matching I also wanted to highlight the matched characters in the text. That proved harder to do with a regular expression. Probably not impossible, but I'll be honest with you; I gave up.

Turns out a non-regex solution is simple enough, and plenty fast. Here it is:

function fuzzy_match(text, search)
    Parameter text is a title, search is the user's search
    // remove spaces, lower case the search so the search
    // is case insensitive
    var search = search.replace(/\ /g, '').toLowerCase();
    var tokens = [];
    var search_position = 0;

    // Go through each character in the text
    for (var n=0; n<text.length; n++)
        var text_char = text[n];
        // if we match a character in the search, highlight it
        if(search_position < search.length &&
          text_char.toLowerCase() == search[search_position])
            text_char = '<b>' + text_char + '</b>';
            search_position += 1;
    // If are characters remaining in the search text,
    // return an empty string to indicate no match
    if (search_position != search.length)
        return '';
    return tokens.join('');

This function compares a string with the fuzzy search query. If it matches, it will return the text with the matched characters wrapped in <b> tags, otherwise it returns an empty string.

I put together a demo that gets a list of links from Reddit and gives you a text box to do the fuzzy matching:

View the source if you want to know more, there are some helpful comments.

Use Markdown for formatting
*Italic* **Bold** `inline code` Links to [Google]( > This is a quote > ```python import this ```
your comment will be previewed here

I saw you post on reddit and it reminded me I did something like this once and wanted to remove the regex from it but never got round to it so yours interested me. Unfortunately I was interested in the word completion in the editor, didnt even realize it worked different else where. But made me do mine without regex which was fun, havent coded in ages. Was also interested in making it more unicode compatible coz we got new stuff in es6 that makes working with them better but not perfect. I made a version of yours that is very compatible if you use the grapheme splitter. Anywayz, all fun, heres some links...

Yours with Unicode support
Theres some checkboxs to turn grapheme splitting on and off. This allows you to handle stuff that es6 doesnt. Turn it of and copy and paste the yoga dude into the search box. Notice the entry in the list now has a symbol next to the first dude. Thats because of the es6 not handling a zero width joiner. Turn it on and it goes away. Look in the browsers console to see speed results.

Article I got my unicode knowledge from....

My Word Completion.....

My original word completion....