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中所示。