搜索引擎中的爬虫搜索策略探析

　　网络爬虫也称蜘蛛程序（Spider），是一个自动提取网页的程序， 在搜索引擎中占据重要位置。 网络爬虫对搜索引擎的查全、查准很有影响，对于爬虫来说就是尽可能多和快地给索引部分输送网页。 网络爬虫的好坏直接影响搜索结果页中的死链接的个数。 搜索引擎中网络爬虫的策略包括深度优先策略、广度优先策略不重复抓取策略、 网页抓取优先策略网页重访策略及网页抓取提速策略等，都是高性能爬虫的设计目标。

　　1 网络爬虫

　　1.1 搜索引擎网络爬虫介绍

　　网络爬虫是搜索引擎的重要模块[1-2],它自动从互联网中下载网页，从种子站点开始下载网页，同时从中读取其他的链，然后从这些链接地址寻找下一个网页，如此循环，并将爬取的网页加入到网页数据库中。 网络爬虫进入超级文本时利用 HTML 语言的标记结构来搜索信息及获取指向下一个超级文本的 URL地址，可以不依赖用户干预完成网络的自动爬取搜索。 当然在搜索时往往要采用一定的搜索策略。

　　1.2 网络爬虫运行过程

　　在网络爬虫爬行开始的时候， 需要给爬虫输送一个 URL 列表作为爬虫的开始位置， 爬虫从这些URL 开始爬行， 不断地发现新的 URL, 并根据策略爬行这些新发现的 URL,如此反复。 一般的爬虫都会自己建立 DNS 缓冲，这样就加快了 URL 解析成IP 地址的速度。

　　2 爬虫搜索策略

　　2.1 深度优先策略

　　深度优先策略是尽量往最远的地方走， 直到不能再走为止。 那么会发现爬虫爬了很多重复的结点，要控制爬虫爬行的路径，以避免重复结点就得要有一个较好的算法。 当然在爬行的过程中爬虫会做一些计算然后做出判断，如"是否要向深层爬行？ ""这个链接是否已经爬过？ "最后还要记录每次爬行的分支结点，为下次爬行做准备。 为方便描述深度优先策略，给出如图 2 的网页连接模型。

　　假设搜索引擎爬虫从"中国烟草资讯网"开始，根据深度优先策略，所爬行的路径为：

　　1）中国烟草资讯网→中国烟草学会网→中国烟草培训网2）中国烟草资讯网→中国烟草学会网→中国烟草科教网3）中国烟草资讯网→中国烟草→中国烟草标准化→云南烟叶信息网4）中国烟草资讯网→中国烟草→中国烟草标准化→中国电子商务网5）中国烟草资讯网→东方烟草报→新烟草6）中国烟草资讯网→东方烟草报→烟草在线→中国电子商务网2.2 广度优先策略。

　　由广度优先搜索策略[4]也称为"层次优先搜索策略",它是一种层次型距离不断增大的遍历方法，在抓取过程中，完成当前层的搜索后才进入下一层进行搜索。 很多研究将广度优先搜索策略应用于聚焦爬虫中。 其基本思想是认为与初始 URL 距离近的网页具有主题相关性的概率大。 对于图 2 的烟草网页连接模型，采用广度优先的策略爬取顺序为：中国烟草资讯网→中国烟草学会网→中国烟草→东方烟草报→中国烟草培训网→中国烟草科教网→中国烟草标准化→新烟草→烟草在线→云南烟叶信息网→中国电子商务网。

　　在抓取策略上，之所以广泛选择广度优先爬虫策略，主要有三个原因：

　　1）重要的网页往往离种子比较近。 例如我们打开新闻网站，越往后深入冲浪，网站的重要性越来越低。

　　2）万维网的实际深度最多达 17 层，广度优先策略总会以最快的速度找到最短路径到达某个网页。

　　3）广度优先也更适合爬虫的分布式处理，多个爬虫合作。

　　2.3 偏好烟草爬虫的最佳优先搜索策略

　　最佳优先策略就是尽可能地先抓取重要性的网页， 但是如何确定一个网页的重要性，如何量化这种重要性呢，这将是研究的重点。 下面以烟草行业为例说明偏好烟草爬虫的最佳优先搜索策略。

