实施文档搜索引擎。

Question

问题背景

---

大家好，我正在处理一个搜索相关文档的项目，基于提供的查询。由于这是一个小型项目，我的内存结构很典型，我假设我没有超过100个文档，每个文档不超过1000个单词（一个单词不超过10个字符）。我会收到许多查询，并且必须尽快处理查询（绝对不能超过1秒）。

我的第一种方法（幼稚且不可扩展）：

---

由于用户可以上传文档，因此每当我收到一个文档时，我会查找“潜在”关键字并将关键字作为键和文档作为值对或在MYSQL表中存储。显然，这必须手动完成，不像程序员所做的那样。

我的第二种方法（略微改善）：

---

我取出每个文档，扫描其中的每个单词，并将此单词添加到Trie数据结构中，因此对于100个文档，我必须搜索100个Trie，并且如果查询长度为l，则该方法将花费最坏的O（所有文档中的单词数*最大单词长度）来构建trie，并查询O（查询长度）。这相当合理。 为了实现这一点，我将每个文档的Trie根节点保留在向量中，并遍历每个Trie节点并在每个Trie内搜索。如果我至少匹配查询的一半单词，我将将该文档存储为潜在结果。我不会给出超过某个截止文档数的结果。

我的问题：

---

我想问问社区，您对我的方法有何看法？我如何优化它们？我可以在现有方法中进行哪些其他改进？是否可以使用其他算法或数据结构更有效地完成此任务？ 在浏览网络时，我发现了像Boyer-Moore和Aho-Corasick这样的算法，以及一些建议调整Lucene Apache所实现的算法等。你有什么建议吗？

- hulk_baba

---

看看 elasticsearch。它非常可扩展，应该完美适合您的项目。 - CaptainTrunky

对于每个包含1000个单词的100个文档和每秒1个请求，grep 应该足够。如果您坚持采用某种索引策略，请维护一个按单词排序并进行二进制搜索的（单词、文档集）对列表。这可以简单地是一个文件。 - Rein Henrichs

对于真正的企业级索引，您可以使用任何喜欢的二叉搜索树。 - Rein Henrichs

@ReinHenrichs 不需要每秒一个请求，这些限制是因为我的系统内存限制。我的目标是从零开始构建它。 - hulk_baba

我只是使用您列出的要求。 - Rein Henrichs

Answer 1

实现全文搜索最基本的方法是构建一个倒排索引，并使用类似TF-IDF的度量标准对匹配的文档进行排名。

随着新的文档进入，您提取文档中的单词并将文档添加到倒排索引中。

当查询进来时，您从索引中找到匹配的文档，并根据TF-IDF（或其他您关心的指标）进行一些排序。然后，您返回k个排名最高的文档作为查询结果。

此外，在信息检索领域还有大量研究正在使操作更加高效，以及使结果（top-k文档）更好。

- Chen Pang