1 # fast-levenshtein - Levenshtein algorithm in Javascript
3 [![Build Status](https://secure.travis-ci.org/hiddentao/fast-levenshtein.png)](http://travis-ci.org/hiddentao/fast-levenshtein)
4 [![NPM module](https://badge.fury.io/js/fast-levenshtein.png)](https://badge.fury.io/js/fast-levenshtein)
5 [![NPM downloads](https://img.shields.io/npm/dm/fast-levenshtein.svg?maxAge=2592000)](https://www.npmjs.com/package/fast-levenshtein)
6 [![Follow on Twitter](https://img.shields.io/twitter/url/http/shields.io.svg?style=social&label=Follow&maxAge=2592000)](https://twitter.com/hiddentao)
8 An efficient Javascript implementation of the [Levenshtein algorithm](http://en.wikipedia.org/wiki/Levenshtein_distance) with locale-specific collator support.
12 * Works in node.js and in the browser.
13 * Better performance than other implementations by not needing to store the whole matrix ([more info](http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm)).
14 * Locale-sensitive string comparisions if needed.
15 * Comprehensive test suite and performance benchmark.
16 * Small: <1 KB minified and gzipped
22 Install using [npm](http://npmjs.org/):
25 $ npm install fast-levenshtein
33 $ bower install fast-levenshtein
36 If you are not using any module loader system then the API will then be accessible via the `window.Levenshtein` object.
43 var levenshtein = require('fast-levenshtein');
45 var distance = levenshtein.get('back', 'book'); // 2
46 var distance = levenshtein.get('我愛你', '我叫你'); // 1
49 **Locale-sensitive string comparisons**
51 It supports using [Intl.Collator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator) for locale-sensitive string comparisons:
54 var levenshtein = require('fast-levenshtein');
56 levenshtein.get('mikailovitch', 'Mikhaïlovitch', { useCollator: true});
60 ## Building and Testing
62 To build the code and run the tests:
65 $ npm install -g grunt-cli
72 _Thanks to [Titus Wormer](https://github.com/wooorm) for [encouraging me](https://github.com/hiddentao/fast-levenshtein/issues/1) to do this._
74 Benchmarked against other node.js levenshtein distance modules (on Macbook Air 2012, Core i7, 8GB RAM):
77 Running suite Implementation comparison [benchmark/speed.js]...
78 >> levenshtein-edit-distance x 234 ops/sec ±3.02% (73 runs sampled)
79 >> levenshtein-component x 422 ops/sec ±4.38% (83 runs sampled)
80 >> levenshtein-deltas x 283 ops/sec ±3.83% (78 runs sampled)
81 >> natural x 255 ops/sec ±0.76% (88 runs sampled)
82 >> levenshtein x 180 ops/sec ±3.55% (86 runs sampled)
83 >> fast-levenshtein x 1,792 ops/sec ±2.72% (95 runs sampled)
85 Fastest test is fast-levenshtein at 4.2x faster than levenshtein-component
88 You can run this benchmark yourself by doing:
98 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.
100 See [CONTRIBUTING.md](https://github.com/hiddentao/fast-levenshtein/blob/master/CONTRIBUTING.md) for details.
104 MIT - see [LICENSE.md](https://github.com/hiddentao/fast-levenshtein/blob/master/LICENSE.md)