algorithm - 动态搜索和显示

Question

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

我的要求如下:

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

我想出的一种可能的解决方法如下:我创建了一个包含三个表的数据库(很可能使用 mysql):“Documents”、“Words”和“Word_Docs”。

• 'Documents' 将包含所有文档的 (idDoc, Name, Location)。
• 'Words' 将包含 (idWord, Word) ，并且是所有文档中唯一单词的列表(特定单词只出现一次)。
• 'Word_Docs' 将包含 (idWord, idDoc) ，并且是它出现的每个单词和文档的唯一 ID 组合列表。

然后在每次击键时使用编辑框的内容调用该函数(空格除外):

• 字符串被标记化
• (这里我的轮子有点转):我确信可以构造一个 SQL 语句来返回所需的数据集:(actual_words, doc_name, doc_location)； (我不是 SQL 的热门号码)，或者对每个标记进行一系列调用并解析出非重复的 idDocs？
• 然后返回此数据集(/list/array)

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

例如:调用:“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 也可以使用这种类型的搜索解决方案来浏览标签？(在主页的右上角))

Answer 1

你所说的是一个inverted index或发布列表，并且操作类似于您的建议和 Mecki 的建议。那里有很多关于倒排索引的文献；维基百科文章是一个很好的起点。

更好的是，与其尝试自己构建它，不如使用现有的倒排索引实现。默认情况下，MySQL 和最新版本的 PostgreSQL 都具有全文索引。您可能还想查看 Lucene为一个独立的解决方案。编写一个好的倒排索引需要考虑很多事情，包括标记化、词干提取、多词查询等，而预构建的解决方案将为您完成所有这些。