edit_distance
=============
[](https://badge.fury.io/py/Edit_Distance)
[](https://codecov.io/gh/belambert/edit-distance)
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 git@github.com:belambert/edit_distance.git
cd edit_distance
python setup.py install
To uninstall with pip:
pip uninstall edit_distance
API usage
---------
To see examples of usage, view the [difflib documentation](http://docs.python.org/2/library/difflib.html).
Additional API-level documentation is available on [ReadTheDocs](http://edit-distance.readthedocs.io/en/latest/)
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:
```python
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 `SequenceMatcher` methods, `distance()` and `matches()` methods
are provided which compute the edit distance and the number of matches.
```python
sm.distance()
sm.matches()
```
Even if the alignment of the two sequences is identical to `difflib`,
`get_opcodes()` and `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:
```python
sm = edit_distance.SequenceMatcher(a=ref, b=hyp,
action_function=edit_distance.highest_match_action)
```
Notes
-----
This doesn't implement the 'junk' matching features in difflib.
Hacking
-------
To run unit tests:
python -m unittest
To deploy...
Contributing and code of conduct
--------------------------------
For contributions, it's best to Github issues and pull requests. Proper
testing and documentation required.
Code of conduct is expected to be reasonable, especially as specified by
the [Contributor Covenant](http://contributor-covenant.org/version/1/4/)
Raw data
{
"_id": null,
"home_page": "https://github.com/belambert/editdistance",
"name": "edit-distance",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "edit,distance,editdistance,levenshtein",
"author": "Ben Lambert",
"author_email": "blambert@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/16/b2/27b30ff8c251012789f0976de74a5b497a03ab259c7ae2b08502b81618bb/edit_distance-1.0.6.tar.gz",
"platform": null,
"description": "edit_distance\n=============\n\n[](https://badge.fury.io/py/Edit_Distance)\n[](https://codecov.io/gh/belambert/edit-distance)\n\nPython module for computing edit distances and alignments between sequences.\n\nI needed a way to compute edit distances between sequences in Python. I wasn't\nable to find any appropriate libraries that do this so I wrote my own. There\nappear to be numerous edit distance libraries available for computing edit\ndistances between two strings, but not between two sequences.\n\nThis is written entirely in Python. This implementation could likely be\noptimized to be faster within Python. And could probably be much faster if\nimplemented in C.\n\nThe library API is modeled after difflib.SequenceMatcher. This is very similar\nto difflib, except that this module computes edit distance (Levenshtein \ndistance) rather than the Ratcliff and Oberhelp method that Python's difflib\nuses. difflib \"does not yield minimal edit sequences, but does tend to yield\nmatches that 'look right' to people.\"\n\nIf you find this library useful or have any suggestions, please send me a\nmessage.\n\nInstalling & uninstalling\n-------------------------\nThe easiest way to install is using pip:\n\n pip install edit_distance\n\nAlternatively you can clone this git repo and install using distutils:\n\n git clone git@github.com:belambert/edit_distance.git\n cd edit_distance\n python setup.py install\n\nTo uninstall with pip:\n\n pip uninstall edit_distance\n\n\nAPI usage\n---------\nTo see examples of usage, view the [difflib documentation](http://docs.python.org/2/library/difflib.html).\nAdditional API-level documentation is available on [ReadTheDocs](http://edit-distance.readthedocs.io/en/latest/)\n\nThis requires Python 2.7+ since it uses argparse for the command line \ninterface. The rest of the code should be OK with earlier versions of Python\n\nExample API usage:\n\n```python\nimport edit_distance\nref = [1, 2, 3, 4]\nhyp = [1, 2, 4, 5, 6]\nsm = edit_distance.SequenceMatcher(a=ref, b=hyp)\nsm.get_opcodes()\nsm.ratio()\nsm.get_matching_blocks()\n```\n\nDifferences from difflib\n------------------------\nIn addition to the `SequenceMatcher` methods, `distance()` and `matches()` methods \nare provided which compute the edit distance and the number of matches.\n\n```python\nsm.distance()\nsm.matches()\n```\n\nEven if the alignment of the two sequences is identical to `difflib`, \n`get_opcodes()` and `get_matching_blocks()` may return slightly different \nsequences. The opcodes returned by this library represent individual character \noperations, and thus should never span two or more characters.\n\nIt's also possible to compute the maximum number of matches rather than the \nminimum number of edits:\n\n```python\nsm = edit_distance.SequenceMatcher(a=ref, b=hyp, \n action_function=edit_distance.highest_match_action)\n```\n\nNotes\n-----\nThis doesn't implement the 'junk' matching features in difflib.\n\n\nHacking\n-------\nTo run unit tests:\n\n python -m unittest\n\nTo deploy...\n\n\nContributing and code of conduct\n--------------------------------\nFor contributions, it's best to Github issues and pull requests. Proper\ntesting and documentation required.\n\nCode of conduct is expected to be reasonable, especially as specified by\nthe [Contributor Covenant](http://contributor-covenant.org/version/1/4/)\n",
"bugtrack_url": null,
"license": "LICENSE.txt",
"summary": "Computing edit distance on arbitrary Python sequences.",
"version": "1.0.6",
"project_urls": {
"Homepage": "https://github.com/belambert/editdistance"
},
"split_keywords": [
"edit",
"distance",
"editdistance",
"levenshtein"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "211d559e453bc451ab12c7cb79b953f108ed92b378fb8ea4296db1d7c62bbb5e",
"md5": "c273d858d4d04fb880e8814543ff5b9e",
"sha256": "019df0dcd07881d7ead52a3a6bb4cdd5b4d2fbe9d84ad5889f3b8afee524a2d8"
},
"downloads": -1,
"filename": "edit_distance-1.0.6-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c273d858d4d04fb880e8814543ff5b9e",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 11041,
"upload_time": "2023-02-20T18:13:45",
"upload_time_iso_8601": "2023-02-20T18:13:45.244287Z",
"url": "https://files.pythonhosted.org/packages/21/1d/559e453bc451ab12c7cb79b953f108ed92b378fb8ea4296db1d7c62bbb5e/edit_distance-1.0.6-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "16b227b30ff8c251012789f0976de74a5b497a03ab259c7ae2b08502b81618bb",
"md5": "07f6486b2b300a3b18ec42db85e9b8ee",
"sha256": "bf0c1a2edd113d4159b31a55b3810c258dbbcb508fcf2fbc1da6cd51f936de2d"
},
"downloads": -1,
"filename": "edit_distance-1.0.6.tar.gz",
"has_sig": false,
"md5_digest": "07f6486b2b300a3b18ec42db85e9b8ee",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 21905,
"upload_time": "2023-02-20T18:13:46",
"upload_time_iso_8601": "2023-02-20T18:13:46.759762Z",
"url": "https://files.pythonhosted.org/packages/16/b2/27b30ff8c251012789f0976de74a5b497a03ab259c7ae2b08502b81618bb/edit_distance-1.0.6.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-02-20 18:13:46",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "belambert",
"github_project": "editdistance",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "edit-distance"
}
JSON
