Web检索工具WebCrawler研究的主要问题研究方法

　　Web检索工具WebCrawler研究的主要问题研究方法

　　随着互联网的兴起和发展，人们获取信息的方式已经从传统的方式逐渐被互联网取代。起初，人们主要是通过浏览网页来获取自己需要的信息，但是随着网络的不断扩大，通过这种方式找到自己需要的信息变得越来越困难。如今，大多数人严重依赖搜索引擎来帮助他们获取有用的信息。因此，作为一种典型的Web信息获取技术，搜索引擎技术直接影响着人们获取信息的质量。

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

　　1 网络爬虫的工作原理

　　网络爬虫来自Spider的释义。同义词有Crawler、robots、bots、wanderer等，网络爬虫有广义和狭义之分。狭义上的软件程序是使用标准的http协议，基于超链接和Web文档检索方法来遍历万维网信息空间的软件程序；广义的指所有可以使用http协议检索Web文档的软件程序。软件称为网络爬虫。

　　Web crawler 是一个强大的程序，可以自动提取网页。它从万维网下载网页以供搜索引擎使用。它是搜索引擎的重要组成部分。它通过请求站点上的 HTML 文档来访问站点。它遍历 Web 空间，不断地从一个站点移动到另一个站点，自动构建索引并将其添加到网页数据库中。当网络爬虫进入一个超文本时，它利用HTML语言的标记结构搜索信息并获取指向其他超文本的URL地址。它可以在不依赖用户干预的情况下实现网络上的自动“爬行”和搜索。网络爬虫在搜索时通常会采用某些搜索策略。

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

　　搜索引擎使用的第一代网络爬虫主要基于传统的图算法，例如广度优先或深度优先算法来索引整个网络。核心 URL 集用作*敏*感*词*集。这种算法是递归跟踪到其他页面的超链接，通常不考虑页面的内容，因为最终的目标是这种跟踪可以覆盖整个Web。这种策略一般用在通用搜索引擎中，因为通用搜索引擎获取的页面越多越好，没有具体要求。如图1所示：

　　2.1 广度优先搜索算法

　　广度优先搜索算法（也称为广度优先搜索）是一种简单的图搜索算法。该算法也是许多重要图算法的原型。 Dijktra 单源极短路径算法和 Prim 极小生成树算法都采用了与广度优先搜索类似的思想。广度优先搜索算法沿树的宽度遍历树的节点，如果找到目标则停止算法。该算法的设计和实现比较简单，属于盲搜索。目前，为了覆盖尽可能多的网页，一般采用广度优先搜索的方法。也有许多研究将广度优先搜索策略应用于聚焦爬虫。基本思想是，距离初始 URL 一定链接距离内的网页具有很高的主题相关性概率。另一种方法是将广度优先搜索与网页过滤技术相结合。首先使用广度优先策略抓取网页，然后过滤掉不相关的网页。这些方法的缺点是随着爬取的网页数量的增加，会出现大量不相关的网页。网页会被下载和过滤，算法效率会降低。

　　2. 2Depth First Search

　　深度优先搜索遵循的搜索策略是尽可能“深入”地搜索图像。在深度优先搜索中，对于一个非常新发现的顶点，如果它有一条未检测到的边从该点开始，它将沿着这条边继续。当探索了节点 v 的所有边时，搜索将返回到找到节点 v 边的起始节点。这个过程一直持续到所有从源节点可达的节点都被找到为止。如果还有未发现的节点，则选择其中一个作为源节点，重复上述过程。重复整个过程，直到找到所有节点。深度优先会导致爬虫陷入（t rapped））问题，所以既不完整也不优秀。

　　3焦点搜索策略

　　基于第一代网络爬虫的搜索引擎抓取的网页一般在1,000,000个网页以下，很少重新采集网页和刷新索引。而且检索速度很慢，一般要等10s甚至更长时间。随着网页信息的指数级增长和动态变化，这些通用搜索引擎的局限性越来越大。随着科技的发展，定向抓取相关网络资源的Focused crawler应运而生。

　　专注于爬虫的爬虫策略只挑出特定主题的页面，按照“好优先原则”进行访问，快速有效地获取更多主题相关的页面，主要通过内容和链接结构Web 以指导进一步的页面抓取。图 2 展示了一个典型的以应用为中心的策略爬虫的爬虫规则。

