在大型数据库中搜索(非常)近似子字符串

Question

我试图在大型数据库中搜索长的近似子串.例如,查询可以是1000个字符的子字符串,它可以通过几百次编辑的Levenshtein距离与匹配不同.我听说索引的q-gram可以做到这一点,但我不知道实现细节.我也听说过Lucene可以做到这一点,但是Lucene的levenshtein算法能够快速进行数百次编辑吗？也许是抄袭检测世界的东西？任何建议表示赞赏.

Answer 1

Q-grams 可能是一种方法，但还有其他方法，例如 Blast、BlastP - 用于蛋白质、核苷酸匹配等。

Simmetrics库是字符串距离方法的综合集合。