Repository files navigation

@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

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 usesmicrobundle. Please consult their documentation for more information on how to use the different files.

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

import*asfuzzySearchfrom'./path/to/fuzzy-search.module.js';constsearcher=fuzzySearch.SearcherFactory.createDefaultSearcher();constpersons=[{id:23501,firstName:'Alice',lastName:'King'},{id:99234,firstName:'Bob',lastName:'Bishop'},{id:5823,firstName:'Carol',lastName:'Queen'},{id:11923,firstName:'Charlie',lastName:'Rook'}];functionlog<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,    ...  }} */constresult=searcher.getMatches(newfuzzySearch.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    }  }} */constremovalResult=searcher.removeEntities([99234,5823]);log(removalResult);/* {  "removedEntities": [    99234,    5823  ],  "meta": {    "entries": {      "removalDuration": 0    }  }} */constpersons2=[{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];constupsertMeta=searcher.upsertEntities(persons2,(e)=>e.id,(e)=>[e.firstName,e.lastName,`${e.firstName}${e.lastName}`]);log(upsertMeta);/* {  "entries": {    "numberOfTerms": 12,    "upsertDuration": 0,    ...  }} */constresult2=searcher.getMatches(newfuzzySearch.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:

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 alsoISO 15924), the default configuration must be adjusted before creating the searcher:

constconfig=fuzzySearch.Config.createDefaultConfig();config.normalizerConfig.allowCharacter=(_c)=>true;constsearcher=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 inthis usage example.

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

constindexingMeta=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 installnpm 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 theLive Server extension for this purpose.

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 theindex method eventually.

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 alsoLatin 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];letspaceEquivalentCharacters=newSet(['_','-','–','/',',','\t']);config.normalizerConfig.treatCharacterAsSpace=(c)=>spaceEquivalentCharacters.has(c);config.normalizerConfig.allowCharacter=(c)=>{returnfuzzySearch.StringUtilities.isAlphanumeric(c);};

With this pipeline and configuration, the stringThanh Việt Đoàn is normalized tothanh viet doan.

The general idea of n-grams and the sorting trick is outlined in thisblog 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 stringsarah 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., compareaabaaa andaaabaa. With this approach, the following quality values are obtained:

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 matcheswolff 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 is realized with a single suffix array created byAn 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 querysa matches the termsarah with a quality of 2/5 = 0.4, and the queryara 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:

The default configuration for the searchers is as follows:

config.substringSearchConfig.suffixArraySeparator='$';

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.

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

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!