我有大量的文档和文本文件，我想搜索相关的内容。我见过一个搜索工具，无法记住在哪里，它实现了一个很好的方法，正如我在下面的需求中所描述的。

我的要求如下：

• 我需要一个优化的搜索功能：我为该搜索功能提供了一个列表(一个或者多个)部分完整(或者完整)的单词，并用空格分隔。
• 然后，该函数查找所有包含以第一个单词开头或者等于第一个单词的单词的文档，然后使用第二个单词以相同的方式搜索这些找到的文档，依此类推，最后返回包含链接的实际单词的列表。以及包含它们的文档(名称和位置)，以获取完整的单词列表。
• 这些文档必须包含列表中的所有单词。
• 我想使用此功能进行按需搜索，以便可以以树状结构实时显示和更新结果。

我提出的解决方案的可能方法如下：
我用三个表创建一个数据库(最有可能使用mysql)：'Documents'，'Words'和'Word_Docs'。

• "文档"将包含所有文档(idDoc，名称，位置)。
• "单词"将具有(idWord，Word)，并且是所有文档中唯一单词的列表(一个特定单词仅出现一次)。
• 'Word_Docs'将具有(idWord，idDoc)，并且是出现在其中的每个单词和文档的唯一ID组合的列表。

然后，在每个按键(空格除外)上使用一个编辑框的内容来调用该函数：

• 字符串被标记化
• (在这里我的轮子有些旋转)：我确信可以构造一个SQL语句来返回所需的数据集：(actual_words，doc_name，doc_location)； (我不是SQL的热门电话)，或者是每个令牌的调用序列并解析出非重复的idDocs？
• 然后返回该数据集(/列表/数组)

然后显示返回的列表内容：

例如：呼叫：" seq sta cod"
显示：

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

(等等)

这是一种最佳的做法吗？该函数需要快速运行，还是仅在敲打空格时才应调用它？
它应该提供单词补全功能吗？ (获得数据库中的单词)至少这将防止对不存在的单词无用的调用该函数。
如果是单词补全：将如何实施？

(也许SO也可以使用这种类型的搜索解决方案来浏览标签？(在主页的右上角))

解决方案

不确定语法(这是sql server语法)，但是：

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

也就是说，无需使用like。有了类似的东西，情况就更加复杂了。

最快的方法肯定是根本不使用数据库，因为如果我们使用优化的数据手动进行搜索，则可以轻松击败精选的搜索性能。假设文档不经常更改，最快的方法是建立索引文件并使用它们来查找关键字。索引文件是这样创建的：

• 在文本文件中找到所有唯一的单词。就是用空格将文本文件分割成多个单词，然后将每个单词添加到列表中，除非已经在该列表中找到了。
• 将找到的所有单词按字母顺序排序；最快的方法是使用Three Way Radix QuickSort。在对字符串进行排序时，该算法的性能很难被超越。
• 将排序后的列表写入磁盘，每行一个单词。
• 现在，当我们要搜索文档文件时，请完全忽略它，而是将索引文件加载到内存中，然后使用二进制搜索来查找索引文件中是否包含单词。搜索大型，已排序的列表时，二进制搜索很难被击败。

或者，我们可以在单个步骤中合并步骤(1)和步骤(2)。如果我们使用InsertionSort(使用二进制搜索来找到正确的插入位置，以将新元素插入已经排序的列表中)，则不仅有一种快速的算法来查找单词是否已经在列表中，以防万一并非如此，我们将立即获得正确的位置来插入它，并且如果我们总是这样插入新的位置，则在执行步骤(3)时将自动获得一个已排序的列表。

问题是，每当文档发生更改时，我们都需要更新索引...但是，这对于数据库解决方案也不是正确的吗？另一方面，数据库解决方案为我们提供了一些优势：即使文档包含大量单词，也可以使用它，以至于索引文件不再适合存储(不太可能，因为即使所有英文单词的列表也会适合任何普通用户PC的内存)；但是，如果我们需要加载大量文档的索引文件，则内存可能会成为问题。好的，我们可以使用巧妙的技巧(例如，使用mmap等直接在映射到内存的文件中搜索)解决该问题，但是这些技巧与数据库已经使用它们来执行快速查找一样，因此，为什么要重新发明车轮？此外，我们还可以防止在文档发生更改时在搜索单词和更新索引之间出现锁定问题(也就是说，如果数据库可以为我们执行锁定操作，或者可以作为原子操作执行一次或者多次更新)。对于使用AJAX要求进行列表更新的Web解决方案，使用数据库可能是更好的解决方案(如果这是使用低级语言(如C)编写的本地运行应用程序，则我的第一个解决方案是比较合适的)。

如果我们希望在一个选择调用中完成所有操作(这可能不是最佳选择，但是当我们使用AJAX动态更新Web内容时，通常证明这是导致麻烦最少的解决方案)，则需要将所有三个表联接在一起。可能SQL有点生疏，但我将尝试一下：

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

好吧，也许这不是最快的选择...我想它可以做得更快。无论如何，它将找到所有包含至少一个单词的匹配文档，然后将所有相等的文档按ID分组在一起，计算将多少个文档分组在一起，最后仅在NumOfHits(在IN语句中找到的单词数)处显示结果等于IN语句中的单词数(如果我们搜索10个单词，则X为10)。

Google桌面搜索或者类似工具可能满足要求。

我们所说的内容称为反向索引或者发布列表，其操作与我们提出的内容以及Mecki提出的内容相似。那里有很多关于倒排索引的文献。 Wikipedia文章是一个不错的起点。

更好的方法是使用现有的反向索引实现，而不是尝试自己构建它。默认情况下，MySQL和PostgreSQL的最新版本都具有全文索引。我们可能还需要查看Lucene以获得独立的解决方案。编写良好的反向索引要考虑很多事情，包括标记化，词干，多词查询等，而预构建的解决方案将为我们完成所有这些工作。