这是一道面试题。
您必须编写程序，它可以找到包含所有给定关键字的所有文件。您将如何预处理文件以提高搜索性能。
我的回答:
我会使用 Lucene(或任何其他文本搜索引擎)。如果我需要手动实现它，我将建立一个索引，将文档单词映射到文档 ids。我们或许应该使用 B-trees 来实现该索引。另一种方法是使用 RDBMS(mySQL 或 smth.)，但对我来说这看起来有点矫枉过正。
有意义吗？你会如何回答这个问题？
最佳答案
我同意，大多数时候文本搜索引擎是要走的路..真的很容易构建而且可靠。这里只是一个小细节:大多数引擎默认执行 OR 搜索，因此您必须指定要匹配所有单词。
如果您必须构建自己的解决方案，是的，显然您必须构建映射。我会使用散列查找而不是树索引，但您的树大概不会太大，所以这只是次要的性能改进。不过，我不明白使用树的意义，你不需要它的遍历功能，你永远不会搜索上一个或下一个单词..
当您实际检查您将如何使用您的数据结构时，会弹出更多有趣的细节。让我们以搜索为例:The pony he comes。直觉上，您不会以 the 开始查找，可能所有文档都包含它(假设它们是英文文本)。 pony 是个不错的选择，可以轻松缩小搜索范围。大多数文本搜索引擎都包含一个度量标准:有多少文档包含该特定单词。因此，在此基础上，您从出现频率最低的单词开始，然后按出现频率递增的顺序检查单词。
一旦您设法缩小搜索范围，您就会开始意识到您的索引不能很好地工作......您仍然需要检查单词 the，并且在您的索引中将显示 zillion的文档，所以此时最好使用从文档到单词的反向映射(同样，哈希查找或 trie)。您检查了少量文档，看它们是否包含剩余的单词。
注意:这里的很多决定(如何存储映射，简单或双映射，btree/hash/trie/...)取决于项目的规模。很明显，如果你必须在几个文件中搜索，你构建的东西很简单，如果你必须在 github 上索引所有文件，或者用于基因序列搜索，即使索引可能不适合内存...
关于algorithm - 如何提高关键字搜索的性能？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15186229/