Skip to content

Latest commit

 

History

History
113 lines (70 loc) · 4.41 KB

README.md

File metadata and controls

113 lines (70 loc) · 4.41 KB

·𝕗𝕫·

🔍 Simple, fast, fuzzy string searching.

fz('fuzzy', 'fz'); // true

Motivation

A recent project I worked on required building out a fuzzy search interaction. Surveying the already available options led me to discover that the majority of existing implementations go with one of two techniques:

  1. old-school for/while loops, checking character-by-character for matches
  2. auto-generated regular expressions, created from the input query string

While benchmarking these approaches, it became clear that both of these techniques have merit, but under different circumstances. For example, given a use case where the query input remains relatively static between searches, the RegExp approach wins, hands down:

while loops vs. RegExp for static queries

But when the conditions change such that the query input is highly dynamic and frequently changes between searches, the while loop actually fares better (primarily due to the underutilized cost of RegExp instantiation):

while loops vs. RegExp for dynamic queries

While not everyone requires a solution that tackles both dynamic and static search inputs, it seemed like a useful feature to bring to the table. Instead of choosing one of these techniques over the other, fz simply defaults to while loops, and if it detects that the same query is being used across successive calls, it internally optimizes to a RegExp approach.

While this internal optimization is a trivial one, the result is a solution that performs competitively (but not identically) with the more efficient solution for both of these use cases. For comparison, here is how fz stacks up for static query inputs:

while loops vs. RegExp vs. fz for static queries

And here it is for dynamic query inputs:

while loops vs. RegExp vs. fz for dynamic queries

As can be seen above, fz does a decent job of keeping up for both static and dynamic input queries. If you're looking for a fuzzy search utility that removes some of the guesswork on which use case to optimize for, then fz might be a good option for you.

Getting Started

Installing fz

$ npm install fz --save

API

fz(candidate, query)

Performs a fuzzy search against candidate, using query as the search criteria.

candidate will be considered a match for query using the following criteria:

  • Every character in query must have a match in candidate.
  • The matching characters must appear in the same order.
  • candidate may contain any number of non-matching characters, including in-between the matching characters.
  • CASING is IgNoRed.

Alternatively, if you think more in terms of regular expressions, then fz('foobar', 'fb') will behave similarly to /f.*b.*/i.test('foobar') (with special handling for escape sequences and other special characters).

Please see the examples below for more clarification.

Arguments:

  • candidate : String (Required)

    The string value to search against.

  • query : String (Required)

    The fuzzy search criteria to use when determining whether or not candidate is a match.

Returns: isMatch : Boolean

If candidate is a match for query, then true, otherwise false.

Examples:

const fz = require('fz');

fz('Wombat Developers Union', 'wdu') // true
fz('ninja pumpkin mutants', 'NPM') // true
fz('nebulus plasma muffin', 'mpn') // false
fz('foo', 'O') // true
fz('bar', 'bart') // false
fz('???', '') // true
fz('', '???') // false
fz('', '') // true

Contributing

Pull requests are welcome, but I recommend filing an issue to discuss feature proposals first.

To get started:

  1. Install dev dependencies:
$ npm install
  1. To run the test suite:
$ npm test
  1. To run the bench suite:
$ npm run bench

A special shout-out and "thank you" goes to Diego Rodríguez Baquero for being awesome enough to hand over the fz package name on npm!