indexing - 建立倒排索引的最佳方法是什么？

Question

我正在构建一个小型网络搜索引擎，用于搜索大约 100 万个网页，我想知道构建倒排索引的最佳方法是什么？使用 DBMS 还是什么……？从存储成本、性能、索引和查询速度等许多不同的角度？而且我不想使用任何开源项目，我想自己做一个！

Answer 1

当前的大多数闭源数据库管理器都具有某种全文索引功能。鉴于它的受欢迎程度，我猜大多数人还为 HTML 预先编写了过滤器，因此搜索类似的<p>内容不会为每个网页提供 1000 次点击。

如果您想完全自己完成这项工作，过滤 HTML 可能是最难的部分。从那里开始，倒排索引需要大量的文本处理，并产生很大的结果，但它基本上非常简单——你只需扫描所有文档，并构建一个单词列表及其位置（通常在过滤掉非常常见的诸如“a”、“an”、“and”等词，这些词不会是有意义的搜索词）然后将它们放在一个大索引中。

考虑到完整索引的大小，添加一个足够小的二级索引通常很有用，您可以确保它很容易适合实际内存（例如，将其限制为几百个左右的条目）。一个非常小（但有点无效）的版本只是通过单词的第一个字母，所以“A”单词从 0 开始，“B”从 12345 开始，“C”从 34567 开始，依此类推。但这并不是很有效——例如，以“A”开头的单词比以“X”开头的单词要多得多。建立索引更有效，然后选择在整个索引中均匀分布的几百个（或其他）单词。然后将其用作您的一级索引。从理论上讲，您可以做得更精细，例如像 B+ 树这样的东西，但那 s 通常是矫枉过正——在一百万个文档中，很可能你最终会得到少于十万个单词，这些单词的使用频率足以对索引大小产生很大的影响。即便如此，相当多的条目将是拼写错误之类的东西，而不是真实的单词......

Answer 2

如果你还在寻找，我想这本书有你的答案。

http://nlp.stanford.edu/IR-book/information-retrieval-book.html

Answer 3

也许您可能想详细说明为什么您不希望使用 Lucene 或 Sphinx 等 F/OSS 工具。

Answer 4

您可能想从 Hadoop 开始。它将有效地将您的索引构建分布在集群上。您可以使用任何语言。推荐使用 Java 和 Python。使用 Hadoop/MapReduce，您可以轻松索引您的网页。但是它们需要被缓存/存储在磁盘上，并且您需要一个解析器/标记器来首先提取文本。网上有一些免费的解析器。如果您想手动操作，可以从这里开始。一旦有了索引，存储它就是另一项任务。