在大型數據集中檢測重複/相似的文本？

Question

我有一個包含數千條記錄的大型數據庫。每次用戶發佈他的信息時，我都需要知道是否已經有相同/相似的記錄。有沒有任何算法或開源實現來解決這個問題？

我們使用的是中國，什麼「相似」指的是記錄具有最相同的內容，可能是80％-100％是相同的。每個記錄不會太大，大約2k-6k字節

Answer 1

http://d3s.mff.cuni.cz/~holub/sw/shash/

http://matpalm.com/resemblance/simhash/

Answer 2

這個答案是一個非常複雜的類（最糟糕的情況下，它是五重奏，預計它是四次驗證您的數據庫的第一次，然後四/立方米添加一個記錄），所以它不能很好地擴展，遺憾的是我現在沒有更好的答案。

該算法被稱爲Ratcliff-Obershelp algorithm，它在python的difflib中實現。該算法本身是立方時間最壞情況和二次預期。那麼你必須爲每個可能的記錄對做到這一點，這是二次的。當添加記錄時，當然，這只是線性的。

編輯：對不起，我看錯文檔，difflib只有二次，而不是三次。使用它而不是其他算法。我已經習慣了做同樣的事情

Answer 3

一種方法是建立在平時的搜索索引基於詞的統計數據，然後使用新的項目，如果它是針對索引的搜索 - 如果分數在頂部的項目搜索過高，則新項目太相似。毫無疑問，一些標準的文本搜索庫可以用於這個，但如果它只有幾千條記錄，那麼構建自己的記錄是相當微不足道的。

Answer 4

看shngle分鐘散列技術。這是一個presentation，可以幫助你。