fast-levenshtein

What is fast-levenshtein?

The fast-levenshtein npm package is a high-performance JavaScript implementation of the Levenshtein algorithm, which measures the difference between two sequences. It is commonly used to determine the similarity between two strings by calculating the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into the other.

What are fast-levenshtein's main functionalities?

Calculate Levenshtein distance

This feature allows you to calculate the Levenshtein distance between two strings. The code sample demonstrates how to use the package to find the distance between 'back' and 'book', which is 2.

const levenshtein = require('fast-levenshtein');
const distance = levenshtein.get('back', 'book');
console.log(distance); // Output: 2

Other packages similar to fast-levenshtein

levenshtein

This package provides a simple implementation of the Levenshtein algorithm. It is not as performance-optimized as fast-levenshtein but is straightforward to use for basic needs.

levenshtein-edit-distance

Similar to fast-levenshtein, this package calculates the Levenshtein edit distance. It focuses on being a small and fast implementation, but fast-levenshtein might still have performance advantages in certain scenarios.

string-similarity

This package goes beyond just calculating the Levenshtein distance by providing a way to compare two strings and find the similarity percentage. It uses a different algorithm for comparison and can be used for more complex string comparison tasks.

natural

Natural is a general natural language facility for Node.js. It includes a Levenshtein distance implementation among other features like tokenization, stemming, classification, phonetics, and more. It is more comprehensive but less specialized than fast-levenshtein.

README

fast-levenshtein - Levenshtein algorithm in Javascript

An efficient Javascript implementation of the Levenshtein algorithm with asynchronous callback support.

Features

• Works in node.js and in the browser.
• Better performance than other implementations by not needing to store the whole matrix (more info).
• Provides synchronous and asynchronous versions of the algorithm.
• Asynchronous version is almost as fast as the synchronous version for small strings and can also provide progress updates.
• Comprehensive test suite and performance benchmark.
• Small: <1 KB minified and gzipped

Installation

node.js

Install using npm:

$ npm install fast-levenshtein

Browser

Using bower:

$ bower install fast-levenshtein

Or the following inside your HTML:

<script type="text/javascript" src="https://github.com/hiddentao/fast-levenshtein/raw/master/levenshtein.min.js"></script>

The API will then be accessible via the window.Levenshtein object.

Examples

Synchronous

var levenshtein = require('fast-levenshtein');

var distance = levenshtein.get('back', 'book');   // 2
var distance = levenshtein.get('我愛你', '我叫你');   // 1

Asynchronous

var levenshtein = require('fast-levenshtein');

levenshtein.getAsync('back', 'book', function (err, distance) {
  // err is null unless an error was thrown
  // distance equals 2
});

Asynchronous with progress updates

var levenshtein = require('fast-levenshtein');

var hugeText1 = fs.readFileSync(...);
var hugeText2 = fs.readFileSync(...);

levenshtein.getAsync(hugeText1, hugeText2, function (err, distance) {
  // process the results as normal
}, {
  progress: function(percentComplete) {
    console.log(percentComplete + ' % completed so far...');
  }
);

Building and Testing

To build the code and run the tests:

$ npm install -g grunt-cli
$ npm install
$ npm run build

Performance

Thanks to Titus Wormer for encouraging me to do this.

Benchmarked against other node.js levenshtein distance modules (on Macbook Air 2012, Core i7, 8GB RAM):

Running suite Implementation comparison [benchmark/speed.js]...
>> levenshtein-edit-distance x 234 ops/sec ±3.02% (73 runs sampled)
>> levenshtein-component x 422 ops/sec ±4.38% (83 runs sampled)
>> levenshtein-deltas x 283 ops/sec ±3.83% (78 runs sampled)
>> natural x 255 ops/sec ±0.76% (88 runs sampled)
>> levenshtein x 180 ops/sec ±3.55% (86 runs sampled)
>> fast-levenshtein x 1,792 ops/sec ±2.72% (95 runs sampled)
Benchmark done.
Fastest test is fast-levenshtein at 4.2x faster than levenshtein-component

You can run this benchmark yourself by doing:

$ npm install -g grunt-cli
$ npm install
$ npm run build
$ npm run benchmark

Contributing

If you wish to submit a pull request please update and/or create new tests for any changes you make and ensure the grunt build passes.

See CONTRIBUTING.md for details.

License

MIT - see LICENSE.md