在大型数据库中搜索（非常）近似的子字符串
我正在尝试在大型数据库中搜索长的近似子字符串。例如，查询可能是 1000 个字符的子字符串，该子字符串可能与匹配项的编辑距离相差数百个编辑。我听说索引 q-gram 可以做到这一点，但我不知道实现细节。我也听说 Lucene 可以做到这一点，但是 Lucene 的 levenshtein 算法是否足够快以进行数百次编辑？也许是剽窃检测领域之外的东西？任何建议表示赞赏。
I am trying to search for long, approximate substrings in a large database. For example, a query could be a 1000 character substring that could differ from the match by a Levenshtein distance of several hundred edits. I have heard that indexed q-grams could do this, but I don't know the implementation details. I have also heard that Lucene could do it, but is Lucene's levenshtein algorithm fast enough for hundreds of edits? Perhaps something out of the world of plagiarism detection? Any advice is appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Q-grams 可能是一种方法，但还有其他方法，例如 Blast、BlastP - 用于蛋白质、核苷酸匹配等。
Simmetrics 库是字符串距离方法的综合集合。
Q-grams could be one approach, but there are others such as Blast, BlastP - which are used for Protein, nucleotide matches etc.
The Simmetrics library is a comprehensive collection of string distance approaches.
Lucene 似乎不是合适的工具。除了 Mikos 的好建议之外，我还听说过 AGREP、FASTA 和 局部敏感哈希 (LSH)。我认为有效的方法应该首先大量修剪搜索空间，然后才对剩余的候选者进行更复杂的评分。
Lucene does not seem to be the right tool here. In addition to Mikos' fine suggestions, I have heard about AGREP, FASTA and Locality-Sensitive Hashing(LSH). I believe that an efficient method should first prune the search space heavily, and only then do more sophisticated scoring on the remaining candidates.