Fuse.js

Lightweight fuzzy-search, in JavaScript.

Download:

• fuse.js - (9 kb) development
• fuse.min.js - (1.58 kb) production

Why?

If you need a lightweight, fast way to search through a list of items, and allow mispellings, then Fuse.js is for you. Forget all server-side logic. This is done all in JavaScript. Check out the demo, and look at the examples below.

Try it out!

Given this list of books, try searching by misspelling the title or author's name:

Author

Title

Case sensitive

The results are sorted by score. That is, the ones that match the strongest are first.

Usage

Suppose you have the following data structure:

// List of books
var books = [{
  id: 1,
  title: 'The Great Gatsby',
  author: 'F. Scott Fitzgerald'
},{
  id: 2,
  title: 'The DaVinci Code',
  author: 'Dan Brown'
},{
  id: 3,
  title: 'Angels & Demons',
  author: 'Dan Brown'
}];

Example 1

Search and return a result list of identifiers

var options = {
  keys: ['author', 'title'],   // keys to search in
  id: 'id'                     // return a list of identifiers only
}
var f = new Fuse(books, options);
var result = f.search('brwn'); // Fuzzy-search for pattern 'brwn'

// Output:
==> [2, 3]; // The list of identifiers

Example 2

Search and return a result list of records

var options = {
  keys: ['author', 'title']
}
var f = new Fuse(books, options);
var result = f.search('brwn');

// Output:
==>
[{
  id: 2,
  title: 'The DaVinci Code',
  author: 'Dan Brown'
},{
  id: 3,
  title: 'Angels & Demons',
  author: 'Dan Brown'
}]; // List of the items

Example 3

Search over a flat array, and return the indices

var books = ["Old Man's War", "The Lock Artist", "HTML5", "Right Ho Jeeves", "The Code of the Wooster", "Thank You Jeeves", "The DaVinci Code", "Angels & Demons", "The Silmarillion", "Syrup", "The Lost Symbol", "The Book of Lies", "Lamb", "Fool", "Incompetence", "Fat", "Colony", "Backwards, Red Dwarf", "The Grand Design", "The Book of Samson", "The Preservationist", "Fallen", "Monster 1959"];

var f = new Fuse(books);
var result = f.search('Falen');

// Output:
==> [21, 15, 16]; // List of the indices

Example 4

Fuse also allows for deep key search:

// List of books
var books = [{
  id: 1,
  title: 'The Great Gatsby',
  author: {
    firstName: 'F. Scott',
    lastName: 'Fitzgerald'
  }
},{
  title: 'The DaVinci Code',
  author: {
    firstName: 'Dan',
    lastName: 'Brown'
  }
}];

var options = {
  keys: ['author.firstName']
}
var f = new Fuse(books, options);
var result = f.search('brwn');

// Output:
==>
[{
  title: 'The DaVinci Code',
  author: {
    firstName: 'Dan',
    lastName: 'Brown'
  }
}];

Options

• keys

  List of keys (properties) that will be searched.

• id

  The string name of the identifier key. If specified, the returned result will be a list of the items' identifiers, otherwise it will be a list of the items.

• threshold

  A decimal value indicating at which point the match algorithm gives up. A threshold of 0.0 requires a perfect match (of both letters and location), a threshold of 1.0 would match anything.

• caseSensitive

  A boolean value indicating whether comparisons should be case sensitive. False by default.

Limitations

This isn't meant to work across hundreds of thousands, or millions of records. If you have that many records at once on the client, then you probably have bigger problems to worry about. To give you an idea of performance, searching over 2 keys in 20,000 records takes approximately 1 second. Still, 20k records is an awful lot. Ideally, a client-side fuzzy-search solution is only acceptable if the record-set is small, and the pattern string and keys' short.

Note: the pattern string cannot exceed 32 characters.

How does it do it?

Currently, it uses a full Bitap algorithm, leveraging a modified version of the Diff, Match & Patch tool by Google.

To do

Currently planning to make it faster, and work for larger sets of data. Let me know your thoughts, ideas, or anything else.

Browser support

Fuse.js has been successfully tested in the following browsers:

• Chrome
• Safari 4+
• Firefox 3.5+
• IE 6,7,8,9+
• Opera 10.6+
• Mobile Safari (iOS 4+)

Problems?

If you encounter any problems, please use the GitHub issue tracker (GitHub account required).

For anything else, feel free to email me, or post a comment below.