algorithm - 对于我的数据集，我的模糊搜索方法会比使用 Lucene 更好吗？

Question

我想在我目前正在开发的网络应用程序中实现一个模糊搜索工具。后台是Java的，正好大家在这里推荐的搜索引擎，Lucene , 也是用 Java 编码的。但是，出于以下几个原因，我回避使用它:

1. 我会觉得构建自己的东西很有成就感。
2. Lucene 有很多我认为自己没有利用的功能；我想尽量减少膨胀。
3. 据我了解，Lucene 的模糊搜索实现会手动评估每个索引词的编辑距离。我觉得我想采用的方法(详见下文)会更有效率。

要索引的数据可能是英语中的整套名词和代词，因此您可以看到 Lucene 的模糊搜索方法让我感到厌倦。

我想做的是采用基于 n-gram 的方法来解决问题:从数据库中读取和标记每个项目，并将它们保存到磁盘中由给定 n-gram 及其位置命名的文件中。

例如:假设 n = 3，我的文件命名方案类似于:[n-gram]_[location_of_n-gram_in_string].txt。

文件 bea_0.txt 将包含:

bear
beau
beacon
beautiful
beats by dre

当我收到要搜索的术语时，我可以简单地将其标记为 n-gram，并使用它们及其相应的位置来读入相应的 n-gram 文件(如果存在)。然后，我可以对这组数据执行任何过滤操作(消除不在给定长度范围内的那些、执行编辑距离计算等)，而不是对整个数据集执行此操作。

我的问题是……嗯，我想我有几个问题。

1. Lucene 的模糊搜索是否有任何我不知道的改进，这将使我的方法变得不必要？
2. 这是实现模糊搜索的好方法(考虑到我正在处理的数据集)，还是我过于简单化/遗漏了什么？

Answer 1

Lucene 3.x 模糊查询用于评估 Levenshtein查询词和每个索引词之间的距离(蛮力法)。鉴于这种方法效率很低，Lucene spellchecker 曾经依赖于类似于您所描述的东西:Lucene 将首先搜索与查询术语具有相似 n-gram 的术语，然后根据字符串距离(例如Levenshtein 或 Jaro-Winckler )。

但是，这在 Lucene 4.0 ( an ALPHA preview has been released a few days ago ) 中发生了很大变化:FuzzyQuery now uses a Levenshtein automaton to efficiently intersect the terms dictionary .这要快得多，现在有一个新的 direct spellchecker。它不需要专门的索引，直接与自动机相交的术语字典，类似于 FuzzyQuery。