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

Question

我有一个字符串数据库(任意长度)，其中包含超过一百万个项目(可能更多)。

我需要将用户提供的字符串与整个数据库进行比较，并检索相同的字符串(如果存在)，否则返回最接近的模糊匹配(相似度为60％或更高)。理想的搜索时间应小于一秒。

我的想法是在根据候选数据库的长度缩小候选数据库的范围后，使用编辑距离将每个数据库字符串与搜索字符串进行比较。

但是，由于我将需要经常执行此操作，因此我正在考虑构建数据库字符串的索引以保留在内存中并查询该索引，而不是直接查询数据库。

关于如何以不同方式处理此问题或如何建立内存索引的任何想法？

Answer 1

This paper seems to describe exactly what you want.

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