Fuzzy search algorithm in Sublime Text

Fuzzy string searching is the technique of finding strings that match a pattern approximately (rather than exactly. In many editors, we can easily find the Find menu item to do exact matching. While in Sublime Text and some other editors, we can use fuzzy string searching as well if we just want to have an approximate match.

There is some algorithm implemented in Sublime Text to implement achieve this. First the search query is split into characters, join them with a regex wildcard, and then run the regex on your set of strings.

stringsToSearch.forEach(function(string) {

    if (RegExp(string.split('').join('.*?')).test(string)) {

        pick(string);

    }

});

If you disable backtracking, a search across n strings with query length k should run in O(nk) time (perhaps depending on the regex engine).

That doesn't help with highlighting the matches, but for that you can:

• observe that regex matching is deterministic, so regex-replace on the result set to insert some formatting;
• or write a very simple regex parser to do custom stuff. Since the only operators are the . and *, you can do it with a DFA.

DEMO:

function fuzzyMatch(searchSet, query) {
    var tokens = query.toLowerCase().split(''),
        matches = [];

    searchSet.forEach(function(string) {
        var tokenIndex = 0,
            stringIndex = 0,
            matchWithHighlights = '',
            matchedPositions = [];

        string = string.toLowerCase();

        while (stringIndex < string.length) {
            if (string[stringIndex] === tokens[tokenIndex]) {
                matchWithHighlights += highlight(string[stringIndex]);
                matchedPositions.push(stringIndex);
                tokenIndex++;

                if (tokenIndex >= tokens.length) {
                    matches.push({
                        match: string,
                        highlighted: matchWithHighlights + string.slice(
                            stringIndex + 1
                        ),

                        // Maybe use this to weight matches?
                        // More consecutive numbers = higher score?
                        positions: matchedPositions
                    });
                    break;
                }
            }else {
                matchWithHighlights += string[stringIndex];
            }
            stringIndex++;
        }
    });

    return matches;
}

function highlight(string) {
    return '<span class="highlight">' + string + '</span>';
}