Skip to content

gustf/js-levenshtein

master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
May 14, 2017 21:45
October 26, 2017 16:27
February 18, 2020 14:02
October 1, 2017 12:30
January 10, 2019 22:24
June 19, 2017 15:33

js-levenshtein Build Status

A very efficient JS implementation calculating the Levenshtein distance, i.e. the difference between two strings.

Based on Wagner-Fischer dynamic programming algorithm, optimized for speed and memory

  • use a single distance vector instead of a matrix
  • loop unrolling on the outer loop
  • remove common prefixes/postfixes from the calculation
  • minimize the number of comparisons
  • always allocate a new distance vector in order to not leak memory

Install

$ npm install --save js-levenshtein

Usage

const levenshtein = require('js-levenshtein');

levenshtein('kitten', 'sitting');
//=> 3

Benchmark

$ npm run bench
  
                      50 paragraphs, length max=500 min=240 avr=372.5
             162 op/s » js-levenshtein
              98 op/s » talisman
              94 op/s » levenshtein-edit-distance
              85 op/s » leven
              39 op/s » fast-levenshtein

                      100 sentences, length max=170 min=6 avr=57.5
           3,076 op/s » js-levenshtein
           2,024 op/s » talisman
           1,817 op/s » levenshtein-edit-distance
           1,633 op/s » leven
             800 op/s » fast-levenshtein

                      2000 words, length max=20 min=3 avr=9.5
           3,119 op/s » js-levenshtein
           2,416 op/s » talisman
           2,141 op/s » levenshtein-edit-distance
           1,855 op/s » leven
           1,260 op/s » fast-levenshtein

Benchmarks was performed with node v8.12.0 on a MacBook Pro 15", 2.9 GHz Intel Core i9

License

MIT © Gustaf Andersson