js-levenshtein-opt
A fork of js-levenshtein adding a threshold after which the original algorithm will stop calculating the distance between two inputs.
Install
$ npm i @joogl/js-levenshtein-opt
Usage
const levenshtein = require('js-levenshtein-opt');
// Original algorithm available without a third argument.
levenshtein('kitten', 'sitting'); // => 3
// Adding a limitation will stop the calculation as soon as the limit is met.
levenshtein('kitten', 'sitting', 5); // => 3
levenshtein('kitten', 'ambiguous', 5); // => 5Benchmark
| Test | Limit 0 ops | Limit 3 ops | Limit 5 ops | Limit 10 ops |
|---|---|---|---|---|
| Paragraphs | 123 | 209,363 | 222,938 | 216,120 |
| Sentences | 2,374 | 561,027 | 207,529 | 112,869 |
| Words | 2,389 | 9,797 | 6,115 | 2,106 |
These benchmarks were done in the integrated test suite on a Ryzen 7 1700 Eight-Core @ 3 GHz and Node v8.11.1.
The package provides significant performance boosts for paragraphs and sentences. Distance calculation for words can be sped up to 5 times, but declines quickly the higher the limit. If comparing single words, it is recommended to use the algorithm without limitation starting at a distance limit of 10.
License
MIT © Gustaf Andersson