LCS和字符串相似度之间的关系是什么？

Question

我想知道如何相似，其中两个字符串，我发现在以下页面的工具： https://www.tools4noobs.com/online_tools/string_similarity/

，它说，这个工具是基于文章：

“的O（ND）的差异算法及其变奏”

可在： http://www.xmailserver.org/diff2.pdf

我读过这篇文章，但我对他们如何编程的工具有些怀疑，例如作者说，这是巴sed在C库GNU diff和analyze.c;也许它指的是这样的：

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

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

我已经是如何理解的文章，为我读文章的关系问题给出了找到一个算法一对字符串之间的LCS（最长的公共子序列），所以他们使用修改的动态规划算法来解决这个问题。修改是使用最短路径算法来查找具有最少修改次数的LCS。

在这一点上，我迷路了，因为我不知道我第一次提到的工具的作者如何使用LCS来找出两个序列的相似程度。还有一个极限值为0.4，这是什么意思？有人可以帮助我吗？还是我误解了那篇文章？

感谢

Answer 1

我觉得串相似度工具的描述并非是完全诚实的，因为我敢肯定它已经使用Perl模块，String::Similarity实现。相似性评分标准化为介于0和1之间的值，并且如模块页面所述，如果相似性低于此值，则可以使用限制值提前中止比较。

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

的LCS和字符串相似性之间的连接很简单，就是那些在LCS不字符正是你需要添加，以第一个字符串转换为第二删除或替换的字符，这些不同字符的数量通常用作差异分数，如Levenshtein Distance中所示。