如何为Damerau-Levenshtein距离选择合适的最大值？

Question

我在相似性度量中使用了here提供的Damerau-Levenshtein代码。问题是，当我将Damerau-Levenshtein应用于两个字符串(如cat sat on a mat和dog sat mat )时，我得到的编辑距离为8。这种相似性结果可以得到关于插入、删除或替换的任何数字，如0，1，2，...。现在我想知道是否有任何方法可以假设或找到此距离(相似度)的最大值，并在0和1之间转换，或者我们如何设置最大值，至少我可以说：distance =1 - similarity。

写这篇文章的原因是，我正在为一些距离度量设置阈值，比如余弦，Levenstein和damerau levenstein，所有的输出都应该在0和1之间。

Answer 1

困难的是Damerau-Levenshtein的上限是无限的(给定无限长的单词)，但我们实际上不能制造无限的字符串。

如果你想安全起见，你可以使用一些东西将字符串的范围0->最大长度映射到范围0->1。字符串的最大长度取决于你拥有的内存量(假设64位)，所以我建议使用doing...not。Source

实际上，您也可以只检查要比较的所有字符串，并选择该列表中最长字符串的长度作为最大值。另一种解决方案是预先计算所有分数，并在知道最大分数后应用转换因子。一些可以做到这一点的代码：

def adjustScore(lists, maxNum):
    scaleFactor = 1/maxNum
    return [x * scaleFactor for x in lists]

testWords = ["test1", "testing2", "you", "must", "construct", "additional", "plyometrics"]
testScores = []
for i in range(len(testWords)-1):
    testScores.append(damerau_levenshtein_distance(testWords[i], testWords[i+1]))

#method 1: just check the biggest score you got to obtain the max
max1 = max(testScores)
result = adjustScore(testScores, max1)

#method 2: if you need the adjusted score first, pick the longest string's length as max
lens = map(len, testWords)
max2 = max(lens)
result2 = adjustScore(testScores, max2)

这些方法恰好给出了相同的答案，因为大多数单词彼此之间非常不同，但这两种方法中的任何一种都应该适用于大多数情况。

长话短说，两个字符串之间的最大距离是较长字符串的长度。

注意:如果映射方向错误(即高分显示低分，反之亦然)，只需在左方括号和调整分数中的x之间添加"1-“即可。

此外，如果您希望它映射不同的do范围，请用不同的最大值替换1。

Answer 2

Levenshtein Distance score = number of insertion + number of deletion + number of substitution.

因此，最大值是数据集中最大长度字符串的3X(乘以)。