Benchmark: Fuzzy search 4 - MeasureThat.net

HTML Preparation code:

<script src='https://cdn.jsdelivr.net/npm/lodash@4.17.15/lodash.min.js'></script>
<script src="https://rawgit.com/farzher/fuzzysort/master/fuzzysort.js"></script>
<script type="text/javascript" src="https://rawgit.com/bvaughn/js-search/1.2.0/dist/js-search.js"></script>

Script Preparation code:

var books = [];
var xmlhttp = new XMLHttpRequest();
xmlhttp.onreadystatechange = function() {
  if (xmlhttp.readyState == 4 && xmlhttp.status == 200) {
    var json = JSON.parse(xmlhttp.responseText);
    books = json.books;
  }
}
xmlhttp.open('GET', 'https://bvaughn.github.io/js-search/books.json', false);
xmlhttp.send();

var search = new JsSearch.Search('isbn');
search.addIndex('title');
search.addDocuments(books);

var titles = books.map(b => b.title);
var searchTerms = ['letter', 'world', 'wife', 'love', 'foobar'];
// var searchTerms = ['letter'];

var fuzzy = {};

var __assign = (this && this.__assign) || function () {
    __assign = Object.assign || function(t) {
        for (var s, i = 1, n = arguments.length; i < n; i++) {
            s = arguments[i];
            for (var p in s) if (Object.prototype.hasOwnProperty.call(s, p))
                t[p] = s[p];
        }
        return t;
    };
    return __assign.apply(this, arguments);
};
(function (factory) {
    factory(_, fuzzy)
})(function (lodash, exports) {
    "use strict";
    Object.defineProperty(exports, "__esModule", { value: true });
    exports.filterAndSort = exports.splitByMatches = void 0;
    var lodash_1 = lodash;
    var DEBUG = false;
    // eslint-disable-next-line @typescript-eslint/no-explicit-any
    var matchCache = new Map();
    var wordsCache = new Map();
    var wordsWithoutSeparatorsCache = new Map();
    var stringCache = new Map();
    var getJaccardCoefficient = function (_a) {
        var matchText = _a.matchText, searchWord = _a.searchWord, targetWord = _a.targetWord;
        if (matchText.length === 0) {
            return 0;
        }
        var intersection = matchText.length;
        var union = targetWord.length + searchWord.length - intersection;
        return intersection / union;
    };
    var normalize = function (_a) {
        var string = _a.string;
        if (stringCache.has(string)) {
            return stringCache.get(string);
        }
        var stringNormalized = string
            // https://stackoverflow.com/questions/990904/remove-accents-diacritics-in-a-string-in-javascript/37511463#37511463
            .normalize('NFD')
            .replace(/[\u0300-\u036f]/g, '')
            .replace(/['"“”’‘.,]/g, '')
            .replace(/-/g, ' ')
            .toLowerCase();
        stringCache.set(string, stringNormalized);
        return stringNormalized;
    };
    var SEPARATOR_CHARACTERS = [',', '.', '-', ' ', '|', '/', '(', ')', '[', ']'];
    var REGEXP_SEPARATORS = new RegExp("[\\" + SEPARATOR_CHARACTERS.join('\\') + "]+");
    var REGEXP_SEPARATORS_CAPTURING = new RegExp("([\\" + SEPARATOR_CHARACTERS.join('\\') + "])");
    var splitWords = function (_a) {
        var text = _a.text, isCapturingSeparators = _a.isCapturingSeparators;
        var cache = isCapturingSeparators ? wordsWithoutSeparatorsCache : wordsCache;
        if (cache.has(text)) {
            return cache.get(text);
        }
        var regExp = isCapturingSeparators
            ? REGEXP_SEPARATORS_CAPTURING
            : REGEXP_SEPARATORS;
        var words = text.split(regExp).filter(function (value) { return value; });
        cache.set(text, words);
        return words;
    };
    var hasAnySeparator = function (_a) {
        var word = _a.word;
        return SEPARATOR_CHARACTERS.some(function (character) { return word.includes(character); });
    };
    var pushMatchCharacter = function (_a) {
        var matchCharacters = _a.matchCharacters, match = _a.match, value = _a.value, valueNormalized = _a.valueNormalized;
        var previousMatchCharacter = matchCharacters[matchCharacters.length - 1];
        if (previousMatchCharacter != null &&
            previousMatchCharacter.match === match) {
            previousMatchCharacter.value += value;
            previousMatchCharacter.valueNormalized += valueNormalized;
        }
        else {
            matchCharacters.push({
                value: value,
                valueNormalized: valueNormalized,
                match: match,
            });
        }
    };
    var getWordMatchCharacters = function (_a) {
        var targetWord = _a.targetWord, searchWordNormalized = _a.searchWordNormalized, targetWordNormalized = _a.targetWordNormalized;
        if (SEPARATOR_CHARACTERS.includes(targetWordNormalized)) {
            return [];
        }
        if (hasAnySeparator({ word: targetWordNormalized }) ||
            hasAnySeparator({ word: searchWordNormalized })) {
            throw new Error('Neither the targetWordNormalized nor the searchWordNormalized can contain separator characters');
        }
        var matchCharacters = [];
        var searchIndex = 0;
        var targetIndex = 0;
        var lastMatchedTargetIndex = -1;
        while (true) {
            var searchCharacter = searchWordNormalized[searchIndex];
            var targetCharacter = targetWordNormalized[targetIndex];
            if (searchCharacter == null && targetCharacter == null) {
                return matchCharacters;
            }
            if (searchCharacter == null) {
                pushMatchCharacter({
                    matchCharacters: matchCharacters,
                    match: false,
                    value: targetWord.slice(targetIndex),
                    valueNormalized: targetWordNormalized.slice(targetIndex),
                });
                return matchCharacters;
            }
            if (targetCharacter == null && searchWordNormalized[searchIndex] != null) {
                searchIndex += 1;
                targetIndex = lastMatchedTargetIndex + 1;
                matchCharacters.pop();
                continue;
            }
            if (targetCharacter == null) {
                return matchCharacters;
            }
            var match = searchCharacter === targetCharacter;
            pushMatchCharacter({
                matchCharacters: matchCharacters,
                match: match,
                value: targetWord[targetIndex],
                valueNormalized: targetWordNormalized[targetIndex],
            });
            if (match) {
                lastMatchedTargetIndex = targetIndex;
                searchIndex += 1;
            }
            targetIndex += 1;
        }
        return matchCharacters;
    };
    var getWordMatch = function (_a) {
        var pairs = _a.pairs, index = _a.index, searchWord = _a.searchWord, targetWord = _a.targetWord;
        var searchWordNormalized = normalize({ string: searchWord });
        var targetWordNormalized = normalize({ string: targetWord });
        var matchCharacters = typeof pairs[index] === 'string'
            ? getWordMatchCharacters({
                targetWord: targetWord,
                searchWordNormalized: searchWordNormalized,
                targetWordNormalized: targetWordNormalized,
            })
            : [];
        var matchText = matchCharacters.reduce(function (accumulator, matchCharacter) {
            return accumulator + (matchCharacter.match ? matchCharacter.value : '');
        }, '');
        return {
            index: index,
            coefficient: getJaccardCoefficient({ matchText: matchText, searchWord: searchWord, targetWord: targetWord }),
            isExact: targetWordNormalized.startsWith(searchWordNormalized),
            matchCharacters: matchCharacters,
            matchText: matchText,
            searchWord: searchWord,
            targetWord: targetWord,
            searchWordNormalized: searchWordNormalized,
            targetWordNormalized: targetWordNormalized,
        };
    };
    var getBestWordMatch = function (_a) {
        var pairs = _a.pairs, searchWord = _a.searchWord, targetWords = _a.targetWords;
        return lodash_1.chain(targetWords)
            .map(function (targetWord, index) {
            return getWordMatch({ pairs: pairs, index: index, searchWord: searchWord, targetWord: targetWord });
        })
            .filter(function (match) { return match.coefficient; })
            .sortBy(function (match) { return match.coefficient * -1; })
            .sortBy(function (match) { return (match.isExact ? -1 : 1); })
            .first()
            .value();
    };
    var getMatch = function (_a) {
        var item = _a.item, searchText = _a.searchText, targetText = _a.targetText;
        var cacheKey = searchText + ":" + targetText;
        if (matchCache.has(cacheKey)) {
            var cachedMatch = matchCache.get(cacheKey);
            return __assign(__assign({}, cachedMatch), { item: item });
        }
        var searchWords = splitWords({
            text: searchText,
            isCapturingSeparators: false,
        });
        var targetWords = splitWords({
            text: targetText,
            isCapturingSeparators: true,
        });
        var targetWordsWithoutSeparators = splitWords({
            text: targetText,
            isCapturingSeparators: false,
        });
        var pairs = targetWords.slice(0);
        searchWords.forEach(function (searchWord) {
            var bestMatch = getBestWordMatch({ pairs: pairs, searchWord: searchWord, targetWords: targetWords });
            if (bestMatch != null) {
                pairs[bestMatch.index] = bestMatch;
            }
        });
        var match = {
            pairs: pairs,
            searchText: searchText,
            searchWords: searchWords,
            targetText: targetText,
            targetWords: targetWords,
            coefficient: getJaccardCoefficient({
                matchText: pairs
                    .map(function (pair) { return (typeof pair === 'string' ? '' : pair.matchText); })
                    .join(''),
                searchWord: searchWords.join(''),
                targetWord: targetWordsWithoutSeparators.join(''),
            }),
            isIncluded: targetWords.some(function (targetWord) {
                return searchWords.some(function (searchWord) {
                    return normalize({ string: targetWord }).includes(normalize({ string: searchWord }));
                });
            }),
            isExact: pairs.some(function (pair) {
                return typeof pair !== 'string' &&
                    pair.matchCharacters.length > 0 &&
                    pair.matchCharacters[0].match === true &&
                    pair.matchCharacters[0].valueNormalized.startsWith(pair.targetWordNormalized);
            }),
            isFull: pairs.some(function (pair) {
                return typeof pair !== 'string' &&
                    pair.matchCharacters.length > 0 &&
                    pair.matchCharacters[0].match === true &&
                    pair.matchCharacters[0].valueNormalized === pair.targetWordNormalized;
            }),
        };
        matchCache.set(cacheKey, match);
        return Object.assign(match, { item: item });
    };
    var reduceConsecutiveStrings = function (values) {
        return values.reduce(function (accumulator, value) {
            if (typeof value === 'string' && typeof lodash_1.last(accumulator) === 'string') {
                accumulator[accumulator.length - 1] = lodash_1.last(accumulator) + value;
            }
            else {
                accumulator.push(typeof value === 'string' ? value : value.matchCharacters);
            }
            return accumulator;
        }, []);
    };
    exports.splitByMatches = function (_a) {
        var searchText = _a.searchText, targetText = _a.targetText;
        if (searchText.length === 0) {
            return [targetText];
        }
        var match = getMatch({ item: targetText, searchText: searchText, targetText: targetText });
        return reduceConsecutiveStrings(match.pairs);
    };
    // TO:DO: Add cache
    exports.filterAndSort = function (_a) {
        var _b;
        var data = _a.data, _c = _a.getTargetText, getTargetText = _c === void 0 ? function (_a) {
            var item = _a.item;
            return item;
        } : _c, searchText = _a.searchText, _d = _a.sortIteratees, sortIteratees = _d === void 0 ? [function () { return 0; }] : _d;
        if (searchText.length === 0) {
            return data;
        }
        return ((_b = lodash_1.chain(data)
            // Get matches for each item
            .map(function (item) {
            var targetText = getTargetText({ item: item });
            if (typeof targetText !== 'string') {
                throw new Error('The target text to search through needs to be a string');
            }
            return getMatch({
                item: item,
                searchText: searchText,
                targetText: targetText,
            });
        })
            // Filter out non-matches
            .filter(function (match) {
            if (DEBUG) {
                // eslint-disable-next-line no-console
                console.debug('Match of %o in %o: isFull=%o isExact=%o isIncluded=%o coefficient=%o', match.searchText, match.targetText, match.isFull, match.isExact, match.isIncluded, match.coefficient);
            }
            return (match.isFull ||
                match.isExact ||
                match.isIncluded ||
                match.coefficient > 0);
        })
            // Sort by the coefficient, then by included matches, and then exact matches
            .sortBy(function (match) { return match.coefficient * -1; })
            .sortBy(function (match) { return (match.isIncluded ? -1 : 1); })
            .sortBy(function (match) { return (match.isExact ? -1 : 1); })
            .sortBy(function (match) { return (match.isFull ? -1 : 1); })
            // Finally, sort by the number of exact matches in the pairs of matches
            .sortBy(function (match) {
            return match.pairs.reduce(function (accumulator, pair) {
                if (typeof pair !== 'string') {
                    return accumulator - (pair.isExact ? 2 : 1);
                }
                return accumulator;
            }, 0);
        })).sortBy.apply(_b, sortIteratees).map(function (match) { return match.item; })
            .value());
    };
    exports.indexList = function (_a) {
        var data = _a.data, _b = _a.getTargetText, getTargetText = _b === void 0 ? function (_a) {
            var item = _a.item;
            return item;
        } : _b;
        data.forEach(function (item) {
            var targetText = getTargetText({ item: item });
            splitWords({
                text: targetText,
                isCapturingSeparators: true,
            });
            splitWords({
                text: targetText,
                isCapturingSeparators: false,
            });
        });
    };
});

fuzzy.indexList({
  data: titles,
})

Tests:

Custom fuzzy
for (var i = 0, length = searchTerms.length; i < length; i++) { const result1 = fuzzy.filterAndSort({ data: titles, searchText: searchTerms[i], }) // console.log({ result1 }) }
Fuzzysort
for (var i = 0, length = searchTerms.length; i < length; i++) { const result2 = fuzzysort.go(searchTerms[i], titles); // console.log({ result2 }) }
js-search
for (var i = 0, length = searchTerms.length; i < length; i++) { const result3 = search.search(searchTerms[i]); // console.log({ result3 }) }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Custom fuzzy
Fuzzysort
js-search

Fastest: N/A

Slowest: N/A

ⓘ Get performance results from real users on your website with Request Metrics.

Website Performance Monitoring by Request Metrics

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:100.0) Gecko/20100101 Firefox/100.0

Browser/OS: Firefox 100 on Windows

View result in a separate tab

Test name	Executions per second
Custom fuzzy	156.2 Ops/sec
Fuzzysort	2206.1 Ops/sec
js-search	29459.8 Ops/sec

Fuzzy search 4 (version: 15)

Comparing performance of: Custom fuzzy vs Fuzzysort vs js-search

Created: 3 years ago by: Registered User

Jump to the latest result

Custom fuzzy

Fuzzysort

js-search

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A