我正在尝试在大型数据库中搜索长的、近似的子字符串。例如，一个查询可能是一个 1000 个字符的子字符串，它可能与匹配项相差数百个编辑的 Levenshtein 距离。我听说索引 q-gram 可以做到这一点，但我不知道实现细节。我也听说 Lucene 可以做到，但是 Lucene 的 levenshtein 算法是否足够快以进行数百次编辑？也许是抄袭检测的世界之外的东西？任何建议表示赞赏。
最佳答案
Q-gram 可能是一种方法，但还有其他方法，例如 Blast、BlastP——用于蛋白质、核苷酸匹配等。
Simmetrics库是字符串距离方法的综合集合。
关于indexing - 在大型数据库中搜索(非常)近似子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3432276/