Edit distances should return their alignments

chrislit / abydos

Abydos NLP/IR library for Python

GNU General Public License v3.0

180 stars 34 forks source link

Edit distances should return their alignments #171

Open chrislit opened 5 years ago

chrislit commented 5 years ago

Candidates:

[x] Levenshtein/OSA
[ ] Damerau-Levenshtein
[x] Yujian-Bo
[ ] Higuera-Mico
[x] Indel
[ ] SAPS
[ ] Meta-Levenshtein
[ ] FlexMetric
[ ] BI-SIM
[ ] BlockLevenstein
[ ] Rees-Levenshtein
[x] Phonetic Edit Distance
[x] Discounted Levenshtein
[ ] ShapiraStorerI

chrislit commented 5 years ago

Damerau-Levenshtein should be high priority. Without it, Soft Jaccard can't be implemented with its default parameters, which include using DL as the alignment algorithm/distance measure

chrislit commented 5 years ago

Alignments really need to be done by creating a secondary matrix to track the tracebacks, as in PhoneticEditDistance & DiscountedLevenshtein. The greedy method won't always get the correct alignment.