如何在大型字符串数据库中找到字符串的最佳模糊匹配

我有一个字符串数据库(任意长度),它拥有超过一百万个项目(可能更多).

我需要将用户提供的字符串与整个数据库进行比较,并检索相同的字符串(如果存在)或以其他方式返回最接近的模糊匹配(60%相似性或更好).理想情况下,搜索时间应小于一秒.

我的想法是使用编辑距离将每个数据库字符串与搜索字符串进行比较,然后根据数据库的长度缩小数据库中的候选项.

但是,因为我需要经常执行此操作,所以我正在考虑构建db字符串的索引以保留在内存中并查询索引,而不是直接查询db.

有关如何以不同方式解决此问题或如何构建内存中索引的任何想法？

本文似乎准确描述了你想要的东西.

Lucene(http://lucene.apache.org/)也实现了Levenshtein编辑距离.