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