我有一个字符串数据库（任意长度），其中包含超过一百万个项目（可能更多）。
我需要将用户提供的字符串与整个数据库进行比较，如果存在则检索相同的字符串，否则返回最接近的模糊匹配（60% 相似性或更好）。理想情况下，搜索时间应低于一秒。
我的想法是在根据长度缩小数据库中的候选者之后，使用编辑距离将每个数据库字符串与搜索字符串进行比较。
但是，由于我需要经常执行此操作，我正在考虑构建数据库字符串的索引以保存在内存中并查询索引，而不是直接查询数据库。
关于如何以不同方式解决此问题或如何构建内存索引的任何想法？
Lucene ( http://lucene.apache.org/ ) 也实现了 Levenshtein 编辑距离。
您没有提及您的数据库系统，但对于 PostrgreSQL，您可以使用以下 contrib 模块：trgm - PostgreSQL 的三元组匹配
pg_trgm contrib 模块提供函数和索引类，用于根据 trigram 匹配确定文本的相似性。
如果您的数据库支持它，您应该使用全文搜索。否则，您可以使用诸如 lucene 之类的索引器及其各种实现。
由于数据量很大，因此在插入记录时，我将计算语音算法的值并将其存储在索引列中，然后将我的选择查询约束（WHERE 子句）在该列的某个范围内。
计算 SOUNDEX 哈希（内置在许多 SQL 数据库引擎中）并按它索引。
SOUNDEX 是基于单词发音的哈希值，因此同一个单词的拼写错误很可能具有相同的 SOUNDEX 哈希值。
然后找到搜索字符串的 SOUNDEX 哈希，并在其上进行匹配。
Dan Gusfield所著的《字符串、树和序列的算法：计算机科学和计算生物学》一书中对相关算法进行了非常广泛的解释。
https://en.wikipedia.org/wiki/Levenshtein_distance
Levenshtein 算法已在一些 DBMS 中实现
（例如 PostgreSql：http ://www.postgresql.org/docs/9.1/static/fuzzystrmatch.html ）