A pure, minimalist, no-dependency Python library of various edit distances.
Project description
pyeditdistance
A pure, minimalist Python library of various edit distance metrics. MIT-licensed, zero dependencies.
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-1.0.tar.gz
(5.8 kB
view hashes)
Built Distribution
Close
Hashes for pyeditdistance-1.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d0c63e6945ccd796a8c2d7368b6ea650816faf564dbf5f4503f638788c8b35b |
|
MD5 | f275e99bf453cc8a32eccb8dd509b53f |
|
BLAKE2b-256 | 81476f9728706cd55d9a6583d305aa8203863ffba7f829a5b6bc1789b62f6b07 |