Polyleven -- Fast Pythonic Levenshtein Library

1. Introduction

polyleven is a Pythonic Levenshtein distance library that:

• Is fast independent of input types, and hence can be used for both short (like English words) and long input types (like DNA sequences).
• Can be used readily in a manner not covered by restrictive licenses such as GPL, hence can be used freely in private codes.
• Supports Python 3.x.

2. How to install

The official package is available on PyPI:

$ pip install polyleven

3. How to use

Polyleven provides a single interface function levenshtein(). You can use this function to measure the similarity of two strings.

>>> from polyleven import levenshtein
>>> levenshtein('aaa', 'ccc')
3

If you only care about distances under a certain threshold, you can pass the max threshold to the third argument.

>>> levenshtein('acc', 'ccc', 1)
1
>>> levenshtein('aaa', 'ccc', 1)
2

In general, you can gain a noticeable speed boost with threshold k < 3.

4. Benchmark

4.1 English Words

To compare Polyleven with other Pythonic edit distance libraries, a million word pairs was generated from SCOWL.

Each library was measured how long it takes to evaluate all of these words. The following table summarises the result:

4.2. Longer Inputs

To evaluate the efficiency for longer inputs, I created 5000 pairs of random strings of size 16, 32, 64, 128, 256, 512 and 1024.

Each library was measured how fast it can process these entries. [1]

3.3. List of Libraries