Computing edit distance on arbitrary Python sequences.
Python module for computing edit distances and alignments between sequences.
I needed a way to compute edit distances between sequences in Python. I wasn't able to find any appropriate libraries that do this so I wrote my own. There appear to be numerous edit distance libraries available for computing edit distances between two strings, but not between two sequences.
This is written entirely in Python. This implementation could likely be optimized to be faster within Python. And could probably be much faster if implemented in C.
The library API is modeled after difflib.SequenceMatcher. This is very similar to difflib, except that this module computes edit distance (Levenshtein distance) rather than the Ratcliff and Oberhelp method that Python's difflib uses. difflib "does not yield minimal edit sequences, but does tend to yield matches that 'look right' to people."
If you find this library useful or have any suggestions, please send me a message.
Installing & uninstalling
The easiest way to install is using pip:
pip install edit_distance
Alternatively you can clone this git repo and install using distutils:
git clone email@example.com:belambert/edit_distance.git cd edit_distance python setup.py install
To uninstall with pip:
pip uninstall edit_distance
This requires Python 2.7+ since it uses argparse for the command line interface. The rest of the code should be OK with earlier versions of Python
Example API usage:
import edit_distance ref = [1, 2, 3, 4] hyp = [1, 2, 4, 5, 6] sm = edit_distance.SequenceMatcher(a=ref, b=hyp) sm.get_opcodes() sm.ratio() sm.get_matching_blocks()
Differences from difflib
In addition to the
are provided which compute the edit distance and the number of matches.
Even if the alignment of the two sequences is identical to
get_matching_blocks() may return slightly different
sequences. The opcodes returned by this library represent individual character
operations, and thus should never span two or more characters.
It's also possible to compute the maximum number of matches rather than the minimum number of edits:
sm = edit_distance.SequenceMatcher(a=ref, b=hyp, action_function=edit_distance.highest_match_action)
This doesn't implement the 'junk' matching features in difflib.
Contributing and code of conduct
For contributions, it's best to Github issues and pull requests. Proper testing and documentation suggested.
Code of conduct is expected to be reasonable, especially as specified by the Contributor Covenant
Release history Release notifications | RSS feed
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, size||File type||Python version||Upload date||Hashes|
|Filename, size edit_distance-1.0.4-py3-none-any.whl (11.2 kB)||File type Wheel||Python version py3||Upload date||Hashes View|
|Filename, size edit_distance-1.0.4.tar.gz (17.5 kB)||File type Source||Python version None||Upload date||Hashes View|
Hashes for edit_distance-1.0.4-py3-none-any.whl