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

Latest run results:

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

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/128.0.0.0 Safari/537.36

Browser/OS: Chrome 128 on Linux

View result in a separate tab

js-search

24K/s

Fuzzysort

3K/s

Custom fuzzy

181/s

View exact numbers

Test name	Executions per second
✓ js-search	23,860 Ops/sec
Fuzzysort	2,613 Ops/sec
Custom fuzzy	181 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

It seems like we have some benchmarking code here!

To answer your question, it appears that the provided JavaScript code is comparing three different fuzzy search algorithms:

1. `fuzzy.filterAndSort`
2. `fuzzysort.go`
3. `search.search`

The benchmark results show the execution rate (ExecutionsPerSecond) of each algorithm for a specific set of search terms and data.

To provide a concise answer, I'll highlight some observations:

* The execution rates are:
	+ js-search: 29459.833984375 ExecutionsPerSecond
	+ Fuzzysort: 2206.105224609375 ExecutionsPerSecond
	+ Custom fuzzy: 156.20742797851562 ExecutionsPerSecond
* Firefox 100 browser is being used for the benchmark.
* The data and search terms are likely generated dynamically, as they seem to be related to a web application.

Without more context or information about the specific use case, it's difficult to provide a definitive answer on which algorithm performs better. However, based on the execution rates, js-search seems to have the highest performance followed by Fuzzysort, and Custom fuzzy has the lowest performance.

Fuzzy search 4 (version: 15) Benchmark.js

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

Created: 6 years ago by: Registered User

Go to the latest result

Custom fuzzy

Fuzzysort

js-search

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

Fuzzy search 4 (version: 15) Benchmark.js

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

Created: 6 years ago by: Registered User

Go to the latest result

Custom fuzzy

Fuzzysort

js-search

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

Related benchmarks

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