1　网络爬虫的工作原理
网络爬虫出自Spider 的意译, 具有相同词义的词语还有Crawler, robots, bots, wanderer 等等.网络爬虫定义有广义和狭义之分, 狭义上的定义为利用标准的h t tp 协议根据超链和W eb 文档检索的方法遍历万维网信息空间的软件程序; 而广义则是所有能利用h t tp 协议检索W eb 文档的软件都称之为网络爬虫.网络爬虫是一个功能很强的自动提取网页的程序, 它为搜索引擎从万维网上下载网页, 是搜索引擎的重要组成. 它通过请求站点上的HTML 文档访问某一站点. 它遍历W eb 空间, 不断从一个站点移动到另一个站点, 自动建立索引, 并加入到网页数据库中. 网络爬虫进入某个超级文本时, 它利用HTML语言的标记结构来搜索信息及获取指向其他超级文本的U RL 地址, 可以完全不依赖用户干预实现网络上的自动“爬行”和搜索. 网络爬虫在搜索时往往采用一定的搜索策略.
2　宽度或深度优先搜索策略
搜索引擎所用的第一代网络爬虫主要是基于传统的图算法, 如宽度优先或深度优先算法来索引整个W eb, 一个核心的U RL 集被用来作为一个种子集合, 这种算法递归的跟踪超链接到其它页面, 而通常不管页面的内容, 因为最终的目标是这种跟踪能覆盖整个W eb. 这种策略通常用在通用搜索引擎中,因为通用搜索引擎获得的网页越多越好, 没有特定的要求.

2. 1　宽度优先搜索算法

