简析搜索引擎中网络爬虫的搜索策略

    随着互联网的兴起及发展，人们获取信息的途径由传统方式逐渐被网络替代。 起初人们主要通过浏览网页来获取所需信息， 但随着Web不断庞大用这种方式来寻找自己所需的信息变得越来越困难。现在大多数的人很大程度上依赖于搜索引擎来帮助自己获取有用信息，因此搜索引擎技术作为最典型的Web信息获取技术 其发展直接影响人们获取信息的质量。

    自从1994 年4 月世界上第一个Web 检索工具Web Crawler 问世以来， 目前较流行的搜索引擎已有Google、Yahoo、AltaVista、Infoseek、InfoMarket等。出于商业机密的考虑， 目前各个搜索引擎使用的Crawler 系统的技术内幕一般都不公开，现有的文献也仅限于概要性介绍。随着Web 信息资源呈指数级增长及Web 信息资源动态变化， 传统的搜索引擎提供的信息检索服务已不能满足人们日益增长的对个性化服务的需要，它们正面临着巨大的挑战。以何种策略访问Web提高搜索效率 成为近年来专业搜索引擎网络爬虫研究的主要问题之一。

    1　网络爬虫的工作原理

    网络爬虫出自Sp ider 的意译，具有相同词义的词语还有Crawler、robots、bots、wanderer等等。网络爬虫定义有广义和狭义之分，狭义上的定义为利用标准的http协议根据超链和Web文档检索的方法遍历万维网信息空间的软件程序；而广义则是所有能利用http协议检索Web文档的软件都称之为网络爬虫。

    网络爬虫是一个功能很强的自动提取网页的程序, 它为搜索引擎从万维网上下载网页，是搜索引擎的重要组成。 它通过请求站点上的HTML 文档访问某一站点。它遍历Web 空间，不断从一个站点移动到另一个站点，自动建立索引并加入到网页数据库中。网络爬虫进入某个超级文本时, 它利用HTML语言的标记结构来搜索信息及获取指向其他超级文本的URL 地址，可以完全不依赖用户干预实现网络上的自动“爬行”和搜索。 网络爬虫在搜索时往往采用一定的搜索策略。

    2　宽度或深度优先搜索策略

    搜索引擎所用的第一代网络爬虫主要是基于传统的图算法，如宽度优先或深度优先算法来索引整个Web，一个核心的URL 集被用来作为一个种子集合，这种算法递归的跟踪超链接到其它页面，而通常不管页面的内容，因为最终的目标是这种跟踪能覆盖整个Web。这种策略通常用在通用搜索引擎中，因为通用搜索引擎获得的网页越多越好，没有特定的要求. 如图1 所示：

    2. 1　宽度优先搜索算法

    宽度优先搜索算法(又称广度优先搜索) 是最简便的图的搜索算法之一， 这一算法也是很多重要的图的算法的原型. Dijktra 单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想.宽度优先搜索算法是沿着树的宽度遍历树的节点，如果发现目标则算法中止。该算法的设计和实现相对简单属于盲目搜索。 在目前为覆盖尽可能多的网页，一般使用宽度优先搜索方法。也有很多研究将宽度优先搜索策略应用于聚焦爬虫中。其基本思想是认为与初始U RL 在一定链接距离内的网页具有主题相关性的概率很大。 另外一种方法是将宽度优先搜索与网页过滤技术结合使用， 先用广度优先策略抓取网页，再将其中无关的网页过滤掉. 这些方法的缺点在于， 随着抓取网页的增多大量的无关网页将被下载并过滤,算法的效率将变低。

    2. 2　深度优先搜索

    深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边 就沿此边继续汉下去。当结点v 的所有边都己被探寻过，搜索将回溯到发现结点v 有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止. 深度优先在很多情况下会导致爬虫的陷入( t rapped) 问题, 所以它既不是完备的，也不是最优的。

    3　聚焦搜索策略

    基于第一代网络爬虫的搜索引擎抓取的网页一般少于1 000 000 个网页, 极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待10s甚至更长的时间. 随着网页页信息的指数级增长及动态变化， 这些通用搜索引擎的局限性越来越大，随着科学技术的发展, 定向抓取相关网页资源的聚焦爬虫便应运而生。

    聚焦爬虫的爬行策略只挑出某一个特定主题的页面，根据“最好优先原则”进行访问，快速、有效地获得更多的与主题相关的页面，主要通过内容和Web 的链接结构来指导进一步的页面抓取。图2表明了典型的应用聚焦策略爬虫的爬行规则。

    聚焦爬虫会给它所下载下来的页面分配一个评价分，然后根据得分排序。最后插入到一个队列中. 最好的下一个搜索将通过对弹出队列中的第一个页面进行分析而执行，这种策略保证爬虫能优先跟踪那些最有可能链接到目标页面的页面。决定网络爬虫搜索策略的关键是如何评价链接价值，即链接价值的计算方法， 不同的价值评价方法计算出的链接的价值不同, 表现出的链接的“重要程度”也不同， 从而决定了不同的搜索策略。由于链接包含于页面之中，而通常具有较高价值的页面包含的链接也具有较高的价值，因而对链接价值的评价有时也转换为对页面价值的评价. 这种策略通常运用在专业搜索引擎中，因为这种搜索引擎只关心某一特定主题的页面。

    3. 1　基于内容评价的搜索策略

    基于内容评价的搜索策略主要是根据主题(如关键词、主题相关文档) 与链接文本的相似度来评价链接价值的高低，并以此决定其搜索策略： 链接文本是指链接周围的说明文字和链接URL 上的文字信息， 相似度的评价通常采用以下公式：

    其中di为新文本的特征向量，dj为第j类的中心向量，m为特征向量的维数，wk为向量的第K维。

    由于Web页面不同于传统的文本，它是一种半结构化的文档，包含许多结构信息Web页面不是单独存在的，页面中的链接指示了页面之间的相互关系，因而有些学者提出了基于链接结构评价链接价值的方法。

    3. 2　基于链接结构评价的搜索策略

    基于链接结构评价的搜索策略，是通过对Web页面之间相互引用关系的分析来确定链接的重要性，进而决定链接访问顺序的方法。通常认为有较多入链或出链的页面具有较高的价值。PageRank和Hits是其中具有代表性的算法。

    3. 2. 1 　PageRank 算法

    基于链接评价的搜索引擎的优秀代表是Google，它独创的“链接评价体系”(PageRank 算法) 是基于这样一种认识，一个网页的重要性取决于它被其它网页链接的数量，特别是一些已经被认定是“重要”的网页的链接数量。PageRank 算法最初用于Google 搜索引擎信息检索中对查询结果的排序过程，近年来被应用于网络爬虫对链接重要性的评价，PageRank 算法中页面的价值通常用页面的PageRank值表示，若

     设页面p 的PageRank 值为PR (p ) ，则PR (p ) 采用如下迭代公式计算：

    其中T 为计算中的页面总量，C< 1 是阻尼常数因子，in (p ) 为所有指向p 的页面的集合，ou t (C) 为页面C出链的集合. 基于PageRank 算法的网络爬虫在搜索过程中通过计算每个已访问页面的PageRank 值来确定页面的价值，并优先选择PageRank 值大的页面中的链接进行访问。

    3. 2. 2　H ITS 算法

    HITS 方法定义了两个重要概念：Authority和Hub. Authority 表示一个权威页面被其它页面引用的数量，即该权威页面的入度值。网页被引用的数量越大, 则该网页的Authority值越大； Hub 表示一个Web页面指向其它页面的数量，即该页面的出度值。网页的出度值越大其Hub 值越高。由于Hub 值高的页面通常都提供了指向权威页面的链接，因而起到了隐含说明某主题页面权威性的作用。

    HITS (Hyperlink- Induced Topic Search) 算法是利用Hub.Authority方法的搜索方法，Authority表示一个页面被其它页面引用的数量， 即该页面的入度值。Hub 表示一个W eb 页面指向其它页面的数量，即该页面的出度值。算法如下：将查询q 提交给传统的基于关键字匹配的搜索引擎。搜索引擎返回很多网页，从中取前n 个网页作为根集用S 表示。通过向S 中加入被S 引用的网页和引用S 的网页将S 扩展成一个更大的集合T。以T 中的Hub 网页为顶点集V l，以权威网页顶点集V 2，V 1 中的网页到V 2 中的网页的超链接为边集E , 形成一个二分有向图S G = (V 1,V 2, E )。对V 1 中的任一个顶点v，用H (v ) 表示网页v 的Hub值，对V 2 中的顶点u, 用A (u) 表示网页的Authority值。开始时H (v ) = A (u) = 1，对u 执行公式(1) 来修改它的A (u) ，对v 执行公式(2) 来修改它的H (v ) ，然后规范化A (u) ，H (v ) ，如此不断的重复计算上述运算，直到A (u)，H (v ) 收敛。

    式(1) 反映了若一个网页由很多好的Hub 指向，则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub值之和)。式(2) 反映了若一个网页指向许多好的权威页，则Hub 值也会相应增加(即Hub 值增加为该网页链接的所有网页的权威值之和)。虽然基于链接结构评价的搜索考虑了链接的结构和页面之间的引用关系，但忽略了页面与主题的相关性，在某些情况下会出现搜索偏离主题的问题。另外搜索过程中需要重复计算PageRank值或Authority以及Hub权重，计算复杂度随页面和链接数量的增长呈指数级增长。

    3. 3　基于巩固学习的聚焦搜索

    近年来对W eb 信息资源分布的研究表明很多类型相同的网站在构建方式上，主题相同的网页在组织方式上都存在着一定的相似性，有的学者就考虑将巩固学习引入网络爬虫的训练过程中，从这些相似性获取一些“经验”，而这些经验信息在搜索距相关页面集较远的地方往往能获得较好的回报，而前两种策略在这种情况下容易迷失方向。在巩固学习模型中，把网络爬虫经过若干无关页面的访问之后才能获得的主题相关页面称为未来回报，对未来回报的预测值称为未来回报价值，用Q价值表示。这种方法的核心就是学习如何计算链接的Q 价值，根未来回报价值确定正确的搜索方向。目前这类搜索策略不足之处在于学习效率低的问题，而且在训练过程中增加了用户的负担。

    3. 4　基于语境图的聚焦搜索

    基于巩固学习的网络爬虫通过计算链接的Q价值可以确定搜索方向，但它却无法估计距离目标页面的远近。为此 Diligen t 等提出了基于“语境图”的搜索策略，它通过构建典型页面的web“语境图”来估计离目标页面的距离，距离较近的页面较早得到访问。基于“语境图”的搜索策略需要借助已有的通用搜索引擎构建“语境图”，而搜索引擎的检索结果并非一定代表真实的web 结构，因而这种方式也具有局限性。

    4　小结

    通过以的分析，各类搜索策略各有的优缺点，网络爬虫搜索策略的研究对搜索引擎的应用与发展有着重要意义。一种好的策略就是要在合理的时间限度内，以较少的网络资源、存储资源和计算资源的消耗获得更多的与主题相关页面。因而未来网络爬虫所使用的策略应该在提高链接价值预测的准确性、降低计算的时空复杂度，以及增加网络爬虫的自适应性等方面有所发展，有所突破。

    本文作者：刘世涛(江苏联合职业技术学院连云港财经分院, 江苏连云港　222003)

建议继续学习：