algorithm - LCS和字符串相似度有什么关系？

Question

我想知道两个字符串的相似程度，我在下一页找到了一个工具: https://www.tools4noobs.com/online_tools/string_similarity/

它说这个工具是基于这篇文章:

《一种O(ND)差分算法及其变体》

可用于: http://www.xmailserver.org/diff2.pdf

我看过这篇文章，但我对他们如何编写该工具有一些疑问，例如作者说它基于 C 库 GNU diff 和 analyze.c；可能是指这个:

https://www.gnu.org/software/diffutils/

还有这个: https://github.com/masukomi/dwdiff-annotated/blob/master/src/diff/analyze.c

我遇到的问题是如何理解与文章的关系，因为我读到的文章显示了一种用于查找一对字符串之间的 LCS(最长公共(public)子序列)的算法，因此他们使用了动态的修改用于解决此问题的编程算法。修改是使用最短路径算法找到修改次数最少的LCS。

此时我迷路了，因为我不知道我首先提到的工具的作者是如何使用 LCS 来查找两个序列的相似程度的。还有一个限制值0.4，那是什么意思？有人可以帮我吗？还是我误解了那篇文章？

谢谢

Answer 1

我认为关于字符串相似性工具的描述并不完全诚实，因为我很确定它是使用 Perl 模块实现的 String::Similarity .相似度分数被归一化为 0 到 1 之间的值，并且如模块页面所述，如果相似度低于该限制值，则可以使用限制值提前中止比较。

如果您下载 Perl 模块并展开它，您可以阅读算法的 C 源代码，在名为 fstrcmp.c 的文件中，它说它是“源自 GNU diff 2.7，analyze.c 等”。 .

LCS 和字符串相似性之间的联系很简单，LCS 中不的那些字符正是您需要添加、删除或替换的字符，以便将第一个字符串转换为第二，这些不同字符的数量通常用作差异分数，如 Levenshtein Distance .