I made a fork with wheels

[polm]

I forked this package and put wheels (OSX, Windows, Linux) on PyPI as levenshtein.

https://pypi.org/project/levenshtein/

This should fix compiler related issues with install that people seem to be having.

The last release of this project is from 2014, and I can't find any comments from the maintainer since 2019, so I assume they've moved on. At the moment the fork is just minimal changes to make wheels, but if there's interest I would be up for maintaining it.

[ztane]

Howdy, there is no need to fork, I can pass the maintainership forward. I have not been using python-Levenshtein for ages, back in the day it was the only fast alternative when I needed lots of string matching but its license has been a problem lately.

[Lucas-C]

Just FYI, there is another published version with wheels there : https://pypi.org/project/python-Levenshtein-wheels/ by @Tobotimus, who already opened a PR about wheel support on this repo 2 years ago: #36

Maybe the people who worked on forks & alternative Pypi releases could team up & gather their efforts on this repo,
given your proposal to hand over maintainership @ztane?

The next step could be to migrate this project into https://github.com/python-Levenshtein/python-Levenshtein and give GitHub maintainer permissions to a few volunteers who have already contributed to this package? Or submit it to https://jazzband.co?

[ztane]

@Lucas-C I looked into creating an organization. To create an organization on Github one needs to set up a single communications email for the organization, which presumably will be used for recovery and such.

[polm]

Is having a single communications email a problem? I think there still needs to be a primary maintainer if it's an organization, but presumably that mail wouldn't have to be used regularly once other admin users are added.

[maxbachmann]

@ztane I am working on a project with a similar feature set: https://github.com/maxbachmann/RapidFuzz (In fact mostly created because of the License) and I am willing to help maintaining this project

[polm]

This project is MIT Licsensed and has Levenshtein distance, so it may be a good alternative.

https://github.com/Martinsos/edlib

[maxbachmann]

edlib provides some useful information about the alignment. However at least for short input (< 128 characters) it is a lot slower, than python-Levenshtein. I did perform a benchmark for multiple Levenshtein implementations a while ago:

@ztane What is your current plan on the maintenance? A couple of things that I think would be useful (I would be willing to work on them)

• adding wheels using cibuildwheel
• Releasing new versions in form of GitHub Releases + Tags
• adding unit test + fuzz tests
• Updating the usage of the Python C API, so the library properly works in future versions of Python (A lot of the used APIs are already deprecated for years)

[woctezuma]

If I understand this plot [1] correctly, then all these libraries i) provide support for Levenshtein distance ii) in Python, and iii) for every input string length, rapidfuzz [2] and polyleven [3] are a lot faster than the other libraries.

If true, then these two libraries look more enticing anyway... So I guess I am missing something there about support for python-Levenshtein. Does python-Levenshtein provide some utility that these two other libraries miss?

On a side-note, I don't understand why the runtime seems quadratic w.r.t. the input length N for python-Levenshtein and linear for other libraries, while you mention in [1] that the time complexity:

• for python-Levenshtein is O(N*M), so O(N^2) if N=M,
• in the worst case for rapidfuzz is O(N*M) as well. You mention O([N/64]*M), but that is O(N*M) as well, right?

Shouldn't all of these plots show a quadratic curve in the case N=M?

Or is it quadratic, but due to the division by 64, the x-axis is scaled by a factor 8 when N=M?
In this case, shouldn't the performance with rapidfuzz and N=512 be on par or better than with python-Levenshtein and N=64?

Sorry if I look inquisitive, but I am curious now. :)

[1] https://maxbachmann.github.io/RapidFuzz/string_metric.html#levenshtein
[2] https://github.com/maxbachmann/RapidFuzz
[3] https://github.com/fujimotos/polyleven

[maxbachmann]

So I guess I am missing something there about support for python-Levenshtein. Does python-Levenshtein provide some utility that these two other libraries miss?

For most use cases these libraries would be a better fit, since they are faster and more open licensed. However, there are many people using python-Levenshtein. This has probably multiple reasons. Some I could think of:

1. It already exists for a long time
2. It is easier to find a library called Levenshtein than RapidFuzz/Polyleven

It makes sense to fix some of the long-standing bugs and make it compatible with future Python versions. It would be even possible to implement the Levenshtein distance in faster for python-Levenshtein as well. AFAIK this should not take a lot of time, since I already work on very similar libraries.

in the worst case for rapidfuzz is O(N*M) as well. You mention O([N/64]M), but that is O(NM) as well, right?

All the other libraries use an implementation based on Myers or Hyyrö. They convert one of the two strings into bitvectors of computer word length. Afterwards they iterate over the second string and calculate the Levenshtein distance for the whole bitvector at once using bitwise operations. In all of these implementations computer words of 64 bit are used. However it would be possible to further extend this to 128/256/512 using SIMD. You can clearly see this behavior in the graph:

1. There are steps each 64 character, since afterwards another bitvector is required
2. There is linear growth in between, since each character of the second string is compared to each bitvector.

Especially in the graph of polyleven you can see the start of the exponential growth.

In this case, shouldn't the performance with rapidfuzz and N=512 be on par or better than with python-Levenshtein and N=64?

You can not really compare them this way, since they use completely different algorithms. So the runtime for each step already takes different times. This can be seen for editdistance and edlib. Both of them use the bitparallel implementation, but have a very inefficient implementation (E.g. one of them uses a hash map which is very slow).

In my opinion RapidFuzz is the best suited of the libraries for the following reasons (as the author I am super biased)

• MIT License
• fastest Levenshtein implementation in many cases. Polyleven uses a very similar implementation. However RapidFuzz has special handling for more cases. E.g. for similar strings, for strings containing only extended ASCII ...
• It allows the use of custom weights for Insert/Deletion/Substitution in the Levenshtein distance
• It provides all the metrics of FuzzyWuzzy with efficient implementations
• It provides special functions to calculate the similarity for multiple strings at once. This can make a huge difference in performance, since it can pre-calculate some parts of the algorithm which are reused and does not have to convert between Python and C Types all the time (Python function calls are very slow)
• It provides wheels for all platforms supported on PyPi

[maxbachmann]

@ztane any updates?