Frontend Fuzzy + Substring + Prefix Search

@m31coding/fuzzy-search is a frontend library for searching objects with ids (entities) by their names and features (terms). It is

• Fast: A query takes usually well below 10 ms.
• Accurate: Powered by a suffix array and n-grams with a novel approach of character sorting.
• Multilingual: The language-agnostic design of the algorithm enables operation across all languages.
• Flexible: Entities and their terms can be inserted, updated and removed.
• Reliable: Well tested standalone library with no dependencies.
• Universal: Works seamlessly in both frontend and backend (Node.js) environments.

• Related blog post
• Try the demo

Installation

Install the package via npm:

npm install @m31coding/fuzzy-search

The following files are available in the dist folder for different use cases:

• fuzzy-search.module.js (ESM)
• fuzzy-search.cjs (CommonJS)
• fuzzy-search.umd.js (UMD)
• fuzzy-search.modern.js (Modern mode)
• fuzzy-search.d.ts (TypeScript definitions)

This library uses microbundle. Please consult their documentation for more information on how to use the different files.

Usage

The most important definitions can be found in the folder interfaces. For creating a searcher, use the SearcherFactory. Here is a basic usage example (esm module syntax):

import * as fuzzySearch from './path/to/fuzzy-search.module.js';

const searcher = fuzzySearch.SearcherFactory.createDefaultSearcher();

const persons = [
  { id: 23501, firstName: 'Alice', lastName: 'King' },
  { id: 99234, firstName: 'Bob', lastName: 'Bishop' },
  { id: 5823, firstName: 'Carol', lastName: 'Queen' },
  { id: 11923, firstName: 'Charlie', lastName: 'Rook' }
];

function log<T>(obj: T): void {
  console.log(JSON.stringify(obj, null, 2));
}

const indexingMeta = searcher.indexEntities(
  persons,
  (e) => e.id,
  (e) => [e.firstName, e.lastName, `${e.firstName} ${e.lastName}`]
);
log(indexingMeta);
/* {
  "entries": {
    "numberOfTerms": 12,
    "indexingDurationTotal": 1,
    ...
  }
} */

const result = searcher.getMatches(new fuzzySearch.Query('alice kign'));
log(result);
/* {
  "matches": [
    {
      "entity": {
        "id": 23501,
        "firstName": "Alice",
        "lastName": "King"
      },
      "quality": 0.8636363636363635,
      "matchedString": "Alice King"
    }
  ],
  "query": {
    "string": "alice kign",
    "topN": 10,
    "searchers": [
      {
        "type": "fuzzy",
        "minQuality": 0.3
      },
      {
        "type": "substring",
        "minQuality": 0
      },
      {
        "type": "prefix",
        "minQuality": 0
      }
    ]
  },
  "meta": {
    "entries": {
      "queryDuration": 1
    }
  }
} */

const removalResult = searcher.removeEntities([99234, 5823]);
log(removalResult);
/* {
  "removedEntities": [
    99234,
    5823
  ],
  "meta": {
    "entries": {
      "removalDuration": 0
    }
  }
} */

const persons2 = [
  { id: 723, firstName: 'David', lastName: 'Knight' }, // new
  { id: 2634, firstName: 'Eve', lastName: 'Pawn' }, // new
  { id: 23501, firstName: 'Allie', lastName: 'King' }, // updated
  { id: 11923, firstName: 'Charles', lastName: 'Rook' } // updated
];

const upsertMeta = searcher.upsertEntities(
  persons2,
  (e) => e.id,
  (e) => [e.firstName, e.lastName, `${e.firstName} ${e.lastName}`]
);
log(upsertMeta);
/* {
  "entries": {
    "numberOfTerms": 12,
    "upsertDuration": 0,
    ...
  }
} */

