汉明距离与莱文施泰因距离
nlp
5
0

对于我正在研究的问题,找到两个序列之间的距离以确定它们的相似性,序列顺序非常重要。但是,我拥有的序列的长度并不完全相同,因此我用空点填充任何不足的字符串,以使两个序列的长度相同,以满足汉明距离的要求。我这样做有什么大问题,因为我只关心转座的数量(不是像Levenshtein那样的插入或删除)?

我发现汉明距离比Levenshtein快得多,它是较长序列的距离度量。什么时候应该使用Levenshtein距离(或Levenshtein距离的导数)而不是便宜得多的汉明距离?汉明距离可以视为两个序列之间可能存在的Levenshtein距离的上限,因此,如果我比较两个序列的顺序有序的相似性度量,而不是匹配序列的绝对最小移动数,则没有明显的区别为什么我选择Levenshtein而不是Hamming作为度量标准,是吗?

参考资料:
Stack Overflow
收藏
评论
共 2 个回答
高赞 时间 活跃

除了正确的Johan答案外,填充也可能有问题。

例如,当您比较123123456 ,是在字符串的末尾还是在字符串的开头填充。 ___123123456的相似度为0,但123___123456的相似度为3。

收藏
评论

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

如果认为“ 1234567890”和“ 0123456789”完全不同不是问题,那么汉明距离确实可以。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号