miohtama/python-levenshtein

The Levenshtein Python C extension module contains functions for fast computation of Levenshtein distance and string similarity

Contents

• Maintainer needed
• Introduction
• Documentation
• License
• History
• Source code
• Authors

Maintainer needed

I (Mikko Ohtamaa) am not currently maintaining this code. I just pulled in to Github for general good (was not available in public repo before). So if you file any issues I won't be looking into them.

Introduction

The Levenshtein Python C extension module contains functions for fast computation of

• Levenshtein (edit) distance, and edit operations
• string similarity
• approximate median strings, and generally string averaging
• string sequence and set similarity

It supports both normal and Unicode strings.

Python 2.2 or newer is required.

StringMatcher.py is an example SequenceMatcher-like class built on the top of Levenshtein. It misses some SequenceMatcher's functionality, and has some extra OTOH.

Levenshtein.c can be used as a pure C library, too. You only have to define NO_PYTHON preprocessor symbol (-DNO_PYTHON) when compiling it. The functionality is similar to that of the Python extension. No separate docs are provided yet, RTFS. But they are not interchangeable:

• C functions exported when compiling with -DNO_PYTHON (see Levenshtein.h) are not exported when compiling as a Python extension (and vice versa)
• Unicode character type used with -DNO_PYTHON is wchar_t, Python extension uses Py_UNICODE, they may be the same but don't count on it

Documentation

gendoc.sh generates HTML API documentation, you probably want a selfcontained instead of includable version, so run in ./gendoc.sh --selfcontained. It needs Levenshtein already installed and genextdoc.py.

License

Levenshtein can be copied and/or modified under the terms of GNU General Public License, see the file COPYING for full license text.

History

This package was long missing from PyPi and available as source checkout only. We needed to restore this package for Go Mobile for Plone and Pywurfl projects which depend on this.

The project is not under active development as far as the maintainer knows.

Source code

• http://github.com/miohtama/python-Levenshtein/tree/

Authors

• Maintainer: Mikko Ohtamaa - I am not actively doing anything for this, please feel free take over PyPi and Github administration
• David Necas (Yeti) <yeti at physics.muni.cz>

python-levenshtein's Issues

Incorrect unicode

In utf-8 (cyrilic letters) Russian name Sergey, Serezha, Sergunia

a = ['сергей', 'сережа', 'сергуня']
print median_improve('серг', a)
сергЃЏ

In unicode

a = [u'сергей', u'сережа',u'сергуня']
print median_improve(u'серг', a)
�е�г��

get_matching_blocks() does not align with ratio()

Example: For strings "abc" and "dac", get_matching_blocks() gives (2, 2, 1), (3, 3, 0) as matching blocks, that is, the substrings "c" and "" from the two strings.

Based on the matching blocks (2, 2, 1), (3, 3, 0) returned by get_matching_blocks(), the Levenshtein ratio would be 2 * (1 + 0) / (3 + 3) = 0.333... However, the ratio() is 0.666... In fact ratio() should be the correct one, because in the sense of "minimal string distance" we should indeed regard "a" and "c" as the two best matching blocks, yielding 2 * (1 + 1) / (3 + 3) = 0.666... So why doesn't get_matching_blocks() capture "a", i.e. (0, 1, 1), also as a matching block?

It's sad to learn that this library is currently not being maintained. I just leave this open quesition here and hope for someone's answer in maybe 2030 :)

The library shouldn't use setuptools package at runtime.

With pip-compile tool, I can pin all my project's packages versions and hashes.
It seems that a problem arises when I try to pin python-Levenshtein library, because it tries to use setuptools at runtime.
Hence, the pip-compile tool will try to pin setuptools, while it shoudn't.

This is the output of pip-compile, and if you search setuptools, you can clearly see that the pip-compile warning in the last line, complaining of pinning setuptools, it's your library fault.

