@m31coding/fuzzy-search

The fuzzy search implementation uses a sorted n-gram approach to handle typos and transpositions efficiently without the overhead of Levenshtein distance.

The Process:

1. Padding: Strings are padded on the left, right, and middle (replacing spaces) with specific characters (default: $$, !, and !$$). This gives more weight to the beginning of the string.
2. N-gram Generation: The padded string is broken into n-grams (default n=3).
3. Filtering & Sorting: N-grams that end with $ are removed. N-grams that do not contain $ have their characters sorted alphabetically. This increases the match rate for transposition errors (e.g., 'ab' vs 'ba').
4. Quality Calculation: Quality is calculated as (common n-grams / max(query_ngrams, term_ngrams)). An inequalityPenalty (default 5%) is applied if the query is not an exact match to the term.

Example: For the term sarah, the padded version is $$sarah!. The resulting 3-grams (after sorting and filtering) might look like $$s, $sa, ars, aar, ahr, !ah.

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;

You can customize the fuzzy search behavior by modifying the fuzzySearchConfig object. Key options include:

• paddingLeft: Character(s) padded to the start of the string.
• paddingRight: Character(s) padded to the end of the string.
• paddingMiddle: Character(s) used to replace spaces for multi-word matching.
• ngramN: The size of the n-grams to generate.
• transformNgram: A function to process each n-gram (used for sorting or filtering).
• inequalityPenalty: A decimal value representing the penalty applied when the query is not an exact match.

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;

The FuzzySearcher follows a specific lifecycle to ensure efficient searching:

1. Initialization: A FuzzySearcher is instantiated with a specific NgramComputer strategy.
2. Indexing: When .index(terms) is called, the searcher clears any previous index, computes n-grams for every valid term, and populates an InvertedIndex. The index is then .seal()ed to optimize for lookups.
3. Searching: When .getMatches(query) is called:
   • The query string is converted into n-grams.
   • The searcher calculates commonNgramCounts (the overlap between query n-grams and indexed terms).
   • It uses QualityComputer.ComputeOverlapMaxCoefficient to determine a quality score for each term.
   • Only terms with a quality score strictly greater than query.minQuality are returned.
4. Persistence: The state can be captured via a Memento and restored later, which is useful for avoiding re-indexing expensive datasets.

To use the library, create a searcher using SearcherFactory.createDefaultSearcher(), index your entities with indexEntities, and perform searches using getMatches with a Query object.

Entities are identified by a unique ID. You provide a getId function and a getTerms function that returns an array of strings (features) to be indexed for each entity.

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' }
];

// Index entities
// getId: (e) => e.id
// getTerms: (e) => [e.firstName, e.lastName, `${e.firstName} ${e.lastName}`]
const indexingMeta = searcher.indexEntities(
  persons,
  (e) => e.id,
  (e) => [e.firstName, e.lastName, `${e.firstName} ${e.lastName}`]
);

// Perform a search
const result = searcher.getMatches(new fuzzySearch.Query('alice kign'));
console.log(result.matches);

The library supports dynamic updates to the indexed data:

• removeEntities(ids): Removes entities by their IDs. This is implemented via blacklisting.
• upsertEntities(entities, getId, getTerms): Adds new entities or updates existing ones.

Performance Warning: Upserting is implemented by reindexing a secondary searcher. Repeated upsert operations on large datasets can be costly. If you perform many updates, consider calling indexEntities (or the internal index method) to reindex from scratch to maintain performance.

// Remove entities
const removalResult = searcher.removeEntities([99234, 5823]);

// Upsert entities (add or update)
const persons2 = [
  { id: 723, firstName: 'David', lastName: 'Knight' },
  { id: 23501, firstName: 'Allie', lastName: 'King' }
];
const upsertMeta = searcher.upsertEntities(
  persons2,
  (e) => e.id,
  (e) => [e.firstName, e.lastName, `${e.firstName} ${e.lastName}`]
);