A pure, minimalist, no-dependency Python library of various edit distances.
Project description
pyeditdistance
A pure, minimalist, no-dependency Python library of various edit distance metrics.
Implemented methods:
- Levenshtein (iterative and recursive implementations)
- Normalized Levenshtein (using Yujian-Bo [1])
- Damerau-Levenshtein
- Hamming distance
- Longest common subsequence (LCS)
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
# Longest common subsequence (LCS)
s7 = "AAGGQQERqer"
s8 = "AaQERqer"
res = d.longest_common_subsequence(s7, s8) # => 7
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.1.tar.gz
(5.7 kB
view hashes)
Built Distribution
Close
Hashes for pyeditdistance-0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbfec1ed2ab8bf0af7f767909d3c10ffe7370699e16caa2b72a3aa3c88dcb26e |
|
MD5 | 63dc84198439498d789ea79eb8596de6 |
|
BLAKE2b-256 | 37048ce1fe843137d2d81a534ecb5287c7ce97cf16670dbcae41ade4590ac6a5 |