@leeoniya/ufuzzy

▒ μFuzzy

A tiny, efficient, fuzzy search that doesn't suck. This is my fuzzy 🐈. There are many like it, but this one is mine.

---

Overview

uFuzzy is a fuzzy search library designed to match a relatively short search phrase (needle) against a large list of short-to-medium phrases (haystack). It might be best described as a more forgiving String.prototype.indexOf(). Common use cases are list filtering, auto-complete/suggest, and title/name/description/filename/function searches.

Each uFuzzy match must contain all alpha-numeric characters from the needle in the same sequence, so is likely a poor fit for applications like spellcheck or fulltext/document search. However, its speed leaves ample headroom to match out-of-order terms by combining results from all permutations of the needle. When held just right, it can efficiently match against multiple object properties, too.

---

Features

• Junk-free, high quality results that are dataset-independent. No need to fine-tune indexing options or boosting params to attain some arbitrary quality score cut-off.
• Straightforward fuzziness control that can be explained to your grandma in 5min.
• Sorting you can reason about and customize using a simple Array.sort() which gets access to each match's stats/counters. There's no composite, black box "score" to understand.
• Concise set of options that don't interact in mysterious ways to drastically alter combined behavior.
• Fast with low resource usage - there's no index to build, so startup is below 1ms with near-zero memory overhead. Searching a three-term phrase in a 162,000 phrase dataset takes 12ms with in-order terms or 50ms with out-of-order terms.
• Micro, with zero dependencies - currently < 3KB min

---

Demos

NOTE: The testdata.json file is a diverse 162,000 string/phrase dataset 4MB in size, so first load may be slow due to network transfer. Try refreshing once it's been cached by your browser.

First, uFuzzy in isolation to demonstrate its performance.

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy&search=super%20ma

Now the same comparison page, booted with fuzzysort, QuickScore, and Fuse.js:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=super%20ma

Here is the full library list but with a reduced dataset (just hearthstone_750, urls_and_titles_600) to avoid crashing your browser:

https://leeoniya.github.io/uFuzzy/demos/compare.html?lists=hearthstone_750,urls_and_titles_600&search=moo

---

Installation

Node

npm i @leeoniya/ufuzzy

const uFuzzy = require('@leeoniya/ufuzzy');

Browser

<script src="./dist/uFuzzy.iife.min.js"></script>

---

Usage

uFuzzy works in 3 phases:

1. Filter - This filters the full haystack with a fast RegExp compiled from your needle without doing any extra ops. It returns an array of matched indices in original order.
2. Info - This collects more detailed stats about the filtered matches, such as start offsets, fuzz level, prefix/suffix counters, etc. It also gathers substring match positions for range highlighting. Finally, it filters out any matches that don't conform to the desired prefix/suffix rules. To do all this it re-compiles the needle into two more-expensive RegExps that can partition each match. Therefore, it should be run on a reduced subset of the haystack, usually returned by the Filter phase. The uFuzzy demo is gated at <= 1,000 filtered items, before moving ahead with this phase.
3. Sort - This does an Array.sort() to determine final result order, utilizing the info object returned from the previous phase. A custom sort function can be provided via a uFuzzy option: {sort: (info, haystack, needle) => idxsOrder}.

let haystack = [
    'puzzle',
    'Super Awesome Thing (now with stuff!)',
    'FileName.js',
    '/feeding/the/catPic.jpg',
];

let needle = 'feed cat';

let opts = {};

let uf = new uFuzzy(opts);

// pre-filter
let idxs = uf.filter(haystack, needle);

// sort/rank only when <= 1,000 items
if (idxs.length <= 1e3) {
  let info = uf.info(idxs, haystack, needle);

  // order is a double-indirection array (a re-order of the passed-in idxs)
  // this allows corresponding info to be grabbed directly by idx, if needed
  let order = uf.sort(info, haystack, needle);

  // render post-filtered & ordered matches
  for (let i = 0; i < order.length; i++) {
    // using info.idx here instead of idxs because uf.info() may have
    // further reduced the initial idxs based on prefix/suffix rules
    console.log(haystack[info.idx[order[i]]]);
  }
}
else {
  // render pre-filtered but unordered matches
  for (let i = 0; i < idxs.length; i++) {
    console.log(haystack[i]);
  }
}

---

Options

Options with an inter prefix apply to allowances in between search terms, while those with an intra prefix apply to allowances within each search term.