const result2 = searcher.getMatches(new fuzzySearch.Query('allie'));
log(result2);
/* {
  "matches": [
    {
      "entity": {
        "id": 23501,
        "firstName": "Allie",
        "lastName": "King"
      },
      "quality": 3,
      "matchedString": "Allie"
    }
  ],
  "query": {
    "string": "allie",
    "topN": 10,
    "searchers": [
      {
        "type": "fuzzy",
        "minQuality": 0.3
      },
      {
        "type": "substring",
        "minQuality": 0
      },
      {
        "type": "prefix",
        "minQuality": 0
      }
    ]
  },
  "meta": {
    "entries": {
      "queryDuration": 0
    }
  }
} */

The following parameters are available when creating a query:

| Parameter | Type | Default | Description | | --------- | ---- | ------- | ----------- | | string | string | - | The query string. | | topN | number | 10 | The maximum number of matches to return. Provide Infinity to return all matches. | | searchers | SearcherSpec[] | [new FuzzySearcher(0.3), new SubstringSearcher(0), new PrefixSearcher(0)] | The searchers to use and the minimum quality thresholds for their matches. |

A fuzzy search minimum quality threshold below 0.3 is not recommended, as the respective matches are most likely irrelevant.

If the data terms contain characters and strings in non-latin scripts (such as Arabic, Cyrillic, Greek, Han, ... see also ISO 15924), the default configuration must be adjusted before creating the searcher:

const config = fuzzySearch.Config.createDefaultConfig();
config.normalizerConfig.allowCharacter = (_c) => true;
const searcher = fuzzySearch.SearcherFactory.createSearcher(config);

Moreover, if your dataset is large (> 100.000 terms), you may index the searcher in a web worker to avoid blocking the main thread, as shown in this usage example.

If your objects cannot be identified by a unique id, you can also pass (e) => e for the getId parameter of both indexEntities and upsertEntities. Just be aware that the getId function is used for equality checks and the creation of Maps, particularly utilized by the upsertEntities and removeEntities methods. For indexing plain strings, you can call:

const indexingMeta = searcher.indexEntities(
  ["Alice", "Bob", "Carol", "Charlie"],
  (e) => e,
  (e) => [e]
);

To try the demo and usage examples locally, clone the repository and execute the commands:

npm install
npm run build

To proceed, open the html file of interest (e.g., fuzzy-search-demo.html) with a local webserver. If you use VS Code, you may use the Live Server extension for this purpose.

Upsert and removal

This library was optimized for fast querying. At its core, a searcher employs integer indexes that can not be easily updated. The upsert operation is implemented by reindexing a secondary searcher, which is initially empty. Removal is implemented by blacklisting entities.

Consequently, repeated upsert operations with a large number of entities may be costly. In such cases, consider reindexing the searcher from scratch by calling the index method eventually.

Normalization

Query strings and data terms are normalized in the following normalization pipeline (order matters):

• Null and undefined strings are replaced by an empty string.
• Strings are lowercased and normalized to NFKC.
• Replacements are applied to characters such as å -> aa, æ -> ae. See also Latin replacements.
• Strings are normalized to NFKD.
• Space equivalent characters are replaced by a space.
• Surrogate characters, padding characters and other non-allowed characters are removed.

Normalization to NFKC decomposes characters by compatibility, then re-composes them by canonical equivalence. This ensures that the characters in the replacement table always match. Normalization to NFKD decomposes the characters by compatibility but does not re-compose them, allowing undesired characters to be removed thereafter.

The default normalizer config adopts the following values:

config.normalizerConfig.replacements = [fuzzySearch.LatinReplacements.Value];
let spaceEquivalentCharacters = new Set(['_', '-', '–', '/', ',', '\t']);
config.normalizerConfig.treatCharacterAsSpace = (c) => spaceEquivalentCharacters.has(c);
config.normalizerConfig.allowCharacter = (c) => {
  return fuzzySearch.StringUtilities.isAlphanumeric(c);
};

With this pipeline and configuration, the string Thanh Việt Đoàn is normalized to thanh viet doan.

Fuzzy search: sorted n-grams

The general idea of n-grams and the sorting trick is outlined in this blog post. In short, the data terms and the query string are padded on the left, right and middle (replacement of spaces) with $$, !, and !$$, respectively, before they are broken down into 3-grams. For example, the string sarah becomes $$sarah! after padding and the resulting 3-grams are:

