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); // => 5

Benchmark

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