宽度优先搜索算法(又称广度优先搜索) 是最简便的图的搜索算法之一, 这一算法也是很多重要的图的算法的原型. D ijk st ra 单源最短路径算法和P rim 最小生成树算法都采用了和宽度优先搜索类似的思想.宽度优先搜索算法是沿着树的宽度遍历树的节图1 传统的图算法点, 如果发现目标, 则算法中止. 该算法的设计和实现相对简单, 属于盲目搜索. 在目前为覆盖尽可能多的网页, 一般使用宽度优先搜索方法. 也有很多研究将宽度优先搜索策略应用于聚焦爬虫中. 其基本思想是认为与初始U RL 在一定链接距离内的网页具有主题相关性的概率很大. 另外一种方法是将宽度优先搜索与网页过滤技术结合使用, 先用广度优先策略抓取网页, 再将其中无关的网页过滤掉. 这些方法的缺点在于, 随着抓取网页的增多, 大量的无关网页将被下载并过滤, 算法的效率将变低.
2. 2　深度优先搜索
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图. 在深度优先搜索中, 对于最新发现的顶点, 如果它还有以此为起点而未探测到的边, 就沿此边继续汉下去. 当结点v 的所有边都己被探寻过, 搜索将回溯到发现结点v 有那条边的始结点. 这一过程一直进行到已发现从源结点可达的所有结点为止. 如果还存在未被发现的结点, 则选择其中一个作为源结点并重复以上过程, 整个进程反复进行直到所有结点都被发现为止. 深度优先在很多情况下会导致爬虫的陷入( t rapped) 问题, 所以它既不是完备的, 也不是最优的.
3　聚焦搜索策略
基于第一代网络爬虫的搜索引擎抓取的网页一般少于1 000 000 个网页, 极少重新搜集网页并去刷新索引. 而且其检索速度非常慢, 一般都要等待10 s甚至更长的时间. 随着网页页信息的指数级增长及动态变化, 这些通用搜索引擎的局限性越来越大, 随着科学技术的发展, 定向抓取相关网页资源的聚焦爬虫便应运而生.聚焦爬虫的爬行策略只挑出某一个特定主题的页面, 根据“最好优先原则”进行访问, 快速、有效地获得更多的与主题相关的页面, 主要通过内容和W eb 的链接结构来指导进一步的页面抓取.表明了典型的应用聚焦策略爬虫的爬行规则.聚焦爬虫会给它所下载下来的页面分配一个评价分, 然后根据得分排序, 最后插入到一个队列中. 最好的下一个搜索将通过对弹出队列中的第一个页面进行分析而执行, 这种策略保证爬虫能优先跟踪些最有可能链接到目标页面的页面. 决定网络爬虫搜索策略的关键是如何评价链接价值, 即链接价值的计算方法, 不同的价值评价方法计算出的链接的价值不同, 表现出的链接的“重要程度”也不同, 从而决定了不同搜索策略. 由于链接包含于页面之中,而通常具有较高价值的页面包含的链接也具有较高的价值, 因而对链接价值的评价有时也转换为对页面价值的评价. 这种策略通常运用在专业搜索引擎中, 因为这种搜索引擎只关心某一特定主题的页面.
3. 1　基于内容评价的搜索策略
基于内容评价的搜索策略主要是根据主题(如关键词、主题相关文档) 与链接文本的相似度来评价链接价值的高低, 并以此决定其搜索策略: 链接文本是指链接周围的说明文字和链接U RL 上的文字信息, 相似度的评价通常采用以下公式:
sim (d i, d j ) =Σmk= 1w ik ×w jk(Σmk= 1w 2ik ) (Σmk= 1w 2jk )
其中, d i 为新文本的特征向量, d j 为第j 类的中心向量,m 为特征向量的维数,w k 为向量的第K 维.由于W eb 页面不同于传统的文本, 它是一种半结构化的文档, 包含许多结构信息W eb 页面不是单独存在的, 页面中的链接指示了页面之间的相互关系, 因而有些学者提出了基于链接结构评价链接价值的方法.
3. 2　基于链接结构评价的搜索策略
基于链接结构评价的搜索策略, 是通过对W eb页面之间相互引用关系的分析来确定链接的重要性, 进而决链接访问顺序的方法. 通常认为有较多入链或出链的页面具有较高的价值. PageRank 和H it s 是其中具有代表性的算法.
3. 2. 1 　PageRank 算法
基于链接评价的搜索引擎的优秀代表是Google (h t tp: ööw ww. Google. com ) , 它独创的“链接评价体系”(PageRank 算法) 是基于这样一种认识, 一个网页的重要性取决于它被其它网页链接的数量, 特别是一些已经被认定是“重要”的网页的链接数量. PageRank 算法最初用于Google 搜索引擎信息检索中对查询结果的排序过程[ 5 ] , 近年来被应用于网络爬虫对链接重要性的评价, PageRank 算法中, 页面的价值通常用页面的PageRaz3 值表示, 若设页面p 的PageRank 值为PR (p ) , 则PR (p ) 采用如下迭代公式计算:PR (p ) = C 1T+ (1 - C) Σ C∈in (p )PR (p )ûou t (C) û其中T 为计算中的页面总量, C< 1 是阻尼常数因子, in (p ) 为所有指向p 的页面的集合, ou t (C) 为页面C出链的集合. 基于PageRank 算法的网络爬虫在搜索过程中, 通过计算每个已访问页面的PageR2ank 值来确定页面的价值, 并优先选择PageRank 值大的页面中的链接进行访问.
3. 2. 2　H ITS 算法
H ITS 方法定义了两个重要概念: A u tho rity 和Hub. A u tho rity 表示一个权威页面被其它页面引用的数量即该权威页面的入度值. 网页被引用的数量越大, 则该网页的A u tho rity 值越大; Hub 表示一个W eb 页面指向其它页面的数量, 即该页面的出度值. 网页的出度值越大, 其Hub 值越高. 由于Hub 值高的页面通常都提供了指向权威页面的链接, 因而起到了隐含说明某主题页面权威性的作用.H ITS (HyperlinkInducedTopicSearch) 算法是利用HuböA u tho rity 方法的搜索方法,A u tho rity表示一个页面被其它页面引用的数量, 即该页面的
入度值. 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) 表示网页的A u tho rity
值. 开始时H (v ) = A (u) = 1, 对u 执行公式(1) 来修改它的A (u) , 对v 执行公式(2) 来修改它的H (v ) , 然后规范化A (u) , H (v ) , 如此不断的重复计算上述运算, 直到A (u) , H (v ) 收敛.　A (u) = Σ v: (v , u) ∈EH (v ) (1)
H (v ) = Σ v: (v, u) ∈EA (v ) (2)式(1) 反映了若一个网页由很多好的Hub 指向, 则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub 值之和). 式(2) 反映了若一个网页指向许多好的权威页, 则Hub 值也会相应增加(即Hub 值增加为该网页链接的所有网页的权威值之和).虽然基于链接结构评价的搜索考虑了链接的结构和页面之间的引用关系, 但忽略了页面与主题的相关性, 在某些情况下, 会出现搜索偏离主题的问题. 另外, 搜索过程中需要重复计算PageRank 值或A u tho rity 以及Hub 权重, 计算复杂度随页面和链
接数量的增长呈指数级增长
3. 3　基于巩固学习的聚焦搜索
近年来对W eb 信息资源分布的研究表明很多类型相同的网站在构建方式上, 主题相同的网页在组织方式上都存在着一定的相似性, 有的学者就考虑将巩固学习引入网络爬虫的训练过程中, 从这些相似性获取一些“经验”, 而这些经验信息在搜索距相关页面集较远的地方往往能获得较好的回报, 而前两种策略在这种情况下容易迷失方向.在巩固学习模型中, 把网络爬虫经过若干无关页面的访问之后才能获得的主题相关页面称为未来回报, 对未来回报的预测值称为未来回报价值, 用Q价值表示. 这种方法的核心就是学习如何计算链接的Q 价值, 根据未来回报价值确定正确的搜索方向. 目前这类搜索策略不足之处在于学习效率低的问题, 而且在训练过程中增加了用户的负担.
3. 4　基于语境图的聚焦搜索
基于巩固学习的网络爬虫通过计算链接的Q价值可以确定搜索方向, 但它却无法估计距离目标页面的远近. 为此, D iligen t 等提出了基于“语境图”的搜索策略, 它通过构建典型页面的w eb“语境图”来估计离目标页面的距离, 距离较近的页面较早得到访问基于“语境图”的搜索策略需要借助已有的通用搜索引擎构建“语境图”, 而搜索引擎的检索结果并非一定代表真实的w eb 结构, 因而这种方式也具有局限性.
4　小结
通过以的分析, 各类搜索策略各有的优缺点, 网络爬虫搜索策略的研究对搜索引擎的应用与发展有着重要意义. 一种好的策略就是要在合理的时间限度内, 以较少的网络资源、存储资源和计算资源的消耗获得更多的与主题相关页面. 因而未来网络爬虫所使用的策略应该在提高链接价值预测的准确性、降低计算的时空复杂度, 以及增加网络爬虫的自适应性等方面有所发展, 有所突破.

    ① IP 地址搜索策略
