Levenshtein Distance is a true Metric, not a SemiMetric about stringdistances.jl HOT 8 CLOSED

Inheritance from StringDistances is useful for me. I’m not going to remove it because you need Levenshtein to be a true metric. Maybe ask the NearestNeighbour package to allow premetric — they can always print a warning in this case.

from stringdistances.jl.

I've removed the inheritance from StringDistance (it is just now just a union of distances). Levenshtein is now a Metric. Let's see how it goes — I'll tag a new version in a few weeks if no one complains.

from stringdistances.jl.

The more minimal version of this is to just change Levenshtein

from stringdistances.jl.

That's interesting. I'm not sure what to do. The issue is that Levenshtein cannot both inherit from StringDistances and Metric.
To be clear, Levenshtein is still a semi-metric, so the current behavior is not wrong per se, it's just not precise enough.

from stringdistances.jl.

Removing the abtract type StringDistance would not solve everything.

This package introduces distance modifiers Partial, Winkler etc which are StringDistances parametrized by other StringDistances (see an example here). It is possible (I have not checked) that Partial{Levenshtein} is a true metric whereas Partial{Jaro} is only a semimetric. But there is no way to express these properties through inheritance in Julia: the type Partial must either inherit from SemiMetric or fromMetric.

This suggests that properties of the metric should a trait rather than an abstract type. I'm curious what other people think (e.g. @KristofferC)

from stringdistances.jl.

The Distances.jl has some very strange stuff like https://github.com/JuliaStats/Distances.jl/blob/7f3a28c0d1372e3b3edbcbc28f00ba5645e1bbdb/src/metrics.jl#L107-L108 which makes it hard to understand how types are structured...

Regarding using a trait, it might make sense. The comment about "Partial{Levenshtein} is a true metric whereas Partial{Jaro} is only a semimetric" suggests it would be a good idea since subtyping cannot model that.

from stringdistances.jl.

Removing StringDistance would at least partially solve the issue.
Sinced even if we are left with Partial{Levenshtein} <: SemiMetric (which as you say is certainly not wrong),
its still means we can get Levenshtein<:Metric presice.

My gut is telling me that most of those parameterized distence modifies are not true Metrics
So this wold be a start until
A) a trait based system can be worked out
B) someone sits down and writes the actual proofs on which modifiers on which base metrics are result in which traits.

from stringdistances.jl.

thanks, think that is a good solution, and if it becomes unworkable then traits become next inline

from stringdistances.jl.