搜索引擎原理(五)
操作方法
- 01
的形式就是q 在其中直接出现。不过后面我们会看到，如果一个搜索引擎就是以 百分之百满足这种简单的包含关系为目标，即使实现了也并不就达到了最好的效 果。 “列表”，这蕴含着一种“序”（rank ）。在绝大多数情况下，L 是相当长的， 例如超过 1 万个条目（这是和图书馆全文检索系统的又一个不同，那里返回的列 表通常较短，例如几十个条目）。这不仅是由于 Web 上的信息量大，也由于搜索 引擎的查询方式简单。简单，意味着抽象；抽象，意味着有更多的具体事物可能 是它的体现。对于一个长长的列表，很少有用户有耐心都审视一遍（不仅是因为 长，还因为大多数使用搜索引擎的用户通常都是“找到为止”，而不是“不全部找 到不罢休”，加上这个列表中和一个用户关心的其实只占很少的比例）。有分析统 计表明，用户平均察看返回结果不超过 2 页[Baldi, et al.,2003],[Wang, et al.,2001],[单松巍,2003]。 现代大规模高质量搜索引擎一般采用如图 2-2 所示的称之为三段式的工作流 程，即：网页搜集、预处理和查询服务。 搜集 预处理 服务 图2-2 搜索引擎三段式工作流程 第二节 网页搜集 搜索引擎这样一个软件系统应该是何种工作方式？如果说软件系统是工作 在某个数据集合上的程序的话，这个软件系统操作的数据不仅包括内容不可预测 的用户查询，还要包括在数量上动态变化的海量网页，并且这些网页不会主动送 到系统来，而是需要由系统去抓取。 首先，我们考虑抓取的时机：事先还是即时。我们都有经验，在网络比较畅 通的情况下，从网上下载一篇网页大约需要 1 秒钟左右，因此如果在用户查询的 时候即时去网上抓来成千上万的网页，一个个分析处理，和用户的查询匹配，不 可能满足搜索引擎的响应时间要求。不仅如此，这样做的系统效益也不高（会重 复抓取太多的网页）；面对大量的用户查询，不可能想象每来一个查询，系统就到 网上“搜索”一次。 因此我们看到，大规模搜索引擎服务的基础应该是一批预先搜集好的网页 （直接或者间接）。这一批网页如何维护？可以有两种基本的考虑。 定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。由于每 次都是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花几周。 而由于这样做开销较大，通常两次搜集的间隔时间也不会很短（例如早期天网的 版本大约每3 个月来一次，Google 在一段时间曾是每隔28 天来一次）。这样做的 好处是系统实现比较简单，主要缺点是“时新性”（freshness）不高，还有重复搜 集所带来的额外带宽的消耗。 增量搜集，开始时搜集一批，往后只是（1）搜集新出现的网页，（2 ）搜集 那些在上次搜集后有过改变的网页，（3）发现自从上次搜集后已经不再存在了的 网页，并从库中删除。由于除新闻网站外，许多网页的内容变化并不是很经常的 （ 有 研 究 指 出 50% 网 页 的 平 均 生 命 周 期 大 约 为 50 天 [Cho and Garcia-Molina,2000]，[Cho,2002]），这样做每次搜集的网页量不会很大（例如我 们在 2003 年初估计中国每天有 30-50 万变化了的网页），于是可以经常启动搜集 过程（例如每天）。30 万网页，一台PC 机，在一般的网络条件下，半天也就搜集 完了。这样的系统表现出来的信息时新性就会比较高，主要缺点是系统实现比较 复杂；这种复杂还不仅在于搜集过程，而是还在于下面要谈到的建索引的过程。 上面讲的是系统网页数据库维护的基本策略。在这两种极端的情况之间也可 能有一些折中的方案，J. Cho 博士在这方面做过深入的研究[Cho and Garcia-Molina,2000]，[Cho,2002]，根据一种网页变化模型和系统所含内容时新性 的定义，提出了相应优化的网页搜集策略。其中一个有趣的结论是：在系统搜集 能力一定的情况下，若有两类网页（例如“商业”和“教育”），它们的更新周期 差别很大（例如“商业”类网页平均更新周期是“天”，而“教育”类网页平均更 新周期是“月”），则系统应该将注意力放在更新慢的网页上[Cho and Garcia-Molina,2000]，以使系统整体的时新性达到比较高的取值。 在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见 的一种是所谓“爬取”：将Web 上的网页集合看成是一个有向图，搜集过程从给 定起始 URL 集合 S （或者说“种子”）开始，沿着网页中的链接，按照先深、先 宽、或者某种别的策略遍历，不停的从S 中移除URL，下载相应的网页，解析出 网页中的超链接URL，看是否已经被访问过，将未访问过的那些URL 加入集合 S 。整个过程可以形象地想象为一个蜘蛛（spider）在蜘蛛网（Web ）上爬行（crawl）。 后面我们会看到，真正的系统其实是多个“蜘蛛”同时在爬。 这种方式的好处除了概念很漂亮，一般实现起来也不困难外，还有很重要的 一条是容易通过一定的策略，使搜集到的网页相对比较“重要”。前面提过，任何 1 所谓“间接”，指的是提供搜索服务的系统可能利用别人已经事先抓好的数据，元搜索引擎就 是如此。