先赋予爬虫一个起始的IP地址,然后根据IP地址递增的方式搜索本IP地址段后的每一个WWW地址中的文档，它完全不考虑各文档中指向其它Web 站点的超级链接地址。优点是搜索全面，能够发现那些没被其它文档引用的新文档的信息源；缺点是不适合大规模搜索。

　　② 深度优先搜索策略
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度 优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择 时，说明搜索已经结束。优点是能遍历一个Web 站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。

　　③ 宽度优先搜索策略
在宽度优先搜索中，先搜索完一个Web 页面中所有的超级链接，然后再继续搜索下一层, 直到底层为止。例如，一个HTML 文件中有三个超链,选择其中之一并处理相应的HTML文件，然后不再选择第二个HTML文件中的任何超链, 而是返回并选择第二个超链，处理相应的HTML文件，再返回，选择第三个超链并处理相应的HTML文件。一旦一层上的所有超链都己被选择过，就可以开始在 刚才处理过的HIML 文件中搜索其余的超链。这就保证了对浅层的首先处理。当遇到一个无穷尽的深层分支时，不会导致陷进WWW 中的深层文档中出现出不来的情况发生。宽度优先搜索策略还有一个优点,即它能在两个HTML文件之间找到最短路径。宽度优先搜索策略通常是实现爬虫的最佳 策略,因为它容易实现，而且具备大多数期望的功能。但是如果要遍历一个指定的站点或者深层嵌套的HTML文件集，用宽度优先搜索策略则需要花费比较长的时 间才能到达深层的HTML文件。综合考虑以上几种策略和国内信息导航系统搜索信息的特点，国内一般采用以宽度优先搜索策略为主、线性搜索策略为辅的搜索策 略。对于某些不被引用的或很少被引用的HTML文件，宽度优先搜索策略可能会遗漏这些孤立的信息源,可以用线性搜索策略作为它的补充。

　　④ 专业搜索引擎的爬虫策略
目前，专业搜索引擎网络爬虫通常采用“最好优先”原则访问WEB，即为快速、有效地获得更多的与主题相关的页面（简称“回报”），每次选择“最有价 值”的链接进行访问。由于链接包含于页面之中，而通常具有较高价值的页面包含的链接也具有较高的价值，因而对链接价值的评价有时也转换为对页面价值的评 价。

　　⑤ 爬虫的设计中应该注意的问题

　　第一个问题是URL地址的标准化：在WWW上，一个URL地址可以有多种表示方法，可以用IP地址表示，也可以用域名来表示。为了避免爬虫重复访问同 一地址。第二个问题是避免掉进网络陷阱：网络上的链接情况比较复杂，一些静态的网页可能构成闭环回路。为了避免爬虫在一条循环路线上反复抓取，在把URL 加入待搜索地址列表之前都要检查是否已在待搜索的地址列表中出现过。对于动态网页，爬虫应该忽略所有带参数的URL。第三个问题：对于拒绝访问的页面，爬 虫应该遵从“漫游拒绝访问规则”。