Using indexes:

  | https://pypi.org/simple
  |  
  | ROUND 1
  | Current constraints:
  | attrdict (from -r -)
  | bs4 (from -r -)
  | colorama (from -r -)
  | fuzzywuzzy (from -r -)
  | humanize (from -r -)
  | lxml (from -r -)
  | matplotlib (from -r -)
  | prompt_toolkit (from -r -)
  | pycairo (from -r -)
  | pygments (from -r -)
  | pytest (from -r -)
  | python-dateutil (from -r -)
  | python-Levenshtein (from -r -)
  | regex (from -r -)
  |  
  | Finding the best candidates:
  | found candidate attrdict==2.0.1 (constraint was )
  | found candidate bs4==0.0.1 (constraint was )
  | found candidate colorama==0.4.3 (constraint was )
  | found candidate fuzzywuzzy==0.18.0 (constraint was )
  | found candidate humanize==2.4.0 (constraint was )
  | found candidate lxml==4.5.1 (constraint was )
  | found candidate matplotlib==3.2.2 (constraint was )
  | found candidate prompt-toolkit==3.0.5 (constraint was )
  | found candidate pycairo==1.19.1 (constraint was )
  | found candidate pygments==2.6.1 (constraint was )
  | found candidate pytest==5.4.3 (constraint was )
  | found candidate python-dateutil==2.8.1 (constraint was )
  | found candidate python-levenshtein==0.12.0 (constraint was )
  | found candidate regex==2020.6.8 (constraint was )
  |  
  | Finding secondary dependencies:
  | matplotlib==3.2.2 not in cache, need to check index
  | Collecting matplotlib==3.2.2
  | Using cached matplotlib-3.2.2-cp37-cp37m-manylinux1_x86_64.whl (12.4 MB)
  | Saved /home/rendar/.cache/pip-tools/wheels/matplotlib-3.2.2-cp37-cp37m-manylinux1_x86_64.whl
  | matplotlib==3.2.2         requires cycler>=0.10, kiwisolver>=1.0.1, numpy>=1.11, pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1, python-dateutil>=2.1
  | pygments==2.6.1 not in cache, need to check index
  | Collecting pygments==2.6.1
  | Using cached Pygments-2.6.1-py3-none-any.whl (914 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/Pygments-2.6.1-py3-none-any.whl
  | pygments==2.6.1           requires -
  | fuzzywuzzy==0.18.0 not in cache, need to check index
  | Collecting fuzzywuzzy==0.18.0
  | Using cached fuzzywuzzy-0.18.0-py2.py3-none-any.whl (18 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/fuzzywuzzy-0.18.0-py2.py3-none-any.whl
  | fuzzywuzzy==0.18.0        requires -
  | lxml==4.5.1               requires -
  | pytest==5.4.3             requires attrs>=17.4.0, importlib-metadata>=0.12; python_version < "3.8", more-itertools>=4.0.0, packaging, pluggy<1.0,>=0.12, py>=1.5.0, wcwidth
  | pycairo==1.19.1 not in cache, need to check index
  | Collecting pycairo==1.19.1
  | Using cached pycairo-1.19.1.tar.gz (205 kB)
  | Saved /home/rendar/.cache/pip-tools/pkgs/pycairo-1.19.1.tar.gz
  | pycairo==1.19.1           requires -
  | python-levenshtein==0.12.0 not in cache, need to check index
  | Collecting python-Levenshtein==0.12.0
  | Using cached python-Levenshtein-0.12.0.tar.gz (48 kB)
  | Saved /home/rendar/.cache/pip-tools/pkgs/python-Levenshtein-0.12.0.tar.gz
  | python-levenshtein==0.12.0 requires setuptools
  | colorama==0.4.3           requires -
  | prompt-toolkit==3.0.5     requires wcwidth
  | python-dateutil==2.8.1 not in cache, need to check index
  | Collecting python-dateutil==2.8.1
  | Using cached python_dateutil-2.8.1-py2.py3-none-any.whl (227 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/python_dateutil-2.8.1-py2.py3-none-any.whl
  | python-dateutil==2.8.1    requires six>=1.5
  | attrdict==2.0.1 not in cache, need to check index
  | Collecting attrdict==2.0.1
  | Using cached attrdict-2.0.1-py2.py3-none-any.whl (9.9 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/attrdict-2.0.1-py2.py3-none-any.whl
  | attrdict==2.0.1           requires six
  | regex==2020.6.8 not in cache, need to check index
  | Collecting regex==2020.6.8
  | Using cached regex-2020.6.8-cp37-cp37m-manylinux2010_x86_64.whl (661 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/regex-2020.6.8-cp37-cp37m-manylinux2010_x86_64.whl
  | regex==2020.6.8           requires -
  | bs4==0.0.1                requires beautifulsoup4
  | humanize==2.4.0 not in cache, need to check index
  | Collecting humanize==2.4.0
  | Using cached humanize-2.4.0-py3-none-any.whl (62 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/humanize-2.4.0-py3-none-any.whl
  | humanize==2.4.0           requires -
  |  
  | New dependencies found in this round:
  | adding ['attrs', '>=17.4.0', '[]']
  | adding ['beautifulsoup4', '', '[]']
  | adding ['cycler', '>=0.10', '[]']
  | adding ['importlib-metadata', '>=0.12', '[]']
  | adding ['kiwisolver', '>=1.0.1', '[]']
  | adding ['more-itertools', '>=4.0.0', '[]']
  | adding ['numpy', '>=1.11', '[]']
  | adding ['packaging', '', '[]']
  | adding ['pluggy', '<1.0,>=0.12', '[]']
  | adding ['py', '>=1.5.0', '[]']
  | adding ['pyparsing', '!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1', '[]']
  | adding ['python-dateutil', '>=2.1', '[]']
  | adding ['setuptools', '', '[]']
  | adding ['six', '>=1.5', '[]']
  | adding ['wcwidth', '', '[]']
  | Removed dependencies in this round:
  | ------------------------------------------------------------
  | Result of round 1: not stable
  |  
  | ROUND 2
  | Current constraints:
  | attrdict (from -r -)
  | attrs>=17.4.0 (from pytest==5.4.3->-r -)
  | beautifulsoup4 (from bs4==0.0.1->-r -)
  | bs4 (from -r -)
  | colorama (from -r -)
  | cycler>=0.10 (from matplotlib==3.2.2->-r -)
  | fuzzywuzzy (from -r -)
  | humanize (from -r -)
  | importlib-metadata>=0.12 (from pytest==5.4.3->-r -)
  | kiwisolver>=1.0.1 (from matplotlib==3.2.2->-r -)
  | lxml (from -r -)
  | matplotlib (from -r -)
  | more-itertools>=4.0.0 (from pytest==5.4.3->-r -)
  | numpy>=1.11 (from matplotlib==3.2.2->-r -)
  | packaging (from pytest==5.4.3->-r -)
  | pluggy<1.0,>=0.12 (from pytest==5.4.3->-r -)
  | prompt_toolkit (from -r -)
  | py>=1.5.0 (from pytest==5.4.3->-r -)
  | pycairo (from -r -)
  | pygments (from -r -)
  | pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1 (from matplotlib==3.2.2->-r -)
  | pytest (from -r -)
  | python-dateutil>=2.1 (from -r -)
  | python-Levenshtein (from -r -)
  | regex (from -r -)
  | setuptools (from python-Levenshtein==0.12.0->-r -)
  | six>=1.5 (from attrdict==2.0.1->-r -)
  | wcwidth (from pytest==5.4.3->-r -)
  |  
  | Finding the best candidates:
  | found candidate attrdict==2.0.1 (constraint was )
  | found candidate attrs==19.3.0 (constraint was >=17.4.0)
  | found candidate beautifulsoup4==4.9.1 (constraint was )
  | found candidate bs4==0.0.1 (constraint was )
  | found candidate colorama==0.4.3 (constraint was )
  | found candidate cycler==0.10.0 (constraint was >=0.10)
  | found candidate fuzzywuzzy==0.18.0 (constraint was )
  | found candidate humanize==2.4.0 (constraint was )
  | found candidate importlib-metadata==1.6.1 (constraint was >=0.12)
  | found candidate kiwisolver==1.2.0 (constraint was >=1.0.1)
  | found candidate lxml==4.5.1 (constraint was )
  | found candidate matplotlib==3.2.2 (constraint was )
  | found candidate more-itertools==8.4.0 (constraint was >=4.0.0)
  | found candidate numpy==1.19.0 (constraint was >=1.11)
  | found candidate packaging==20.4 (constraint was )
  | found candidate pluggy==0.13.1 (constraint was >=0.12,<1.0)
  | found candidate prompt-toolkit==3.0.5 (constraint was )
  | found candidate py==1.8.2 (constraint was >=1.5.0)
  | found candidate pycairo==1.19.1 (constraint was )
  | found candidate pygments==2.6.1 (constraint was )
  | found candidate pyparsing==2.4.7 (constraint was >=2.0.1,!=2.0.4,!=2.1.2,!=2.1.6)
  | found candidate pytest==5.4.3 (constraint was )
  | found candidate python-dateutil==2.8.1 (constraint was >=2.1)
  | found candidate python-levenshtein==0.12.0 (constraint was )
  | found candidate regex==2020.6.8 (constraint was )
  | found candidate setuptools==47.3.1 (constraint was )
  | found candidate six==1.15.0 (constraint was >=1.5)
  | found candidate wcwidth==0.2.4 (constraint was )
  |  
  | Finding secondary dependencies:
  | bs4==0.0.1                requires beautifulsoup4
  | prompt-toolkit==3.0.5     requires wcwidth
  | colorama==0.4.3           requires -
  | six==1.15.0               requires -
  | pytest==5.4.3             requires attrs>=17.4.0, importlib-metadata>=0.12; python_version < "3.8", more-itertools>=4.0.0, packaging, pluggy<1.0,>=0.12, py>=1.5.0, wcwidth
  | fuzzywuzzy==0.18.0        requires -
  | attrdict==2.0.1           requires six
  | cycler==0.10.0 not in cache, need to check index
  | Collecting cycler==0.10.0
  | Using cached cycler-0.10.0-py2.py3-none-any.whl (6.5 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/cycler-0.10.0-py2.py3-none-any.whl
  | cycler==0.10.0            requires six
  | py==1.8.2                 requires -
  | lxml==4.5.1               requires -
  | more-itertools==8.4.0     requires -
  | packaging==20.4           requires pyparsing>=2.0.2, six
  | wcwidth==0.2.4            requires -
  | python-dateutil==2.8.1    requires six>=1.5
  | setuptools==47.3.1        requires -
  | pygments==2.6.1           requires -
  | attrs==19.3.0             requires -
  | humanize==2.4.0           requires -
  | kiwisolver==1.2.0 not in cache, need to check index
  | Collecting kiwisolver==1.2.0
  | Using cached kiwisolver-1.2.0-cp37-cp37m-manylinux1_x86_64.whl (88 kB)
  | Saved /home/rendar/.cache/pip-tools/wheels/kiwisolver-1.2.0-cp37-cp37m-manylinux1_x86_64.whl
  | kiwisolver==1.2.0         requires -
  | numpy==1.19.0 not in cache, need to check index
  | Collecting numpy==1.19.0
  | Using cached numpy-1.19.0-cp37-cp37m-manylinux2010_x86_64.whl (14.6 MB)
  | Saved /home/rendar/.cache/pip-tools/wheels/numpy-1.19.0-cp37-cp37m-manylinux2010_x86_64.whl
  | numpy==1.19.0             requires -
  | pyparsing==2.4.7          requires -
  | pluggy==0.13.1            requires importlib-metadata>=0.12; python_version < "3.8"
  | importlib-metadata==1.6.1 requires zipp>=0.5
  | pycairo==1.19.1           requires -
  | regex==2020.6.8           requires -
  | matplotlib==3.2.2         requires cycler>=0.10, kiwisolver>=1.0.1, numpy>=1.11, pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1, python-dateutil>=2.1
  | beautifulsoup4==4.9.1     requires soupsieve>1.2
  | python-levenshtein==0.12.0 requires setuptools
  |  
  | New dependencies found in this round:
  | adding ['pyparsing', '!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1,>=2.0.2', '[]']
  | adding ['soupsieve', '>1.2', '[]']
  | adding ['zipp', '>=0.5', '[]']
  | Removed dependencies in this round:
  | removing ['pyparsing', '!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1', '[]']
  | ------------------------------------------------------------
  | Result of round 2: not stable
  |  
  | ROUND 3
  | Current constraints:
  | attrdict (from -r -)
  | attrs>=17.4.0 (from pytest==5.4.3->-r -)
  | beautifulsoup4 (from bs4==0.0.1->-r -)
  | bs4 (from -r -)
  | colorama (from -r -)
  | cycler>=0.10 (from matplotlib==3.2.2->-r -)
  | fuzzywuzzy (from -r -)
  | humanize (from -r -)
  | importlib-metadata>=0.12 (from pytest==5.4.3->-r -)
  | kiwisolver>=1.0.1 (from matplotlib==3.2.2->-r -)
  | lxml (from -r -)
  | matplotlib (from -r -)
  | more-itertools>=4.0.0 (from pytest==5.4.3->-r -)
  | numpy>=1.11 (from matplotlib==3.2.2->-r -)
  | packaging (from pytest==5.4.3->-r -)
  | pluggy<1.0,>=0.12 (from pytest==5.4.3->-r -)
  | prompt_toolkit (from -r -)
  | py>=1.5.0 (from pytest==5.4.3->-r -)
  | pycairo (from -r -)
  | pygments (from -r -)
  | pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1,>=2.0.2 (from matplotlib==3.2.2->-r -)
  | pytest (from -r -)
  | python-dateutil>=2.1 (from -r -)
  | python-Levenshtein (from -r -)
  | regex (from -r -)
  | setuptools (from python-Levenshtein==0.12.0->-r -)
  | six>=1.5 (from attrdict==2.0.1->-r -)
  | soupsieve>1.2 (from beautifulsoup4==4.9.1->bs4==0.0.1->-r -)
  | wcwidth (from pytest==5.4.3->-r -)
  | zipp>=0.5 (from importlib-metadata==1.6.1->pytest==5.4.3->-r -)
  |  
  | Finding the best candidates:
  | found candidate attrdict==2.0.1 (constraint was )
  | found candidate attrs==19.3.0 (constraint was >=17.4.0)
  | found candidate beautifulsoup4==4.9.1 (constraint was )
  | found candidate bs4==0.0.1 (constraint was )
  | found candidate colorama==0.4.3 (constraint was )
  | found candidate cycler==0.10.0 (constraint was >=0.10)
  | found candidate fuzzywuzzy==0.18.0 (constraint was )
  | found candidate humanize==2.4.0 (constraint was )
  | found candidate importlib-metadata==1.6.1 (constraint was >=0.12)
  | found candidate kiwisolver==1.2.0 (constraint was >=1.0.1)
  | found candidate lxml==4.5.1 (constraint was )
  | found candidate matplotlib==3.2.2 (constraint was )
  | found candidate more-itertools==8.4.0 (constraint was >=4.0.0)
  | found candidate numpy==1.19.0 (constraint was >=1.11)
  | found candidate packaging==20.4 (constraint was )
  | found candidate pluggy==0.13.1 (constraint was >=0.12,<1.0)
  | found candidate prompt-toolkit==3.0.5 (constraint was )
  | found candidate py==1.8.2 (constraint was >=1.5.0)
  | found candidate pycairo==1.19.1 (constraint was )
  | found candidate pygments==2.6.1 (constraint was )
  | found candidate pyparsing==2.4.7 (constraint was >=2.0.1,>=2.0.2,!=2.0.4,!=2.1.2,!=2.1.6)
  | found candidate pytest==5.4.3 (constraint was )
  | found candidate python-dateutil==2.8.1 (constraint was >=2.1)
  | found candidate python-levenshtein==0.12.0 (constraint was )
  | found candidate regex==2020.6.8 (constraint was )
  | found candidate setuptools==47.3.1 (constraint was )
  | found candidate six==1.15.0 (constraint was >=1.5)
  | found candidate soupsieve==2.0.1 (constraint was >1.2)
  | found candidate wcwidth==0.2.4 (constraint was )
  | found candidate zipp==3.1.0 (constraint was >=0.5)
  |  
  | Finding secondary dependencies:
  | colorama==0.4.3           requires -
  | pygments==2.6.1           requires -
  | six==1.15.0               requires -
  | python-dateutil==2.8.1    requires six>=1.5
  | wcwidth==0.2.4            requires -
  | numpy==1.19.0             requires -
  | humanize==2.4.0           requires -
  | py==1.8.2                 requires -
  | fuzzywuzzy==0.18.0        requires -
  | attrs==19.3.0             requires -
  | soupsieve==2.0.1          requires -
  | pycairo==1.19.1           requires -
  | lxml==4.5.1               requires -
  | zipp==3.1.0               requires -
  | more-itertools==8.4.0     requires -
  | pluggy==0.13.1            requires importlib-metadata>=0.12; python_version < "3.8"
  | python-levenshtein==0.12.0 requires setuptools
  | regex==2020.6.8           requires -
  | bs4==0.0.1                requires beautifulsoup4
  | kiwisolver==1.2.0         requires -
  | cycler==0.10.0            requires six
  | packaging==20.4           requires pyparsing>=2.0.2, six
  | matplotlib==3.2.2         requires cycler>=0.10, kiwisolver>=1.0.1, numpy>=1.11, pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1, python-dateutil>=2.1
  | prompt-toolkit==3.0.5     requires wcwidth
  | importlib-metadata==1.6.1 requires zipp>=0.5
  | pyparsing==2.4.7          requires -
  | pytest==5.4.3             requires attrs>=17.4.0, importlib-metadata>=0.12; python_version < "3.8", more-itertools>=4.0.0, packaging, pluggy<1.0,>=0.12, py>=1.5.0, wcwidth
  | setuptools==47.3.1        requires -
  | attrdict==2.0.1           requires six
  | beautifulsoup4==4.9.1     requires soupsieve>1.2
  | ------------------------------------------------------------
  | Result of round 3: stable, done
  |  
  | Generating hashes:
  | colorama
  | pygments
  | six
  | attrdict
  | python-dateutil
  | numpy
  | humanize
  | py
  | fuzzywuzzy
  | attrs
  | soupsieve
  | pycairo
  | lxml
  | zipp
  | more-itertools
  | pluggy
  | regex
  | python-Levenshtein
  | bs4
  | kiwisolver
  | cycler
  | packaging
  | matplotlib
  | prompt-toolkit
  | importlib-metadata
  | pyparsing
  | pytest
  | wcwidth
  | beautifulsoup4
  |  
  | #
  | # This file is autogenerated by pip-compile
  | # To update, run:
  | #
  | #    pip-compile --generate-hashes --output-file=- -
  | #
  | attrdict==2.0.1
  | --hash=sha256:35c90698b55c683946091177177a9e9c0713a0860f0e049febd72649ccd77b70
  | --hash=sha256:9432e3498c74ff7e1b20b3d93b45d766b71cbffa90923496f82c4ae38b92be34
  | # via -r -
  | attrs==19.3.0
  | --hash=sha256:08a96c641c3a74e44eb59afb61a24f2cb9f4d7188748e76ba4bb5edfa3cb7d1c
  | --hash=sha256:f7b7ce16570fe9965acd6d30101a28f62fb4a7f9e926b3bbc9b61f8b04247e72
  | # via pytest
  | beautifulsoup4==4.9.1
  | --hash=sha256:73cc4d115b96f79c7d77c1c7f7a0a8d4c57860d1041df407dd1aae7f07a77fd7
  | --hash=sha256:a6237df3c32ccfaee4fd201c8f5f9d9df619b93121d01353a64a73ce8c6ef9a8
  | --hash=sha256:e718f2342e2e099b640a34ab782407b7b676f47ee272d6739e60b8ea23829f2c
  | # via bs4
  | bs4==0.0.1
  | --hash=sha256:36ecea1fd7cc5c0c6e4a1ff075df26d50da647b75376626cc186e2212886dd3a
  | # via -r -
  | colorama==0.4.3
  | --hash=sha256:7d73d2a99753107a36ac6b455ee49046802e59d9d076ef8e47b61499fa29afff
  | --hash=sha256:e96da0d330793e2cb9485e9ddfd918d456036c7149416295932478192f4436a1
  | # via -r -
  | cycler==0.10.0
  | --hash=sha256:1d8a5ae1ff6c5cf9b93e8811e581232ad8920aeec647c37316ceac982b08cb2d
  | --hash=sha256:cd7b2d1018258d7247a71425e9f26463dfb444d411c39569972f4ce586b0c9d8
  | # via matplotlib
  | fuzzywuzzy==0.18.0
  | --hash=sha256:45016e92264780e58972dca1b3d939ac864b78437422beecebb3095f8efd00e8
  | --hash=sha256:928244b28db720d1e0ee7587acf660ea49d7e4c632569cad4f1cd7e68a5f0993
  | # via -r -
  | humanize==2.4.0
  | --hash=sha256:07dd1293bac6c77daa5ccdc22c0b41b2315bee0e339a9f035ba86a9f1a272002
  | --hash=sha256:42ae7d54b398c01bd100847f6cb0fc9e381c21be8ad3f8e2929135e48dbff026
  | # via -r -
  | importlib-metadata==1.6.1
  | --hash=sha256:0505dd08068cfec00f53a74a0ad927676d7757da81b7436a6eefe4c7cf75c545
  | --hash=sha256:15ec6c0fd909e893e3a08b3a7c76ecb149122fb14b7efe1199ddd4c7c57ea958
  | # via pluggy, pytest
  | kiwisolver==1.2.0
  | --hash=sha256:03662cbd3e6729f341a97dd2690b271e51a67a68322affab12a5b011344b973c
  | --hash=sha256:18d749f3e56c0480dccd1714230da0f328e6e4accf188dd4e6884bdd06bf02dd
  | --hash=sha256:247800260cd38160c362d211dcaf4ed0f7816afb5efe56544748b21d6ad6d17f
  | --hash=sha256:443c2320520eda0a5b930b2725b26f6175ca4453c61f739fef7a5847bd262f74
  | --hash=sha256:4eadb361baf3069f278b055e3bb53fa189cea2fd02cb2c353b7a99ebb4477ef1
  | --hash=sha256:556da0a5f60f6486ec4969abbc1dd83cf9b5c2deadc8288508e55c0f5f87d29c
  | --hash=sha256:603162139684ee56bcd57acc74035fceed7dd8d732f38c0959c8bd157f913fec
  | --hash=sha256:60a78858580761fe611d22127868f3dc9f98871e6fdf0a15cc4203ed9ba6179b
  | --hash=sha256:7cc095a4661bdd8a5742aaf7c10ea9fac142d76ff1770a0f84394038126d8fc7
  | --hash=sha256:c31bc3c8e903d60a1ea31a754c72559398d91b5929fcb329b1c3a3d3f6e72113
  | --hash=sha256:c955791d80e464da3b471ab41eb65cf5a40c15ce9b001fdc5bbc241170de58ec
  | --hash=sha256:d069ef4b20b1e6b19f790d00097a5d5d2c50871b66d10075dab78938dc2ee2cf
  | --hash=sha256:d52b989dc23cdaa92582ceb4af8d5bcc94d74b2c3e64cd6785558ec6a879793e
  | --hash=sha256:e586b28354d7b6584d8973656a7954b1c69c93f708c0c07b77884f91640b7657
  | --hash=sha256:efcf3397ae1e3c3a4a0a0636542bcad5adad3b1dd3e8e629d0b6e201347176c8
  | --hash=sha256:fccefc0d36a38c57b7bd233a9b485e2f1eb71903ca7ad7adacad6c28a56d62d2
  | # via matplotlib
  | lxml==4.5.1
  | --hash=sha256:06748c7192eab0f48e3d35a7adae609a329c6257495d5e53878003660dc0fec6
  | --hash=sha256:0790ddca3f825dd914978c94c2545dbea5f56f008b050e835403714babe62a5f
  | --hash=sha256:1aa7a6197c1cdd65d974f3e4953764eee3d9c7b67e3966616b41fab7f8f516b7
  | --hash=sha256:22c6d34fdb0e65d5f782a4d1a1edb52e0a8365858dafb1c08cb1d16546cf0786
  | --hash=sha256:2754d4406438c83144f9ffd3628bbe2dcc6d62b20dbc5c1ec4bc4385e5d44b42
  | --hash=sha256:27ee0faf8077c7c1a589573b1450743011117f1aa1a91d5ae776bbc5ca6070f2
  | --hash=sha256:2b02c106709466a93ed424454ce4c970791c486d5fcdf52b0d822a7e29789626
  | --hash=sha256:2d1ddce96cf15f1254a68dba6935e6e0f1fe39247de631c115e84dd404a6f031
  | --hash=sha256:4f282737d187ae723b2633856085c31ae5d4d432968b7f3f478a48a54835f5c4
  | --hash=sha256:51bb4edeb36d24ec97eb3e6a6007be128b720114f9a875d6b370317d62ac80b9
  | --hash=sha256:7eee37c1b9815e6505847aa5e68f192e8a1b730c5c7ead39ff317fde9ce29448
  | --hash=sha256:7fd88cb91a470b383aafad554c3fe1ccf6dfb2456ff0e84b95335d582a799804
  | --hash=sha256:9144ce36ca0824b29ebc2e02ca186e54040ebb224292072250467190fb613b96
  | --hash=sha256:925baf6ff1ef2c45169f548cc85204433e061360bfa7d01e1be7ae38bef73194
  | --hash=sha256:a636346c6c0e1092ffc202d97ec1843a75937d8c98aaf6771348ad6422e44bb0
  | --hash=sha256:a87dbee7ad9dce3aaefada2081843caf08a44a8f52e03e0a4cc5819f8398f2f4
  | --hash=sha256:a9e3b8011388e7e373565daa5e92f6c9cb844790dc18e43073212bb3e76f7007
  | --hash=sha256:afb53edf1046599991fb4a7d03e601ab5f5422a5435c47ee6ba91ec3b61416a6
  | --hash=sha256:b26719890c79a1dae7d53acac5f089d66fd8cc68a81f4e4bd355e45470dc25e1
  | --hash=sha256:b7462cdab6fffcda853338e1741ce99706cdf880d921b5a769202ea7b94e8528
  | --hash=sha256:b77975465234ff49fdad871c08aa747aae06f5e5be62866595057c43f8d2f62c
  | --hash=sha256:c47a8a5d00060122ca5908909478abce7bbf62d812e3fc35c6c802df8fb01fe7
  | --hash=sha256:c79e5debbe092e3c93ca4aee44c9a7631bdd407b2871cb541b979fd350bbbc29
  | --hash=sha256:d8d40e0121ca1606aa9e78c28a3a7d88a05c06b3ca61630242cded87d8ce55fa
  | --hash=sha256:ee2be8b8f72a2772e72ab926a3bccebf47bb727bda41ae070dc91d1fb759b726
  | --hash=sha256:f95d28193c3863132b1f55c1056036bf580b5a488d908f7d22a04ace8935a3a9
  | --hash=sha256:fadd2a63a2bfd7fb604508e553d1cf68eca250b2fbdbd81213b5f6f2fbf23529
  | # via -r -
  | matplotlib==3.2.2
  | --hash=sha256:006413f08ba5db1f5b1e0d6fbdc2ac9058b062ccf552f57182563a78579c34b4
  | --hash=sha256:1ab264770e7cf2cf4feb99f22c737066aef21ddf1ec402dc255450ac15eacb7b
  | --hash=sha256:20bcd11efe194cd302bd0653cb025b8d16bcd80442359bfca8d49dc805f35ec8
  | --hash=sha256:2a6d64336b547e25730b6221e7aadfb01a391a065d43b5f51f0b9d7f673d2dd2
  | --hash=sha256:31d32c83bb2b617377c6156f75e88b9ec2ded289e47ad4ff0f263dc1019d88b1
  | --hash=sha256:3d77a6630d093d74cbbfebaa0571d00790966be1ed204e4a8239f5cbd6835c5d
  | --hash=sha256:4416825ebc9c1f135027a30e8d8aea0edcf45078ce767c7f7386737413cfb98f
  | --hash=sha256:465c752278d27895e23f1379d6fcfa3a2990643b803c25e3bc16a10641d2346a
  | --hash=sha256:647cf232ccf6265d2ba1ac4103e8c8b6ac7b03a40da3421234ffb03dda217f59
  | --hash=sha256:67065d938df34478451af62fbd0670d2b51c4d859fb66673064eb5de8660dd7c
  | --hash=sha256:81de040403a33bf3c68e9d4a40e26c8d24da00f7e3fadd845003b7e106785da7
  | --hash=sha256:894dd47c0a6ce38dc19bc87d1f7e2b0608310b2a18d1572291157450b05ce874
  | --hash=sha256:91c153f4318e3c67c035fd1185f5ea2613f15008b73b66985033033f6fe54bbd
  | --hash=sha256:a47abc48c7b81fe6e636dde8a58e49b13d87d140e0f448213a4879f4a3f73345
  | --hash=sha256:a68e42e22f7fd190a532e4215e142276970c2d54040a0c46842fcb3db8b6ec5b
  | --hash=sha256:da06fa530591a141ffbe1712bbeec784734c3436b40c942d21652f305199b5d9
  | # via -r -
  | more-itertools==8.4.0
  | --hash=sha256:68c70cc7167bdf5c7c9d8f6954a7837089c6a36bf565383919bb595efb8a17e5
  | --hash=sha256:b78134b2063dd214000685165d81c154522c3ee0a1c0d4d113c80361c234c5a2
  | # via pytest
  | numpy==1.19.0
  | --hash=sha256:13af0184177469192d80db9bd02619f6fa8b922f9f327e077d6f2a6acb1ce1c0
  | --hash=sha256:26a45798ca2a4e168d00de75d4a524abf5907949231512f372b217ede3429e98
  | --hash=sha256:26f509450db547e4dfa3ec739419b31edad646d21fb8d0ed0734188b35ff6b27
  | --hash=sha256:30a59fb41bb6b8c465ab50d60a1b298d1cd7b85274e71f38af5a75d6c475d2d2
  | --hash=sha256:33c623ef9ca5e19e05991f127c1be5aeb1ab5cdf30cb1c5cf3960752e58b599b
  | --hash=sha256:356f96c9fbec59974a592452ab6a036cd6f180822a60b529a975c9467fcd5f23
  | --hash=sha256:3c40c827d36c6d1c3cf413694d7dc843d50997ebffbc7c87d888a203ed6403a7
  | --hash=sha256:4d054f013a1983551254e2379385e359884e5af105e3efe00418977d02f634a7
  | --hash=sha256:63d971bb211ad3ca37b2adecdd5365f40f3b741a455beecba70fd0dde8b2a4cb
  | --hash=sha256:658624a11f6e1c252b2cd170d94bf28c8f9410acab9f2fd4369e11e1cd4e1aaf
  | --hash=sha256:76766cc80d6128750075378d3bb7812cf146415bd29b588616f72c943c00d598
  | --hash=sha256:7b57f26e5e6ee2f14f960db46bd58ffdca25ca06dd997729b1b179fddd35f5a3
  | --hash=sha256:7b852817800eb02e109ae4a9cef2beda8dd50d98b76b6cfb7b5c0099d27b52d4
  | --hash=sha256:8cde829f14bd38f6da7b2954be0f2837043e8b8d7a9110ec5e318ae6bf706610
  | --hash=sha256:a2e3a39f43f0ce95204beb8fe0831199542ccab1e0c6e486a0b4947256215632
  | --hash=sha256:a86c962e211f37edd61d6e11bb4df7eddc4a519a38a856e20a6498c319efa6b0
  | --hash=sha256:a8705c5073fe3fcc297fb8e0b31aa794e05af6a329e81b7ca4ffecab7f2b95ef
  | --hash=sha256:b6aaeadf1e4866ca0fdf7bb4eed25e521ae21a7947c59f78154b24fc7abbe1dd
  | --hash=sha256:be62aeff8f2f054eff7725f502f6228298891fd648dc2630e03e44bf63e8cee0
  | --hash=sha256:c2edbb783c841e36ca0fa159f0ae97a88ce8137fb3a6cd82eae77349ba4b607b
  | --hash=sha256:cbe326f6d364375a8e5a8ccb7e9cd73f4b2f6dc3b2ed205633a0db8243e2a96a
  | --hash=sha256:d34fbb98ad0d6b563b95de852a284074514331e6b9da0a9fc894fb1cdae7a79e
  | --hash=sha256:d97a86937cf9970453c3b62abb55a6475f173347b4cde7f8dcdb48c8e1b9952d
  | --hash=sha256:dd53d7c4a69e766e4900f29db5872f5824a06827d594427cf1a4aa542818b796
  | --hash=sha256:df1889701e2dfd8ba4dc9b1a010f0a60950077fb5242bb92c8b5c7f1a6f2668a
  | --hash=sha256:fa1fe75b4a9e18b66ae7f0b122543c42debcf800aaafa0212aaff3ad273c2596
  | # via matplotlib
  | packaging==20.4
  | --hash=sha256:4357f74f47b9c12db93624a82154e9b120fa8293699949152b22065d556079f8
  | --hash=sha256:998416ba6962ae7fbd6596850b80e17859a5753ba17c32284f67bfff33784181
  | # via pytest
  | pluggy==0.13.1
  | --hash=sha256:15b2acde666561e1298d71b523007ed7364de07029219b604cf808bfa1c765b0
  | --hash=sha256:966c145cd83c96502c3c3868f50408687b38434af77734af1e9ca461a4081d2d
  | # via pytest
  | prompt-toolkit==3.0.5
  | --hash=sha256:563d1a4140b63ff9dd587bda9557cffb2fe73650205ab6f4383092fb882e7dc8
  | --hash=sha256:df7e9e63aea609b1da3a65641ceaf5bc7d05e0a04de5bd45d05dbeffbabf9e04
  | # via -r -
  | py==1.8.2
  | --hash=sha256:a673fa23d7000440cc885c17dbd34fafcb7d7a6e230b29f6766400de36a33c44
  | --hash=sha256:f3b3a4c36512a4c4f024041ab51866f11761cc169670204b235f6b20523d4e6b
  | # via pytest
  | pycairo==1.19.1
  | --hash=sha256:2c143183280feb67f5beb4e543fd49990c28e7df427301ede04fc550d3562e84
  | # via -r -
  | pygments==2.6.1
  | --hash=sha256:647344a061c249a3b74e230c739f434d7ea4d8b1d5f3721bc0f3558049b38f44
  | --hash=sha256:ff7a40b4860b727ab48fad6360eb351cc1b33cbf9b15a0f689ca5353e9463324
  | # via -r -
  | pyparsing==2.4.7
  | --hash=sha256:c203ec8783bf771a155b207279b9bccb8dea02d8f0c9e5f8ead507bc3246ecc1
  | --hash=sha256:ef9d7589ef3c200abe66653d3f1ab1033c3c419ae9b9bdb1240a85b024efc88b
  | # via matplotlib, packaging
  | pytest==5.4.3
  | --hash=sha256:5c0db86b698e8f170ba4582a492248919255fcd4c79b1ee64ace34301fb589a1
  | --hash=sha256:7979331bfcba207414f5e1263b5a0f8f521d0f457318836a7355531ed1a4c7d8
  | # via -r -
  | python-dateutil==2.8.1
  | --hash=sha256:73ebfe9dbf22e832286dafa60473e4cd239f8592f699aa5adaf10050e6e1823c
  | --hash=sha256:75bb3f31ea686f1197762692a9ee6a7550b59fc6ca3a1f4b5d7e32fb98e2da2a
  | # via -r -, matplotlib
  | python-levenshtein==0.12.0
  | --hash=sha256:033a11de5e3d19ea25c9302d11224e1a1898fe5abd23c61c7c360c25195e3eb1
  | # via -r -
  | regex==2020.6.8
  | --hash=sha256:08997a37b221a3e27d68ffb601e45abfb0093d39ee770e4257bd2f5115e8cb0a
  | --hash=sha256:112e34adf95e45158c597feea65d06a8124898bdeac975c9087fe71b572bd938
  | --hash=sha256:1700419d8a18c26ff396b3b06ace315b5f2a6e780dad387e4c48717a12a22c29
  | --hash=sha256:2f6f211633ee8d3f7706953e9d3edc7ce63a1d6aad0be5dcee1ece127eea13ae
  | --hash=sha256:52e1b4bef02f4040b2fd547357a170fc1146e60ab310cdbdd098db86e929b387
  | --hash=sha256:55b4c25cbb3b29f8d5e63aeed27b49fa0f8476b0d4e1b3171d85db891938cc3a
  | --hash=sha256:5aaa5928b039ae440d775acea11d01e42ff26e1561c0ffcd3d805750973c6baf
  | --hash=sha256:654cb773b2792e50151f0e22be0f2b6e1c3a04c5328ff1d9d59c0398d37ef610
  | --hash=sha256:690f858d9a94d903cf5cada62ce069b5d93b313d7d05456dbcd99420856562d9
  | --hash=sha256:6ad8663c17db4c5ef438141f99e291c4d4edfeaacc0ce28b5bba2b0bf273d9b5
  | --hash=sha256:89cda1a5d3e33ec9e231ece7307afc101b5217523d55ef4dc7fb2abd6de71ba3
  | --hash=sha256:92d8a043a4241a710c1cf7593f5577fbb832cf6c3a00ff3fc1ff2052aff5dd89
  | --hash=sha256:95fa7726d073c87141f7bbfb04c284901f8328e2d430eeb71b8ffdd5742a5ded
  | --hash=sha256:97712e0d0af05febd8ab63d2ef0ab2d0cd9deddf4476f7aa153f76feef4b2754
  | --hash=sha256:b2ba0f78b3ef375114856cbdaa30559914d081c416b431f2437f83ce4f8b7f2f
  | --hash=sha256:bae83f2a56ab30d5353b47f9b2a33e4aac4de9401fb582b55c42b132a8ac3868
  | --hash=sha256:c78e66a922de1c95a208e4ec02e2e5cf0bb83a36ceececc10a72841e53fbf2bd
  | --hash=sha256:cf59bbf282b627130f5ba68b7fa3abdb96372b24b66bdf72a4920e8153fc7910
  | --hash=sha256:e3cdc9423808f7e1bb9c2e0bdb1c9dc37b0607b30d646ff6faf0d4e41ee8fee3
  | --hash=sha256:e9b64e609d37438f7d6e68c2546d2cb8062f3adb27e6336bc129b51be20773ac
  | --hash=sha256:fbff901c54c22425a5b809b914a3bfaf4b9570eee0e5ce8186ac71eb2025191c
  | # via -r -
  | six==1.15.0
  | --hash=sha256:30639c035cdb23534cd4aa2dd52c3bf48f06e5f4a941509c8bafd8ce11080259
  | --hash=sha256:8b74bedcbbbaca38ff6d7491d76f2b06b3592611af620f8426e82dddb04a5ced
  | # via attrdict, cycler, packaging, python-dateutil
  | soupsieve==2.0.1
  | --hash=sha256:1634eea42ab371d3d346309b93df7870a88610f0725d47528be902a0d95ecc55
  | --hash=sha256:a59dc181727e95d25f781f0eb4fd1825ff45590ec8ff49eadfd7f1a537cc0232
  | # via beautifulsoup4
  | wcwidth==0.2.4
  | --hash=sha256:79375666b9954d4a1a10739315816324c3e73110af9d0e102d906fdb0aec009f
  | --hash=sha256:8c6b5b6ee1360b842645f336d9e5d68c55817c26d3050f46b235ef2bc650e48f
  | # via prompt-toolkit, pytest
  | zipp==3.1.0
  | --hash=sha256:aa36550ff0c0b7ef7fa639055d797116ee891440eac1a56f378e2d3179e0320b
  | --hash=sha256:c599e4d75c98f6798c509911d08a22e6c021d074469042177c8c86fb92eefd96
  | # via importlib-metadata
  |  
  | # WARNING: The following packages were not pinned, but pip requires them to be
  | # pinned when the requirements file includes hashes. Consider using the --allow-unsafe flag.
  | # setuptools
  | The generated requirements file may be rejected by pip install. See # WARNING lines for details.

What tech do you use for connecting python and C ?

Thank you
@miohtama @joncasdam @EdwardBetts @wor

Python 3 compatibility

Is this module compatible with Python 3? I't doesn't compile for me in a Python 3 virtualenv.

incorrect jaro halflen

According to http://www.census.gov/srd/papers/pdf/rr91-9.pdf and http://en.wikipedia.org/wiki/Jaro–Winkler_distance, the halflen should be the length of the longer string / 2 - 1. So, this line in Levenshtein.c:

halflen = (len1 + 1)/2;

should be:

halflen = (len2 / 2) - 1;

With test case "chukumwong" and "ckwong", python-Levenshtein currently returns 0.5111111111111111 (halflen=3, matches=2) while lingpipe returns 0.8666666666666667 (halflen=4, matches=6).

question about calloc size

what is the purpose of the memory allocation with the next syntax?

mblocks = (LevMatchingBlock*)malloc(nmb*sizeof(LevOpCode));

I think that the sizeof must be LevMatchingBlock and not LevOpCode

Why GLP License, Why Not MIT or BSD

Can't distribute!

where does this algo come from

why is it correct?
is there any reference?