如何提高关键字搜索的性能？

Question

这是一个面试问题。

你必须编写程序，它会查找包含所有给定关键字的所有文件。你将如何预处理文件以改善搜索性能。

我的回答：

我会用Lucene（或任何其他文本的搜索引擎）。如果我需要手动实现它，我将建立一个索引，将文档字映射到文档ids。我们可能应该用B-trees来实现该索引。另一种方法是使用RDBMS（mySQL或smth），但它看起来对我来说太过分了。

它有道理吗？你会如何回答这个问题？

Answer 1

我同意，大部分时间文本的搜索引擎的是要走的路..真的很容易建立可靠。这里只是一个小细节：大多数引擎默认进行搜索或搜索，因此您必须指定要匹配所有单词。

如果你必须建立你自己的解决方案，是的，显然你必须建立映射..我会使用哈希查找而不是树索引，但你的树大概不会太大，所以这只是一个性能改善不大。不过，我没有看到使用树的时候，你不需要它的穿越功能，你将永远不会搜索上一个或下一个字..

更多有趣的细节弹出你在实际检查你将如何使用你的数据结构。我们举一个例子搜索：The pony he comes。直观地说，你不会开始查找the，可能所有的文件都包含它（假设它们是英文文本）。 pony是一个不错的选择，并且可以轻松缩小搜索范围。大多数文本搜索引擎都包含这样的指标：有多少文档包含该特定字词。因此，根据你从最不频繁的开始，并按增加的频率顺序检查单词。

一旦你设法缩小了搜索范围，你就开始意识到你的索引不能很好地工作......你仍然有the这个词来检查，并且在你的索引中会显示数十亿个文档，所以在这个指出使用反向映射会更好，从文档到单词（再次，哈希查找或trie）。你检查一些文件，看它们是否包含剩余的单词。

注：这里的许多决定（如何存储的映射，单一或双绘图，B树/散列/线索/ ...）取决于项目的规模。如果你必须在几个文件中搜索，建立一些简单的东西，并建立一些不同的东西，如果你必须索引github上的所有文件，或者用于基因序列搜索，甚至索引可能不适合内存...