文本比較算法

我們在項目中有一個要求，我們必須比較兩個文本（update1，update2），並提出一個算法來定義有多少單詞和多少句子已經改變。文本比較算法

是否有任何算法可以使用它？我甚至不在尋找代碼。如果我知道算法，我可以用java編寫它。謝謝。

2012-01-30 java_mouse

http://stackoverflow.com/questions/65199/ c-sharp-comparison-algorithms – 2012-01-30 14:41:49

http://neil.fraser.name/software/diff_match_patch/myers.pdf – 2012-01-30 14:42:16

典型地，這通過尋找Longest Common Subsequence完成（通常稱爲LCS問題）。這就是diff這樣的工具的工作原理。當然，diff是一個面向行的工具，聽起來你的需求有所不同。但是，我假設你已經構建了一些方法來比較單詞和句子。

2012-01-30 14:40:52 FatalError

某種類型的差異變型的可能會有所幫助，如wdiff

如果你決定設計自己的算法，你將必須解決其中的一句話已經插入的情況。例如，對於以下兩個文件：

The men are bad. I hate the men

和

The men are bad. John likes the men. I hate the men

你的工具應該能夠向前看認識到，在第二，I hate the men還沒有被替換John likes the men但而不是被觸動，並在它之前插入一個新的句子。即它應該報告插入一個句子，而不是改變一個新句子後面的四個單詞。

2012-01-30 14:44:20 Howard

由diff和大多數其他比較實用程序的使用的具體算法是尤金Myer百貨公司An O(ND) Difference Algorithm and Its Variations。在java-diff-utils包中有一個Java實現。

2012-01-30 15:37:19

爲了您的信息，也有在下面GitHub上的頁面通過自己各種編程語言實現。

2012-01-31 11:05:14 cubicdaiya

困難來自效率，以良好的業績比較大的文件時。因此，我實施邁爾斯O（ND）的diff算法的變化 - 這表現相當好，準確的（與支持基於濾波正則表達式）：

2015-09-09 21:23:18

下面是描述其他文本比較算法，一般應輸出「更好」（例如兩個文件：主頁上的更多信息更小，更有意義的）差異：

第一文件引用所述第二和提及本繞其算法：

赫克爾[3]指出相似LCS技術存在的問題，並提出了線性石灰算法來檢測塊移動。如果字符串中沒有重複的符號，算法會充分執行。但是，該算法在其他情況下給出的結果不佳。例如，給定兩個字符串aabb和bbaa, Heckel的算法無法發現任何常見的子字符串。

第一紙在this answer提到和第二在this answer，既類似SO問題：

2017-01-12 17:30:18

回答