　　焦点爬虫会对下载的页面进行评分，然后根据评分进行排序。稍后将其插入队列。通过分析弹出队列中的第一页，将执行良好的下一次搜索。该策略确保爬虫可以优先考虑可能链接到目标页面的页面。决定一个网络爬虫的搜索策略的关键是如何评估链接值，即链接值的计算方法。不同的价值评估方法计算链接的价值，链接的“重要性”也不同，这决定了不同的搜索策略。因为链接是收录在页面中的，通常价值较高的页面收录的链接价值也较高，所以有时会将链接价值的评估转换为页面价值的评估。这种策略通常用于专业搜索引擎中，因为这种搜索引擎只关心特定主题的页面。

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

　　基于内容评价的搜索策略主要是根据话题（如关键词、话题相关文档）与链接文本的相似度来评价链接的价值，并确定其搜索策略：链接文字是指链接周围区域的描述文字和链接网址上的文字信息，相似度的评价通常采用以下公式：

　　其中di是新文本的特征向量，dj是第j个类别的中心向量，m是特征向量的维度，wk是向量的第k维度。

　　由于网页不同于传统的文本，它是一种收录大量结构化信息的半结构化文档。网页不是单独存在的。页面中的链接表示页面之间的关系，因此有学者提出了一种基于链接结构的链接价值评估方法。

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

　　基于链接结构评估的搜索策略是一种通过分析网页之间的相互引用关系来确定链接重要性的方法，然后确定链接访问的顺序。人们普遍认为，具有更多传入或传出链接的页*敏*感*词*有更高的价值。其中PageRank和Hits是代表性算法。

　　3. 2. 1 PageRank 算法

　　基于链接评价的搜索引擎的优秀代表是谷歌。其独创的“链接评价系统”（PageRank算法）是基于这样一种认识，即一个网页的重要性取决于与其他网页的链接数，尤其是被认为“重要”的网页链接数。 PageRank算法最初用于谷歌搜索引擎信息检索中查询结果的排序过程。近年来，它被应用于网络爬虫来评估链接的重要性。 PageRank算法中页面的值通常用页面的PageRank值表示，如果

　　假设页面p的PageRank值为PR(p)，那么PR(p)的计算公式如下：

　　其中 T 是计算中的总页数，C

　　3.2. 2H ITS 算法

　　HITS 方法定义了两个重要概念：权威和中心。权威性表示一个权威页面被其他页面引用的次数，即权威页面的入度值。被引用的网页数量越多，该网页的权威值越大； Hub表示一个网页指向的其他页面的数量，即该页面的out-of-degree值。网页的出度值越高，Hub 值就越高。因为Hub值高的页面通常会提供权威页面的链接，所以起到了隐式解释某个主题页面权威的作用。

　　HITS（Hyperlink-Induced Topic Search）算法是一种使用 Hub.Authority 方法的搜索方法。权限表示其他页面对页面的引用次数，即该页面的入度值。 Hub表示一个网页指向的其他页面的数量，即该页面的出度值。算法如下：基于关键字匹配将查询q提交给传统搜索引擎。搜索引擎返回大量网页，其中的前n个网页作为根集，用S表示。通过添加S引用的网页和引用S的网页到S，将S扩展为更大的集合T . 以T中的Hub网页为顶点集V l，权威网页顶点集V 2，以及V 1中网页到V 2中网页的超链接为边集E，二部有向图 SG = (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值或权威和Hub权重，计算复杂度随着页面数的增长呈指数增长，链接。

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

　　最近对Web信息资源分布的研究表明，许多同类型的网站在构造方式上有相似之处，相同主题的网页在组织方式上也有相似之处。一些学者考虑巩固他们的学习。在引入网络爬虫的训练过程中，从这些相似性中获得了一些“经验”，而这些经验信息在搜索远离相关页面集的地方时往往可以获得更好的回报，而前两种策略在这种情况下是容易迷路。在整合学习模型中，网络爬虫访问多个不相关的页面后能够获得的与主题相关的页面称为未来回报，未来回报的预测值称为未来回报值，用Q值表示。该方法的核心是学习如何计算链接的Q值，并根据未来的返回值确定正确的搜索方向。目前这类搜索策略的不足在于学习效率低，训练过程中用户负担重。

　　3. 4 基于上下文映射的聚焦搜索

　　基于整合学习的网络爬虫可以通过计算链接的Q值来确定搜索方向，但无法估计到目标页面的距离。为此，Diligen 等人。提出了一种基于“上下文地图”的搜索策略，通过构建典型页面的网络“上下文地图”来估计与目标页面的距离，越近的页面越早被访问。基于“语境图”的搜索策略需要借助现有的通用搜索引擎构建“语境图”，而搜索引擎的搜索结果并不一定代表真实的网页结构，所以这种方法也有局限性。

　　4 总结

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

　　seo点点引自刘诗涛的搜索引擎爬取策略，引自seo点点新浪博客