• Blog
  • Archives
  • Code
  • Talks
  • About

Fast Levenshtein algorithm implementation

Note: This post is over 2 years old and may now be out of date. Some of the links not work anymore.

(1 minute read)

For my current project I needed an efficient implementation of the Levenshtein algorithm in Javascript. I had a look at the existing modules and didn't find one which implemented it efficiently as well as provide an asynchronous implementation so I decided to write my own.

It's published as an npm module called fast-levenshtein and works in both node.js and in the browser. Usage examples and other documentation is available on the github page.

My implementation is based on the optimized iterative version which does away with the need to calculate and store the entire matrix, instead just storing the last two calculated rows. My improvement on the original code is to do away with the need to copy the current row into the previous row within a separate loop at the end of each iteration.

I've included what I think is a more comprehensive set of test cases than other modules provide thus ensuring the correctness of the implementation as well as making it easier to make changes in future. And I've already come across further potential optimizations that can be made and have created issues for these.