1 | # fast-levenshtein - Levenshtein algorithm in Javascript
|
2 |
|
3 | [![Build Status](https://secure.travis-ci.org/hiddentao/fast-levenshtein.png)](http://travis-ci.org/hiddentao/fast-levenshtein)
|
4 |
|
5 | An efficient Javascript implementation of the [Levenshtein algorithm](http://en.wikipedia.org/wiki/Levenshtein_distance) with asynchronous callback support.
|
6 |
|
7 | ## Features
|
8 |
|
9 | * Works in node.js and in the browser.
|
10 | * 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)).
|
11 | * Provides synchronous and asynchronous versions of the algorithm.
|
12 | * Asynchronous version is almost as fast as the synchronous version for small strings and can also provide progress updates.
|
13 | * Comprehensive test suite and performance benchmark.
|
14 | * Small: <1 KB minified and gzipped
|
15 |
|
16 | ## Installation
|
17 |
|
18 | ### node.js
|
19 |
|
20 | Install using [npm](http://npmjs.org/):
|
21 |
|
22 | ```bash
|
23 | $ npm install fast-levenshtein
|
24 | ```
|
25 |
|
26 | ### Browser
|
27 |
|
28 | Using bower:
|
29 |
|
30 | ```bash
|
31 | $ bower install fast-levenshtein
|
32 | ```
|
33 |
|
34 | If you are not using any module loader system then the API will then be accessible via the `window.Levenshtein` object.
|
35 |
|
36 | ## Examples
|
37 |
|
38 | **Synchronous**
|
39 |
|
40 | ```javascript
|
41 | var levenshtein = require('fast-levenshtein');
|
42 |
|
43 | var distance = levenshtein.get('back', 'book'); // 2
|
44 | var distance = levenshtein.get('我愛你', '我叫你'); // 1
|
45 | ```
|
46 |
|
47 | **Asynchronous**
|
48 |
|
49 | ```javascript
|
50 | var levenshtein = require('fast-levenshtein');
|
51 |
|
52 | levenshtein.getAsync('back', 'book', function (err, distance) {
|
53 | // err is null unless an error was thrown
|
54 | // distance equals 2
|
55 | });
|
56 | ```
|
57 |
|
58 | **Asynchronous with progress updates**
|
59 |
|
60 | ```javascript
|
61 | var levenshtein = require('fast-levenshtein');
|
62 |
|
63 | var hugeText1 = fs.readFileSync(...);
|
64 | var hugeText2 = fs.readFileSync(...);
|
65 |
|
66 | levenshtein.getAsync(hugeText1, hugeText2, function (err, distance) {
|
67 | // process the results as normal
|
68 | }, {
|
69 | progress: function(percentComplete) {
|
70 | console.log(percentComplete + ' % completed so far...');
|
71 | }
|
72 | );
|
73 | ```
|
74 |
|
75 | ## Building and Testing
|
76 |
|
77 | To build the code and run the tests:
|
78 |
|
79 | ```bash
|
80 | $ npm install -g grunt-cli
|
81 | $ npm install
|
82 | $ npm run build
|
83 | ```
|
84 |
|
85 | ## Performance
|
86 |
|
87 | _Thanks to [Titus Wormer](https://github.com/wooorm) for [encouraging me](https://github.com/hiddentao/fast-levenshtein/issues/1) to do this._
|
88 |
|
89 | Benchmarked against other node.js levenshtein distance modules (on Macbook Air 2012, Core i7, 8GB RAM):
|
90 |
|
91 | ```bash
|
92 | Running suite Implementation comparison [benchmark/speed.js]...
|
93 | >> levenshtein-edit-distance x 234 ops/sec ±3.02% (73 runs sampled)
|
94 | >> levenshtein-component x 422 ops/sec ±4.38% (83 runs sampled)
|
95 | >> levenshtein-deltas x 283 ops/sec ±3.83% (78 runs sampled)
|
96 | >> natural x 255 ops/sec ±0.76% (88 runs sampled)
|
97 | >> levenshtein x 180 ops/sec ±3.55% (86 runs sampled)
|
98 | >> fast-levenshtein x 1,792 ops/sec ±2.72% (95 runs sampled)
|
99 | Benchmark done.
|
100 | Fastest test is fast-levenshtein at 4.2x faster than levenshtein-component
|
101 | ```
|
102 |
|
103 | You can run this benchmark yourself by doing:
|
104 |
|
105 | ```bash
|
106 | $ npm install -g grunt-cli
|
107 | $ npm install
|
108 | $ npm run build
|
109 | $ npm run benchmark
|
110 | ```
|
111 |
|
112 | ## Contributing
|
113 |
|
114 | 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.
|
115 |
|
116 | See [CONTRIBUTING.md](https://github.com/hiddentao/fast-levenshtein/blob/master/CONTRIBUTING.md) for details.
|
117 |
|
118 | ## License
|
119 |
|
120 | MIT - see [LICENSE.md](https://github.com/hiddentao/fast-levenshtein/blob/master/LICENSE.md)
|