通过置换来衡量字符串相似度

Question

通过置换来衡量字符串相似度

stringalgorithmsimilaritylevenshtein-distance

3

如果我有三个字符串，第一个是 string1 = Laptop，第二个是 string2 = Latpop，第三个是 string3 = Lavmop，那么编辑距离算法将为 string1 和 string2 的相似度以及 string1 和 string3 的相似度返回相同的距离。这是因为编辑距离算法仅计算插入、删除和替换操作，不包括置换操作。例如，我们可以在字符串 Latpop 中交换第三个和第四个字符，得到 Laptop。

显然，Latpop 与 Laptop 更为相似，而与 Lavmop 相比并不能处于相同的相似度级别。

是否有一种算法可以考虑置换操作？

- hbak

你是否在寻找类似于 https://en.wikipedia.org/wiki/Locality-sensitive_hashing 的东西？ - pandaadb

我认为你正在寻找的是Damerau-Levenshtein距离。除了Levenshtein距离中的操作外，它还考虑了交换相邻字符的额外操作。 https://zh.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein%E8%B7%9D%E7%A6%BB - Siddhanjay Godre

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hbak · Answer 1

我在 Damerau-Levenshtein 距离和 Jaro-Winkler 距离中找到了答案。