DOCSEARCHbyAlgolia
Submit Docs

fast-fuzzy

repository·master·Indexed 18 days ago

https://github.com/ethanrutherford/fast-fuzzy

A high-performance, lightweight fuzzy-searching utility (v1.12.0) that uses a trie-based implementation of modified Levenshtein distance. It provides a `fuzzy()` function for single match scoring, a `search()` function for one-off list searches, and a `Searcher` class for efficient repeated searches via cached tries. Supports Damerau-Levenshtein distance, Sellers substring matching, and customizable normalization options.

Tokens
4.1K
Snippets
13
Records
17
Agent score
62%

What's inside fast-fuzzy

  1. How fast-fuzzy works: Methodology and Ranking

    master

    fast-fuzzy uses a modified Levenshtein distance algorithm (specifically the Sellers substring match) and uses Damerau-Levenshtein distance by default to handle transpositions more gracefully.

    Key Concepts

    • Normalization: Inputs are normalized via UTF-8 normalization, optional lowercasing, optional symbol stripping, and optional whitespace flattening/trimming. Graphemes (like conjoined emojis) are treated as single characters.
    • Scoring: Results are scored from 0 to 1.
    • Tie-breaking:
      1. Ties in score are broken by the earliness of the match (when using Sellers).
      2. Further ties are broken by favoring candidates whose length is closest to the search term length (favoring exact matches).
      3. Final ties are broken by insertion order.
    • Performance: Candidates are stored in a trie. This allows the algorithm to skip entire subtrees if they cannot possibly meet the threshold score, making it much faster than brute-force search.

  2. Configure search options

    master

    Both Searcher and search accept an options object to customize the fuzzy matching behavior.

    optiontypedescriptiondefault
    keySelectorFunctionSelects the string(s) to search when candidates are objects. If it returns an array, the candidate takes the score of the highest scoring key.s => s
    thresholdNumberThe minimum score (0 to 1) that must be met for a result to be returned..6
    ignoreCaseBoolNormalize case by calling toLower on input and pattern.true
    ignoreSymbolsBoolStrip non-word symbols (~!@#$%^&*()-=_+{}[]\;':",./<>?) from input.true
    normalizeWhitespaceBoolNormalize and trim whitespace.true
    returnMatchDataBoolReturn detailed match information.false
    useDamerauBoolUse Damerau-Levenshtein distance (punishes transpositions less).true
    useSellersBoolUse the Sellers method for substring matching.true
    useSeparatedUnicodeBoolUse separated unicode.false
    sortBysortKindDefines the return order. Supported: bestMatch, insertOrder.bestMatch

  3. Use the fuzzy() function for single match scoring

    master

    The fuzzy function is the core ranking algorithm. It compares a search term against a single candidate string and returns a match strength score between 0 and 1. Higher scores indicate closer matches.

    fuzzy accepts a subset of the full options object, specifically excluding keySelector, threshold, and sortBy.

    const {fuzzy} = require("fast-fuzzy");

fuzzy("hello", "hello world"); // returns 1
fuzzy("word", "hello world"); // returns .75

// Pass custom options (e.g., disabling whitespace normalization)
fuzzy("hello world", "hello  world", {normalizeWhitespace: false}); // returns .90909090...

  4. Use the Searcher class for efficient repeated searches

    master

    The Searcher class is recommended when searching the same set of candidates multiple times. It caches a constructed trie internally, which avoids redundant work on candidates with common prefixes and significantly improves search performance compared to brute-force methods.

    Methods

    • constructor(candidates?, options?): Initializes the searcher with an initial list and configuration.
    • add(...candidates): Adds new candidates to the existing list.
    • search(term, options?): Performs a search. The options parameter allows overriding threshold, returnMatchData, and useDamerau for that specific call.
    const {Searcher} = require("fast-fuzzy");

// Initialize with candidates
const searcher = new Searcher(["def", "bcd", "cde", "abc"]);
searcher.search("abc"); // returns ["abc", "bcd"]

// Initialize with objects and keySelector
const anotherSearcher = new Searcher(
    [{name: "thing1"}, {name: "thing2"}],
    {keySelector: (obj) => obj.name},
);

// Override options during a specific search call
searcher.search("abc", {returnMatchData: true});

  5. Use the search() function for one-off searches

    master

    The search function is used for one-off searches against a list of candidates. It returns a sorted array of matches based on the score.

    Use search when you have a static list that you only need to query once. Note that search creates a new internal trie every time it is called, which may impact performance if used frequently in real-time scenarios like search-as-you-type.

    const {search} = require("fast-fuzzy");

// Search a list of strings
search("abc", ["def", "bcd", "cde", "abc"]); // returns ["abc", "bcd"]

// Search a list of objects using a keySelector
search(
    "abc",
    [{name: "def"}, {name: "bcd"}, {name: "cde"}, {name: "abc"}],
    {keySelector: (obj) => obj.name},
);
// returns [{name: "abc"}, {name: "bcd"}]

// Return detailed match data
search("abc", ["def", "bcd", "cde", "abc"], {returnMatchData: true});
/* returns [
    { item: 'abc', original: 'abc', key: 'abc', score: 1, match: {index: 0, length: 3} },
    { item: 'bcd', original: 'bcd', key: 'bcd', score: 0.6666666666666667, match: {index: 0, length: 2} }
] */

  6. Configure fast-fuzzy search options

    master

    Both the standalone functions and the Searcher class accept an options object to customize fuzzy matching behavior.

    OptionTypeDefaultDescription
    keySelector(s) => s(s) => sA function to extract the string to be searched from an object.
    thresholdnumber0.6Minimum similarity score (0 to 1) required for a match to be returned.
    ignoreCasebooleantrueIf true, matching is case-insensitive.
    ignoreSymbolsbooleantrueIf true, symbols/punctuation are ignored during normalization.
    normalizeWhitespacebooleantrueIf true, multiple whitespaces are collapsed into one.
    returnMatchDatabooleanfalseIf true, returns objects containing score and match metadata instead of just the items.
    useDameraubooleantrueIf true, uses Damerau-Levenshtein distance (handles transpositions better).
    useSellersbooleantrueIf true, uses Sellers algorithm for scoring (optimized for substring matching).
    useSeparatedUnicodebooleanfalseIf true, uses graphemesplit to handle unicode characters more granularly.
    sortBysortKindsortKind.bestMatchDetermines the sort order of results.

    Sort Kinds (sortKind):

    • sortKind.bestMatch: Sorts by highest similarity score, then by match position, then by key index, then by length difference.
    • sortKind.insertOrder: Sorts by the order in which items were provided to the searcher.
    import { search, sortKind } from 'fast-fuzzy';

const options = {
  threshold: 0.4,
  sortBy: sortKind.insertOrder,
  keySelector: (obj) => obj.name
};

const results = search('query', [{ name: 'apple' }, { name: 'banana' }], options);

  7. Configure fuzzy search options

    master

    You can fine-tune search behavior using FuzzyOptions and AdditionalOptions.

    FuzzyOptions:

    • ignoreCase: (boolean) Ignore character casing.
    • ignoreSymbols: (boolean) Ignore symbols.
    • normalizeWhitespace: (boolean) Normalize whitespace.
    • useDamerau: (boolean) Use Damerau-Levenshtein distance.
    • useSellers: (boolean) Use Sellers algorithm.
    • useSeparatedUnicode: (boolean) Use separated Unicode.
    • returnMatchData: (boolean) If true, returns detailed match information instead of just the items.
    • sortBy: (sortKind) Determines the sorting order of results.

    AdditionalOptions:

    • keySelector: (function) A function (s: T) => string | string[] used to extract the string(s) to be searched from an object.
    • threshold: (number) The minimum score required for a match to be returned.

  8. Understand the match data format

    master

    When returnMatchData is set to true, results are returned as objects containing metadata about the match.

    Match Data Schema:

    • item: The searched value (string or object).
    • original: The original, non-normalized string.
    • key: The string used for the actual comparison (result of keySelector).
    • score: The match strength (0 to 1).
    • match: An object containing {index, length} representing the match position in terms of the original, non-normalized string.

    Note: match will be undefined if useSellers is set to false.

  9. Use the search() function for array-based searching

    master

    The search() function performs fuzzy matching against an array of candidates. The candidates can be strings or objects. If returnMatchData is true, it returns an array of MatchData<T>; otherwise, it returns the original candidates that matched.

    import { search }

// Searching strings
const results = search('term', ['apple', 'banana', 'orange']);

// Searching objects with a keySelector
const items = [{ name: 'apple' }, { name: 'banana' }];
const results = search('term', items, { 
  keySelector: (item) => item.name 
});

  10. Use fuzzy() for single-pair similarity scoring

    master

    The fuzzy(term, candidate, options) function calculates a similarity score between two strings. It is best used for one-off comparisons where you only have a single candidate to check against a term.

    By default, it returns a score between 0 and 1 (where 1 is a perfect match). If options.returnMatchData is set to true, it returns an object containing the score and metadata about the match location.

    import { fuzzy } from 'fast-fuzzy';

// Returns a score (default)
const score = fuzzy('apple', 'appel');

// Returns detailed match data
const matchData = fuzzy('apple', 'appel', { returnMatchData: true });
// matchData = { item: 'appel', original: 'appel', key: 'appel', score: 0.8, match: { index: 0, length: 5 } }

  11. Use the Searcher class for stateful searching

    master

    The Searcher class allows you to maintain a persistent list of candidates and perform multiple searches against them. You can initialize it with candidates or add them later using the .add() method.

    import { Searcher }

const searcher = new Searcher(['apple', 'banana']);
searcher.add('orange', 'grape');

const results = searcher.search('ap');

  12. Use the fuzzy() function for single string comparisons

    master

    The fuzzy() function compares a search term against a single candidate string. It returns either a number (the score) or MatchData<string> depending on whether returnMatchData is set to true in the options.

    import { fuzzy }

// Returns a score
const score = fuzzy('term', 'candidate');

// Returns detailed match data
const data = fuzzy('term', 'candidate', { returnMatchData: true });