Mismatch between different implementations of Levenshtein

[angelosalatino]

Hi there,

thank you for this work. I love this library because it is 100x faster than its competitors (e.g., strsimpy).

However, I have noticed that for the same couple of words, your implementation returns a different value of similarity.

from strsimpy.normalized_levenshtein import NormalizedLevenshtein
import Levenshtein


a = 'database system'
b = 'database systems'

print("Ration from Strsimpy")
normalized_levenshtein = NormalizedLevenshtein()
print(normalized_levenshtein.similarity(a, b))   

print("Ration from Levenshtein")
print(Levenshtein.seqratio(a,b)) 

as a result I get:

Ration from Strsimpy
0.9375
Ration from Levenshtein
0.967741935483871

I have checked with online tools and seems like that the similarity between a and b is 0.9375 (check here https://awsm-tools.com/levenshtein-distance?form%5Bsource%5D=database+system&form%5Btarget%5D=database+systems) which is in line with Strsimpy.

Do you know we get different values of similarity?

Thank a lot
Angelo

[maxbachmann]

Levenshtein.ratio is based upon the Indel distance and not on the Levenshtein distance. This is basically the same as the Levenshtein distance without substitutions. You can get the normalized Levenshtein distance using rapidfuzz:

>>> from rapidfuzz.distance import Levenshtein, Indel
>>> Levenshtein.normalized_similarity(a, b)
0.9375
>>> Levenshtein.normalized_similarity(a, b, weights=(1,1,2))
0.967741935483871
>>> Indel.normalized_similarity(a, b)
0.967741935483871

when processing large amounts of data I recommend using one of the processing functions in rapidfuzz.process. They are a lot faster, since they do not need to switch between Python and C++ for each string comparision.

[angelosalatino]

Thanks for the clarification and the lead. I will test this one. Thanks again

[R-N]

Why don't Levenshtein library use Levenshtein for ratio?

[maxbachmann]

Why don't Levenshtein library use Levenshtein for ratio?

The original author implemented it like this for some unknown reason and I kept it like this for backwards compatibility. I agree it is pretty confusing, so at least I made sure to mention the indel distance in the documentation.

[R-N]

Why don't Levenshtein library use Levenshtein for ratio?

The original author implemented it like this for some unknown reason and I kept it like this for backwards compatibility. I agree it is pretty confusing, so at least I made sure to mention the indel distance in the documentation.

I think it should be mentioned in the readme too, where people would read first. I mean, I would expect Levenshtein library to use Levenshtein unless specified otherwise. It's not like "Indel" is in the function name.