A pure, minimalist Python library of various edit distances
Project description
python-editdistance
A pure, minimalist, single-file Python library of various edit distance metrics.
Implemented methods:
- Levenshtein (iterative and recursive implementations)
- Normalized Levenshtein (using Yujian-Bo [1])
- Damerau-Levenshtein
- Hamming distance
Levenshtein and Damerau-Levenshtein distances use the Wagner-Fischer dynamic programming algorithm [2].
Some basic unit tests can be executed using pytest
Installation
pip install pyeditdistance
Optional (user-specific):
pip install --user pyeditdistance
Usage
from pyeditdistance import distance as d
s1 = "I am Joe Bloggs"
s2 = "I am John Gault"
# Levenshtein distance
res = d.levenshtein(s1, s2) # => 8
# Levenshtein distance (recursive)
res = d.levenshtein_recursive(s1, s2) # => 8
# Normalized Levenshtein
res = d.normalized_levenshtein(s1, s2) # => 0.4210 (approx)
# Damerau-Levenshtein
s3 = "abc"
s4 = "cb"
res = d.damerau_levenshtein(s3, s4) # => 2
# Hamming distance
s5 = "abcccdeeffghh zz"
s6 = "bacccdeeffhghz z"
res = d.hamming(s5, s6) # => 6
References
- L. Yujian and L. Bo, "A normalized Levenshtein distance metric," IEEE Transactions on Pattern Analysis and Machine Intelligence (2007). https://ieeexplore.ieee.org/document/4160958
- R. Wagner and M. Fisher, "The string to string correction problem," Journal of the ACM, 21:168-178, 1974.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
pyeditdistance-0.0.1.tar.gz
(5.3 kB
view hashes)
Built Distribution
Close
Hashes for pyeditdistance-0.0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3ec34d6635b52d3bc020bd270df75b9c1fe9bcdd19cc16dd66be94304be4555d |
|
MD5 | 5145f5ce87a114d0c8014db9178ed860 |
|
BLAKE2b-256 | 3c25aeed2d3ebacf086371f6b5d1e58ce5ea8e7e7279a31b28ea98b515a5e4ba |