锤距离与Levenshtein距离

Question

对于我正在处理的问题，找到两个序列之间的距离以确定它们的相似性，序列顺序非常重要。但是，我所拥有的序列并非全部相同，因此我将任何缺陷的字符串放在具有空点的任何缺陷字符串中，因此两个序列都是相同的长度，以满足锤距要求。我这样做是否有任何重大问题，因为我所关心的是换位的数量（不是像Levenshtein这样的插入或删除）？

我发现，锤距比Levenshtein作为长度序列的距离度量要快得多。什么时候应该使用Levenshtein距离（或Levenshtein距离的衍生物）而不是便宜得多的锤距？可以将锤子距离视为两个序列之间可能的Levenshtein距离的上限，因此，如果我要比较两个序列的订单偏置相似性度量，而不是绝对最小的移动数以匹配序列，则没有明显我选择Levenshtein而不是锤式作为度量标准的原因，有吗？

Answer 1

这个问题实际上取决于您要匹配的序列类型以及您想要的结果。

如果“ 1234567890”和“ 0123456789”被认为是完全不同的，那不是问题。

Answer 2

除了合适的约翰答案外，填充还可能是有问题的。

例如，当您比较 123 至 123456 如果您在字符串的末端或字符串开始时进行垫子，则情况有所不同。相似性 ___123 和 123456 是0，但相似之处 123___ 和 123456 是3。