在大型數據庫中搜索（非常）近似子串

Question

我正在嘗試在大型數據庫中搜索長而近似的子串。例如，一個查詢可能是一個1000個字符的子字符串，它可能與數百次編輯的Levenshtein距離的匹配不同。我聽說索引q-grams可以做到這一點，但我不知道實現細節。我也聽說Lucene可以做到這一點，但Lucene的levenshtein算法能夠進行數百次編輯嗎？也許是剽竊檢測世界的一些東西？任何建議表示讚賞。

Answer 1

Q-克可能是一個辦法，但也有其他如高爐，BLASTP - 這是用於蛋白質，核苷酸等比賽

的Simmetrics庫的字符串距離的方法全面收集。

Answer 2

Lucene似乎並不是這裏的正確工具。除了Mikos的精彩建議，我聽說過AGREP,FASTA和Locality-Sensitive Hashing(LSH)。我認爲一個有效的方法應該首先修剪搜索空間，然後才能對剩餘的候選人進行更精細的評分。