🔍 Simple, fast, fuzzy string searching.
fz('fuzzy', 'fz'); // true
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:
- old-school
for
/while
loops, checking character-by-character for matches - 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:
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 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:
And here it is for dynamic query inputs:
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.
$ npm install fz --save
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 incandidate
. - 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
Pull requests are welcome, but I recommend filing an issue to discuss feature proposals first.
To get started:
- Install dev dependencies:
$ npm install
- To run the test suite:
$ npm test
- 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!