The Levenshtein distance is infamoulsy known to run in
O(n * m) time,
m being the respective lengths of the considered strings.
But, most of the time, people just want to know whether the Levenshtein distance between two strings is below a given threshold. What's more, especially when targeting the English language, this threshold is often 1 or 2 (1 usually for the very similar Damerau-Levenshtein distance, for the reason explained in this seminal paper).
But people often miss that you can develop a custom implementation of the Levenshtein & Damerau-Levenshtein distance limited to 1 that can be way more performant.
m being the length of the shortest string. It also does not need to rely on auxiliary memory.
The library comes along with its own TypeScript definition files.
npm install levenshtein-lte1
Note that if the distance between strings exceeds
1, the functions will return
Infinity (typical implementation rather return
Infinity is kinda useful with threshold conditions).
var levenshteinLte1 = ;;>>> 0;>>> 1;>>> Infinity
var damerauLevenshteinLte1 = ;;>>> 0;>>> 1;>>> Infinity;>>> 1
Both functions also accepts arrays instead of strings if you need to apply them to arbitrary sequences.
I only benchmarked words because it usually does not make sense to test large strings with a threshold of
Disclaimer: this benchmark is deliberately unfair. It only means to demonstrate that this lib is a valid choice ONLY if your use case is to test whether strings have a Levenshtein distance less than or equal to 1.
2000 words, length max=20 min=3 avr=9.5 145,110 op/s » levenshtein-lte1 19,183 op/s » talisman-limited 3,126 op/s » node-levenshtein 2,557 op/s » js-levenshtein 2,115 op/s » talisman 1,801 op/s » levenshtein-edit-distance 1,840 op/s » leven 1,619 op/s » fast-levenshtein