維基百科使用什麼算法來進行版本比較功能

Question

我目前正在執行某種文本版本（修訂版）比較可視化，並試圖找到一些關於維基百科如何實現其「查看歷史」的信息 - 它們允許的特徵將當前修訂與舊版本進行比較。

你可以找到一個例子在這裏（關於計算器！）：

http://en.wikipedia.org/w/index.php?title=Stack_Overflow&diff=512241244&oldid=458578615

我迄今實施的一些想法，也試圖模仿維基百科是這樣做的方式。爲此，我實現了Levenshtein距離算法（http://en.wikipedia.org/wiki/Levenshtein_distance）。

讓我們假設我有兩個列表。我遍歷第一個列表，並檢查第一個列表的索引位置，如果在那裏找到的字符串超過50％相等，那麼檢查第一個列表的索引位置。如果是，我將在比較視圖中並排打印兩個字符串，並繼續處理第一個列表中的下一個項目。如果不是，我檢查第二個列表中的下一個項目，直到找到它，或者如果找不到第二個列表的字段，則將其留空。 （儘管我基本上更喜歡第二個列表中的句子也總是出現在比較視圖中，而不是將其排除在外，例如，第一個列表字段爲空白字段）

該方法有一些缺點。起初，如果某句話被刪除，我需要檢查索引周圍的位置，而不是簡單地「忘記」它。但是，如果我這樣做，我仍然需要注意文本位置不會倒置。

有沒有人試圖用java實現類似的東西？如果有一些代碼示例說明其他人或你是如何實現它的，我很樂意從它那裏學習。

當然，如果你知道關於算法維基百科的任何內容（以及我假設的一般維基），我們很樂意聽到它。

非常感謝

Answer 1

Wikipedia解釋維基差異引擎是如何工作的 - http://en.wikipedia.org/wiki/Help:Diff

您可以按照在鏈接頁面底部瞭解更多信息，但this page列出了使用的模板。

Answer 2

除了維基百科的版本控制的另一種實現是diff在Unix風味系統。 GNU實際上使得可供diff源代碼，這可以使你在他們的算法來看看這裏：

http://ftp.gnu.org/gnu/diffutils/