我有一个字符串数据库（任意长度），其中包含超过一百万项（可能更多）。
我需要将用户提供的字符串与整个数据库进行比较，如果存在相同的字符串，则检索出，否则返回最接近的模糊匹配（相似度为60％或更高）。搜索时间最好在一秒钟以内。
我的想法是在缩小的候选项范围内，基于它们的长度，使用编辑距离来比较每个数据库字符串和搜索字符串。
然而，考虑到我将需要经常执行此操作，我正在考虑构建一个数据库字符串的索引，保存在内存中并查询索引，而不是直接查询数据库。
有没有不同的方法来解决这个问题，或者如何建立内存索引的想法？
这篇论文似乎恰好描述了你想要的内容。
Lucene（http://lucene.apache.org/）还实现了Levenshtein编辑距离。
你没有提到你的数据库系统，但是对于PostrgreSQL，你可以使用以下 contrib 模块：trgm - Trigram matching for PostgreSQL。
pg_trgm贡献模块提供了基于trigram匹配确定文本相似性的函数和索引类。
如果您的数据库支持全文检索，您应该使用全文检索。否则，您可以使用像Lucene及其各种实现一样的索引器。
计算使用许多SQL数据库引擎内置的SOUNDEX哈希值，并通过它进行索引。
SOUNDEX是基于单词发音的哈希密钥，因此相同单词的拼写错误可能具有相同的SOUNDEX哈希密钥。
然后找到搜索字符串的SOUNDEX哈希，并进行匹配。
由于数据量很大，插入记录时，我会计算并将语音算法的值存储在一个索引列中，然后限制（WHERE子句）我的选择查询在该列的范围内。
《字符串、树和序列算法：计算机科学和计算生物学》一书中有相关算法的非常广泛的解释，作者是Dan Gusfield。
将此翻译为中文：https://en.wikipedia.org/wiki/Levenshtein_distance 莱文斯坦距离（Levenshtein distance）是指两个字符串之间由一个转换成另一个所需的最少编辑操作次数。可用于计算DNA序列和语言识别等领域。编辑操作包括插入一个字符、删除一个字符、替换一个字符。该算法由俄罗斯科学家弗拉基米尔·莱文斯坦（Vladimir Levenshtein）于1965年提出。
Levenshtein算法已在一些数据库管理系统中实施。
例如：PostgreSql：http://www.postgresql.org/docs/9.1/static/fuzzystrmatch.html（请翻译为中文）