Option	Description	Default	Examples
intraMax	Max number of extra chars allowed between each char within a term	0	Searching "cat"... 0 can match: cat, scat, catch, vacate 1 also matches: cart, chapter, outcast
interMax	Max number of extra chars allowed between terms	Infinity	Searching "where is"... Infinity can match: where is, where have blah wisdom 5 cannot match: where have blah wisdom
intraChars	Partial regexp for allowed extra chars between each char within a term	[a-z\d]	[a-z\d] matches only alpha-numeric (case-insensitive) [\w-] would match alpha-numeric, undercore, and hyphen
intraFilt	Callback for excluding results based on term & match	(term, match, index) => true	Do your own thing, maybe... - Length diff threshold - Levenshtein distance - Term offset or content
interChars	Partial regexp for allowed chars between terms	.	. matches all chars [^a-z\d] would only match whitespace and punctuation
interLft	Determines allowable term left boundary	0	Searching "mania"... 0 any - anywhere: romanian 1 loose - whitespace, punctuation, alpha-num, case-change transitions: TrackMania, maniac 2 strict - whitespace, punctuation: maniacally
interRgt	Determines allowable term right boundary	0	Searching "mania"... 0 any - anywhere: romanian 1 loose - whitespace, punctuation, alpha-num, case-change transitions: ManiaStar 2 strict - whitespace, punctuation: mania_foo
sort	Custom result sorting function	(info, haystack, needle) => idxsOrder	Default: Search sort, prioritizes full term matches and char density Demo: Typeahead sort, prioritizes start offset and match length

---

A biased appraisal of similar work

Forget "apples and oranges"; me comparing text search engines is closer to "planes, trains, and cars". However, that doesnt mean we cannot gain some insight into a slice of operational behavior. This assessment is extremely narrow and, of course, biased towards my use cases, text corpus, and my complete expertise in operating my own library. It is highly probable that I'm not taking full advantage of some feature in other libraries that may significantly improve outcomes along some axis; I welcome improvement PRs from anyone with deeper library knowledge than afforded by my hasty 10min skim over any "Basic usage" example and README doc.

Search quality

Can-of-worms #1.

Before we discuss performance let's talk about search quality, because speed is irrelevant when your results are a strange medly of "Oh yeah!" and "WTF?".

Search quality is very subjective. What constitutes a good top match in a "typeahead / auto-suggest" case can be a poor match in a "search / find-all" scenario. Some solutions optimize for the latter, some for the former. It's common to find knobs that skew the results in either direction, but these are often by-feel and imperfect, being little more than a proxy to producing a single, composite match "score".

Let's take a look at some matches produced by the most popular fuzzy search library, Fuse.js and a some others for which match highlighting is implemented in the demo.

Searching for the partial term "twili", we see these results appearing above numerous obvious "twilight" results:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twili

• twirling
• **The total number of received alerts that were invalid.
• Tom Clancy's Ghost Recon Wildlands - ASIA Pre-order Standard Uplay Activation
• theHunter™: Call of the Wild - Bearclaw Lite CB-60

Not only are these terrible matches in isolation, but they actually rank higher than literal substrings!

To continue the absurdity, finishing the search term to "twilight", still scores bizzare results higher:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twilight

• Magic: The Gathering - Duels of the Planeswalkers Wings of Light Unlock
• The Wild Eight

Some engines to better with partial prefix matches, at the expense of higher startup/indexing cost:

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,FlexSearch,match-sorter,MiniSearch&search=twili

Here, match-sorter returns 1,384 results, but only the first 40 are relevant. How do we know where the cut-off is?

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,FlexSearch,match-sorter,MiniSearch&search=super

Performance

Can-of-worms #2.

I've tried to follow any "best performance" advice when I could find it in each library's docs, but it's a certainty that some stones were left unturned when implementing ~20 different search engines.

The task:

1. Given a diverse list of 162,000 words and phrases, assume a Latin/Western European charset (can skip any diacritics/accents normalization)
2. Do a case-insensitive, partial/fuzzy match of the search string "super ma"
3. Sort the results in the most sensible way, following the Principle of least astonishment
4. Optionally highlight the matched substrings in each result
5. Bonus points for matches with out-of-order terms
6. Do it with the fewest resources (CPU and RAM)

Lib	Stars	Size (min)	Init	Search	Heap (peak)	Retained
uFuzzy (try)	★ 0	2.5KB	0.3ms	620ms	25.5MB	7.5MB
Fuse.js (try)	★ 14.8k	23.5KB	40ms	35432ms	306MB	14MB
FlexSearch (Light) (try)	★ 8.9k	5.9KB	3600ms	130ms	673MB	316MB
Lunr.js (try)	★ 8.2k	29.4KB	1700ms	8.7ms	295MB	120MB
LyraSearch (try)	★ 3.3k
match-sorter (try)	★ 3.1k	7.3KB	0.03ms	125ms	145MB	7.6MB
fuzzysort (try)	★ 3k	5.5KB	50ms	12ms	132MB	81MB
Wade (try)	★ 3k	4KB	920ms	3.2ms	464MB	42MB
fuzzysearch (try)	★ 2.6k
Elasticlunr.js (try)	★ 1.9k	18.1KB	1000ms	1.5ms	330MB	67MB
MiniSearch (try)	★ 1.5k	22.4KB	575ms	36ms	209MB	64MB
Fuzzyset (try)	★ 1.3k	2.8KB	2900ms	31ms	800MB	238MB
search-index (try)	★ 1.3k
LiquidMetal (try)	★ 285
ItemJS (try)	★ 260
FuzzySearch (try)	★ 184
FuzzySearch2 (try)	★ 173
QuickScore (try)	★ 131	9.1KB	26ms	489ms	260MB	12.5MB
fzy (try)	★ 115
fuzzyMatch (try)	★ 0