搜索引擎原理(五)
操作方法
- 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 所谓“间接”,指的是提供搜索服务的系统可能利用别人已经事先抓好的数据,元搜索引擎就 是如此。