DamerauLevenshtein() vs Levenshtein() why the same distance?

General Usage
1

I expected a shorter distance for Damerau Levenshtein because there is an exchange of two letters. Why are there the same results?

julia> compare("martha", "martht", DamerauLevenshtein())
0.8333333333333334

julia> compare("martha", "martht", Levenshtein())
0.8333333333333334

Paul

2

This does not really look like a Julia question.
I guess you should at least specify what package are you calling these functions from and why you would expect a different result.

I suppose you refer to StringDistances.jl(but I might be wrong).
By the way, I believe the result is correct: the strings “martha” and “martht” are only separated by a transformation of ‘a’ into ‘t’, hence you have 1-1/6=0.8[3] in both cases.
Instead, where you see the difference between the two metrics is by comparing e.g. “martha” and “martah”: with the Damerau-Levenshtein metric you can swap adjacent letters and hence the two strings are separated by a single edit; with the Levenshtein metric you have to apply 2 separate edits ‘a’->‘h’ and ‘h’->‘a’ and hence you get a bigger distance.

julia> compare("martha", "martah", DamerauLevenshtein())
 0.8333333333333334

julia> compare("martha", "martah", Levenshtein())
 0.6666666666666667

Now Levenshtein returns a smaller value because, as stated in the docs, The function compare is defined as 1 minus the normalized distance between two strings, hence it returns “closeness” between the two strings rather than distance.

4

I think mastrof’s explanation covers the original question pretty well.

I’m looking into edit distance algorithms for a thesis, and there’s another small detail I found interesting while comparing different implementations.

Some libraries use Optimal String Alignment (OSA) under the Damerau-Levenshtein name, which isn’t quite the same as the unrestricted version. They give the same result for simple swaps like “martha” and “martah”, but can differ in more complicated cases.

For example, with “ca” and “abc”, unrestricted Damerau-Levenshtein gives 2, while OSA gives 3.

Maybe not directly related to the original example, but I thought it was worth mentioning for anyone comparing implementations.