gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:41:28 32 4
gpt4 key购买 nike

我想知道两个字符串的相似程度,我在下一页找到了一个工具: 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,那是什么意思?有人可以帮我吗?还是我误解了那篇文章?

谢谢

最佳答案

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

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

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

关于algorithm - LCS和字符串相似度有什么关系?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39321700/

32 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com