algorithm - 关于 Smith-Waterman 算法的问题

Question

我正在使用 Smith-Waterman 算法运行一些字符串匹配测试。我目前正在使用 SimMetrics(Java 开源项目)来运行测试。

谁能解释为什么我比较“Bloggs J”。到“Bloggs”我得到 1.0 的相似度值？

明显有差距(例如'o'和'.')，但似乎没有受到惩罚。

提前谢谢你。

Answer 1

Smith-Waterman Algorithm是一种局部对齐算法。这意味着它旨在对齐对齐良好的片段字符串，而不是对齐整个字符串。您所说的“差距”不应被视为差距，因为它被认为发生在对齐区域之外。长度为“Bloggs”的字符串可能无法更好地与“Bloggs J”对齐。比“博客”做的。如果你想要全局对齐，你应该使用 Needleman-Wunsch Algorithm相反。