我正在尝试在大型数据库中搜索长而近似的子字符串。例如，查询可能是一个 1000 个字符的子字符串，它可能与匹配项相差数百个编辑的 Levenshtein 距离。我听说索引 q-gram 可以做到这一点，但我不知道实现细节。我也听说 Lucene 可以做到，但是 Lucene 的 levenshtein 算法是否足够快，可以进行数百次编辑？也许是抄袭检测领域之外的东西？任何建议表示赞赏。
问问题
280 次
2 回答
1
Q-gram 可能是一种方法，但还有其他方法，例如 Blast、BlastP - 用于蛋白质、核苷酸匹配等。
Simmetrics库是字符串距离方法的综合集合。
于 2010-08-08T01:24:09.613 回答
1
Lucene 在这里似乎不是正确的工具。除了 Mikos 的好建议，我还听说过AGREP、FASTA和Locality-Sensitive Hashing(LSH)。我相信一种有效的方法应该首先大量修剪搜索空间，然后才对剩余的候选者进行更复杂的评分。
于 2010-08-08T11:55:35.013 回答