Turboshtein

Background

I didn’t study computer science so the usefulness of bit shifts and other bitwise operations outside of low-level programming have always been a bit of a gray area for me. I finally gave in and decided to spend some time reading up on the subject and ended up implementing the Myers bit-vector algorithm¹ for computing Levenshtein edit distance. I was fairly happy with the results so I wrapped the original C code in Python and uploaded it to PyPI. Coincidentally, it’s also pretty fast.

Usage

To start using Turboshtein, simply install it via PyPi:

pip install turboshtein

Once installed, computing Levenshtein edit distance then becomes as easy as:

>>> from turboshtein import levenshtein
>>> levenshtein("saturday", "sunday")
3

Note, that this particular implementation is limited to ASCII strings of less than 64 characters.

Performance

After implementing the algorithm, I was curious as to what the real world performance looked like. Given a query of length m and a string length of n, its been shown that the edit distance can be computed in O(mn) time.² The approach as described by Myers offers a considerable improvement and requires only O(mn/w) where w is the register size (64-bit in this case). For comparison, I included a handful of the most popular libraries that include a Levenshtein distance function.

These values are obviously hardware dependent, but on my dusty laptop I was consistently getting a higher throughput with Turboshtein. For example, with strings of less than 24 characters, Turboshtein is able to crunch through a minimum of 600k additional string pairs per second relative to the next fastest library. For short strings (16 characters or less), that figure jumps up to an additional 800k string pairs per second. Test setup was as follows:

Final thoughts

If you’re curious as to what the implementation looks like, here is the repo. I suppose at some point, I ought to implement support for non-ASCII characters so maybe check back in the future…