$$s, $sa, sar, ara, rah, ah!

The more common 3-grams between the query and the term, the higher the quality of the match. By padding the front with two characters, and the back with one character, more weight is given to the beginning of the string.

In addition, the characters of the 3-grams that don't contain '$' are sorted:

$$s, $sa, ars, aar, ahr, !ah

Sorting the characters increases the number of common n-grams for transposition errors, one of the most common types of errors in human typing. Not sorting the first n-grams assumes that transpositions are less likely to occur at the beginning of a string.

The quality is then computed by dividing the number of common n-grams by the number of n-grams of the longer string, query or term. Moreover, a 5% penalty is given if the query string does not match the term exactly. This accounts for the fact that even if two strings have the same 3-grams, they are not necessarily the same, i.e., compare aabaaa and aaabaa. With this approach, the following quality values are obtained:

| Query | Term | Padded query | Padded term | Common 3-grams | Quality | | ----- | ----- | ------------ | ----------- | ---------------|-----------------------| | sarah | sarah | $$sarah! | $$sarah! | 6 | 6 / 6 = 1.0 | | sarha | sarah | $$arah! | $$sarah! | 5 | 5 / 6 * 0.95 = 0.79 | | sar | sarah | $$sar! | $$sarah! | 3 | 3 / 6 * 0.95 = 0.475 | | arah | sarah | $$arah! | $$sarah! | 3 | 3 / 6 * 0.95 = 0.475 |

Note that I refrain from explicitly computing the Damereau-Levenshtein distance between strings, in order to keep the queries fast.

Padding strings in the middle allows for extending the algorithm across word boundaries. sarah wolff becomes $$sarah!$$wolff! and matches wolff sarah with a quality of 0.95, if 3-grams that end with a '$' are discarded.

The overall approach outlined above can be summarized as: remove n-grams that end with '$', sort n-grams that don't contain '$'. The default fuzzy search configuration appears in the code as follows:

config.fuzzySearchConfig.paddingLeft = '$$';
config.fuzzySearchConfig.paddingRight = '!';
config.fuzzySearchConfig.paddingMiddle = '!$$';
config.fuzzySearchConfig.ngramN = 3;
config.fuzzySearchConfig.transformNgram = (ngram) =>
  ngram.endsWith('$') ? null
  : ngram.indexOf('$') === -1 ? ngram.split('').sort().join('')
  : ngram;
config.fuzzySearchConfig.inequalityPenalty = 0.05;

Substring and prefix search

Substring and prefix search is realized with a single suffix array created by An efficient, versatile approach to suffix sorting.

The base quality of a prefix or substring match is simply computed by dividing the query length by the term length. For example, the query sa matches the term sarah with a quality of 2/5 = 0.4, and the query ara matches the same term with a quality of 3/5 = 0.6.

A quality offset of +2 and +1 is added to prefix and substring matches, respectively, as explained in the next section.

The final qualities of the examples are:

| Query | Term | Searcher | Quality | | ----- | ----- | ----------| ----------| | sa | sarah | Prefix | 2 / 5 + 2 = 2.4 |
| ara | sarah | Substring | 3 / 5 + 1 = 1.6 |

The default configuration for the searchers is as follows:

config.substringSearchConfig.suffixArraySeparator = '$';

Combining the searchers

The matches of the searchers are mixed with a simple approach. Prefix matches get a quality offset of +2, substring matches of +1, and fuzzy matches keep their original quality. The rationale is that, for the same query length, prefix matches are more relevant than substring matches. Additionally, fuzzy matches are only relevant if there are no prefix or substring matches.

Changing the default configuration

The default configuration has been chosen carefully. There are only a few specific scenarios that require adjustments. Consult the file default-config.ts for all configuration options and their default values.

Support and Contribution

This library is free. If you find it valuable and wish to express your support, please leave a star. You are kindly invited to contribute. If you see the possibility for enhancement, please create a GitHub issue and you will receive timely feedback.

Happy coding!