　　在 URL 队列中选择需要抓取的 URL 时， 按照重要的 URL先从队列中挑选出来进行抓取，不一定要按照"先进先出"的方式进行，这种策略称为"偏好选择". 而判断网页的重要性因素有很多，如链接的欢迎度、链接的重要度、平均链接深度、网站质量等等因素。

　　链接的欢迎度主要是由反向链接的数量和质量决定的，数目是指，一个网页如果有越多的链接指向它，那么表示其他网页对其的认可度越高，质量是指，这个网页如果有越多重要的网页指向，那么表示该网页重要性也很高，我们定义为：IB（p）。

　　链接的重要度仅仅考察 URL 字符本身，如".tobacco."和"in-dex"的 URL 重要性高于".travel."和"life",我们定义为 IL（p）。平均链接深度，是根据广度优先的原则计算出全站的平均链接深度，距离种子站点越近的重要性越高，反之则越低，记为 ID（p）。定义网页的重要性为 I（p），那么网页重要性公式可有如下公式：I（p）=xIB（p）+yIL（p）+zID（p）其中，x、y 参数用来调整 IB（p）及 IL（p）所占比例的大小，z是由宽度优先遍历规则决定。 如此每次选出的 URL 就是具有高重要性的网页。 例如，在图 2 中重要性为：中国烟草标准化>烟草在线>中国烟草科教网>中国烟草培训网>新烟草，那么可有遍历过程为：中国烟草资讯网→中国烟草学会网→中国烟草→东方烟草报→中国烟草标准化→烟草在线→中国烟草科教网→中国烟草培训网→新烟草→云南烟叶信息网→中国电子商务网。

　　2.4 非完全 PageRank 搜索策略
　　
　　PageRank 是一种链接分析算法，可衡量网页的重要性。 但其是在所有网页都下载完成后计算重要性的， 而爬虫在爬行的过程中只能看到部分页面， 要利用 PageRank 算法计算有如下策略思路：将已下载的网页，加上待抓取的 URL 队列中的 URL一起，进行 PageRank 算法，计算完成后，将待抓取的 URL 队列内的网页按照 PageRank 由高到低排序， 形成新的 URL 序列，爬虫按照此序列依次抓取。

　　那么对于图 2,以及网页重要性排序：中国烟草>东方烟草报>中国烟草学会网、 中国烟草标准化>烟草在线>中国烟草科教网>中国烟草培训网>新烟草，就有爬虫遍历的过程为：中国烟草资讯网→中国烟草→中国烟草标准化→东方烟草报→烟草在线→新烟草→中国烟草学会网→中国烟草科教网→中国烟草培训网→中国电子商务网→云南烟叶信息网。

　　2.5 烟草行业网页重访策略

　　针对烟草行业变化的模型， 制定以下以烟草为主题的爬行策略：

　　1） 首先选取一个或多个烟草行业的网站作为种子网站，如之前介绍的网页：中国烟草资讯网、中国烟草、中国烟草标准化、东方烟草报、烟草在线、新烟草、中国烟草学会网、中国烟草科教网、中国烟草培训网、中国电子商务网、云南烟叶信息网等。

　　2）然后对抓取的页面 URL 进行分类，如针对烟草行业网站的特点，将 URL 分为一级索引页，即首页；二级索引页（列表页如烟草政务信息，内容页如烟草新闻，产品页如烟草专卖等）。

　　3）给各级 URL 设定重访初始值。

　　4）根据 URL 的重访初始值对页面进行重访，根据重访的结果对初始值进行调整。 网页变化频率与搜索检查的频率的关系可用搜索结果中变化的次数除以时刻 0~时刻 t 的变化间隔 T,公式：

　　其中 r^表示λ^与搜索检查频率 f 的比值，λ^表示网页变化频率，X 表示网页变化的总次数，n 表示某时间间隔内搜索检查的次数。

　　5）最 后 ,根据以上策略 ,设置爬取队列 ,定时对队列中的URL 进行重访。 如若发现新的 URL 则重新处理，若发现页面发生变化则进行调整页面的重访值，若页面不存在，则在网页库中删除相应内容。

　　3 结束语

　　在爬虫系统中，待抓取的 URL 队列是很关键的部分，爬虫按照该队列 URL 序列依次爬虫，而爬虫的不同搜索策略决定了抓取的 URL 优先顺序有所不同。 爬虫的抓取策略有很多，但无论是哪种策略，其基本目标一致，就是优先选择重要网页进行抓取。 本文只选择代表性或效果较好的解决方案。