fastest-levenshtein

What is fastest-levenshtein?

The fastest-levenshtein npm package is a JavaScript library that provides an efficient implementation of the Levenshtein distance algorithm, which is used to measure the difference between two sequences of characters. The package is optimized for performance and is useful for tasks such as fuzzy matching, spell checking, and similarity checking between strings.

What are fastest-levenshtein's main functionalities?

distance

Calculates the Levenshtein distance between two strings, which is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into the other.

const { distance } = require('fastest-levenshtein');
const dist = distance('kitten', 'sitting');
console.log(dist); // Output: 3

Other packages similar to fastest-levenshtein

levenshtein

This package provides a simple implementation of the Levenshtein distance algorithm. It is not as performance-optimized as fastest-levenshtein but is widely used for its simplicity and ease of understanding.

levenshtein-edit-distance

This is another package that calculates the Levenshtein distance between two strings. It focuses on accuracy and has a simple API, but it may not be as fast as fastest-levenshtein for large strings or a high number of calculations.

string-similarity

This package goes beyond just the Levenshtein distance and provides a way to find the degree of similarity between two strings. It also includes a method for finding the best match in an array of strings. While it offers more features, it might not be as fast as fastest-levenshtein when only the Levenshtein distance is needed.

natural

Natural is a general natural language facility for Node.js. It includes a Levenshtein distance implementation among many other features for processing human language. It's more comprehensive but also larger and potentially slower than fastest-levenshtein, which is specialized for Levenshtein distance calculations.

README

fastest-levenshtein :rocket:

Fastest JavaScript implementation of the Levenshtein distance algorithm - (up to 10x+ faster than closest competitor). This algorithm can be used to measure the similarity of two strings.

Note: if you need to take the edit distance of one string against many strings (maybe billions), I have created a GPU-implementation that will be atleast 1000x faster than this. Contact me, if you're interested.

$ npm install fastest-levenshtein --save

Usage

const {distance, closest} = require('fastest-levenshtein')

// Print levenshtein-distance between 'fast' and 'faster' 
console.log(distance('fast', 'faster'))
//=> 2

// Print string from array with lowest edit-distance to 'fast'
console.log(closest('fast', ['slow', 'faster', 'fastest']))
//=> 'faster'

Benchmark

I generated 500 pairs of strings with length N. I measured the ops/sec each library achieves to process all the given pairs. Higher is better. fastest-levenshtein is a lot faster in all cases.

Test Target	N=4	N=8	N=16	N=32	N=64	N=128	N=256	N=512	N=1024
fastest-levenshtein	44423	23702	10764	4595	1049	291.5	86.64	22.24	5.473
js-levenshtein	21261	10030	2939	824	223	57.62	14.77	3.717	0.934
leven	19688	6884	1606	436	117	30.34	7.604	1.929	0.478
fast-levenshtein	18577	6112	1265	345	89.41	22.70	5.676	1.428	0.348
levenshtein-edit-distance	22968	7445	1493	409	109	28.07	7.095	1.789	0.445

Relative Performance

This image shows the relative performance between fastest-levenshtein and js-levenshtein (the 2nd fastest). As you can see, fastest-levenshtein is always a lot faster.

License

This project is licensed under the MIT License - see the LICENSE.md file for details