Spider的实现细节(转)

Spider的实现细节

    a. URL的组织和管理考虑到系统自身的资源和时间有限，Spider程序应尽可能的对链接进行筛选，以保证获取信息的质量和效率。冲ider程序对新URL 的选择往往与搜索引擎的类型、口标集合、能够处理信息的类型、资源的限制和是否支持Robots限制协议有关。概括为以卜几点: 访问过的和重复的URI排除 文件类型必须被系统处理，不能处理的URL排除 不在目标集合中的排除 被Rohots. txt限制的排除 URL排序也是减轻系统负担的重要手段之一。这就要求计算URL的重要性，如果评估新URI的重要性较高，则会冲掉旧的URL。无论任何情况下，对 Spider而言，一首先访问目标集合中的重要站点都是意义和重要的。但是一个页面的重要性的准确评估只能在分析其内容之后进行。可以根据一个页面链接数量的多少来评估此页面是否重要;或者对uRL地址进行解析其中的内容例如以“. com", ". edu. c;n”就较为重要一些;或，或者可以根据页而标题与当前的热点问题是否相近或相关来评定其页面的重要性。决定网站或页面的重要性的因素很多，也根据各个搜索引擎的侧重点不同而各异，最终的评估方法都依赖于该搜索引擎对于资源获取的要求来决定。影响Spider速度的一种重要因素是DNS查询，为此每个Spider都要维护一个自己的DNS缓冲。这样每个链接都处于不同的状态，包括:DNS查询、连接到主机、发送请求、得到响应。这些因素综合起来使得Spider变成一个非常复杂的系统。

b. Spider的遍历规则 页面的遍历主要有两种方式:深度遍历和广度遍历。深度遍历算法可以获得的信息较为集中，信息比较完整，但覆盖面就比较有限，广度遍历算法则刚好相反。

c. Spider实现中的主要问题 虽然Spider的功能很强，但也存在不少的问题:

(1)如果一组URL地址没有被组外URL所链接到，那么Spider就找不到它们。由于spi der不能更新过快(因为网络带宽是有限的，更新过快就会影响其他用户的正常使用)，难免有不能及时加入的新网站或新页面。

(2)spider程序在遍历Web时也存在危险，很可能遇到一个环链接而陷入死循环 中。简单的避免方法就是忽略已访问过的URL,或限制网站的遍历深度。

(3)Spider程序时大型搜索引擎中很脆弱的部分，因为它与很多的Wcb报务器、不同的域名服务器打交道，而这些服务完全在系统的控制之外。由于网络上包含了大量的垃圾信息，Spider很可能会收取这些垃圾信息。一个页而出现问题也很可能引至Spider程序中止、崩溃或其他不可预料的行为。囚此访问Internet的Spider程序应该设计得非常强壮，充分考虑各种可能遇到的情况，让Spider在遇到各种情况时可以采取相应的处理行为，而不至于获得一些垃圾信息或者直接就对程序本身造成危害。

Spider构架

发现、搜集网页信息需要有高性能的“网络蜘蛛”程序〔Spider〕去自动地在互联网中搜索信息。一个典型的网络蜘蛛工作的方式:查看一个页面，并从中找到相关信息，然后它再从该页面的所有链接中出发，继续寻找相关的信息，以此类推。网络蜘蛛在搜索引擎整体结构中的位置如下图所示: 初始化时，网络蜘蛛一般指向一个URL ( Uniform Resource Locator)池。在遍历Internet的过程中，按照深度优先或广度优先或其他启发式算法从URL池中取出若干URL进行处理，同时将未访问的 URL放入URL池中，这样处理直到URL池空为止。对Web文档的索引则根据文档的标题、首段落甚至整个页面内容进行，这取决于搜索服务的数据收集策略。

网络蜘蛛在漫游的过程中，根据页面的标题、头、链接等生成摘要放在索引数据库中。如果是全文搜索，还需要将整个页面的内容保存到本地数据库。网络蜘蛛为实现其快速地浏览整个互联网，通常在技术上采用抢先式多线程技术实现在网上搜索信息。通过抢先式多线程的使用，你能索引一个基于URL链接的 Web页面，启动一个新的线程跟随每个新的URL链接，索引一个新的URL起点。当然在服务器上所开的线程也不能无限膨胀，需要在服务器的正常运转和快速收集网页之间找一个平衡点。

在整个搜索引擎工作过程中，整个蜘蛛的数据入口是URL地址，数据出口是Web页仓库。Spide:程序发现URL链接以后，经过Stor处理模块，将我们所需要的网页数据存储在Web页仓库中，为以后的形成网页快照、网页分析提供基础数据。在Spider程序工作的过程中，发现新的链接，对该链接进行分析，形成新的搜索地址，作为下一次Spider程序的数据输入。这个过程的实现就是Spider程序的队列管理。

Spider程序的工作过程，简单来讲，就是不断发现新的链接，并对该链接对应的页面分析存储的工程。如下图所示，

一、索引器： 索引器的功能是理解搜索器所搜集的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。索引项有客观索引项和内容索引项两种: 客观项：与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行度(Link Popularity)等等; 内容索引项：是用来反映文档内容的，如关键词及其权重、短语、词、字等等。内容索引项可以分为单索引项和多索引项(或称短语索引项)两种。单索引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符(空格);对于中文等连续书写的语言，必须采用多索引项，进行词语的切分。索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现实时索引(Real-time Lndexing),否则不能够跟上信息量急剧增加的速度。索引算法对索引器的性能(如大规模峰值查询时的响应速度)有很大的影响。一个搜索引擎的有效性在很大程度取决于索引的质量。 由于汉文字符多，处理复杂，中文词的处理不容易。索引器中的中文分词技术： 一个分词系统=分词程序+分词词典 (1)最大匹配法MM (2)反向最大匹配法RMM (1)最佳匹配法OM (1)双向扫描法[百度的分词就采用了双向扫描法] 系统关键是：分词精度和分词速度

二、建立索引的方法： 为了加快检索速度，搜索引擎要对Snider程序搜集到的信,、建众倒排索引。 （1）全文索引和部分索引有些搜索引擎对于信息库中的贞面建立全文索引，有些只建立摘要部分索引或者每个段落前面部分的索引。还有些搜索引擎在建立索引时，要同时考虑超文本的不同标记所表示的含义，如粗体、大字体显示的东西往往比较重要。有些搜索引擎还在建立索引的过程中收集页面中的超链接。这些超链接反映了收集到的信息之间的空间结构。利用这些结果信息可以提高页面相关度判别时的准确度。 （2）是否过滤无用词由于网页中存在这许多无用(无实际意义)单词，例如“啊”、“的”等。这此词往往不能明确表达该网页信息，所以有些搜索引擎保存一个无用词汇表，在建立索引时将不对这些词汇建立索引。 （3）是否使用Meta标记中的信息网页中的Meta标记用来标注一些非常显示性的信息。有些网页将页面的关键词等信息放在其中。便于在建立索引的过程中提高这些词汇的相关度。（4）是否对图像标记中的替换文本(ALT text)或页面中的注解建立索引由于现有的搜索引擎对图像的检索技术还不太成熟，大多数搜索引擎不支持图像的检索。在超文木的结构页面中，图像标记中往往存放着图像的替换信息。这些信息说明了该图像对应的图像的基本信息。（5）是否支持词干提取技术

三、建立索引的过程： 分析过程对文档进行索引并存储到存储桶中排序过程

Spider处理流程

当一个URL被加入到等待队列中时Spider程序就会开始运行。只要等待队列中有一个网页或Spider程序正在处理一个网页，Spider程序就会继续它的工作。当等待队列为空并且当前没有处理任何网页，Spider程序就会停止它的工作。

Spider程序实现初探

Spider程序是从网上下载Web页面再对其进行处理，为了提高效率，很显然要采用多线程的方法，几个Spider线程同时并行工作，访问不同的链接。构造Spider程序有两种方式。第一种是将它设计为递归程序，第二种是将它编写成非递归的程序。递归是在一个方法中调用它本身的程序设计技术。当需要重复做同样的基本仟务或在处理先前任务时可展现将来的任务信息时，递归是相当实用的。例如下面的代码:

void RecursiveSpider?(String url) {

download URL……

parse URL……

while found each URL

call RecursiveSpider?(found URL) ……

process the page just downloaded……

} 这段代码查看单独的一个Web页的任务放在一个RecursiveSpide?:方法中。在此，调用RecursiveSiper?方法来访问URL.。当它发现链接时，该方法调用它自己。递归方法在访问很少的网页时，可以使用。因为当一个递归程序运行时要把每次递归压入堆栈(堆栈是个程序结构，每次调用一个方法时，将返回地址存入其中)。如果递归程序要运行很多次，堆栈会变得非常大，它可能会耗尽整个堆栈内存而导致程序中止。递归还有个问题是多线程和递归是不兼容的，因为在这一过程中每一个线程都是自己的堆栈。当一个方法调用它自身时，它们需要使用同一个堆栈。这就是说递归的Spider程序不能使用多线程。 非递归程序不调用自身，而是采用队列的方法。队列就是排队，要得到程序的处理就必须在队列中排队等待。我们在构造造Spider时就采用该方式。使用非递归的方法时，给定Spider程序一个要访问的页面，它会将其加入到要访问的站点的队列中去。当Spider发现新的链接时，也会将它们加入到该队列中。 Spider程序会顺序处理队列中的每一个网页。 实际在Spider程序中使用了四个队列; 在Spider程序的构造过程中，有两种方法用于访问队列的管理。一种方法就是基于内存的队列管理。

第二种方法就是基于SQL的队列管理。基于SQL的队列和基于内存的队列都是有效的，在校园网上做实验的结果表明，在系统运行过程中间，如果Spider 的访问任务随着网页数量增加，基于内存的Spider程序效率会下降。因而，选择基于SQL的队列管理方案来构造本Spider程序。

等待队列: 在这个队列中，URL.等待被Spider程序处理。新发现的URL被加入到该处理队列:当Spider开始处理URL时，它们被传送到这一队列。当一个 URL被处理后它被移送到错误队列或完成队列: 错误队列: 如果下载某一页面时出现错误，它的URL将被加入该队列。该队列的URL不会再移动到其他队列。被列入该队列的URL将不再会被Spider程序处理。

完成队列: 如果页面的下载没有出现任何错误，则该页面将会被加入完成队列。加入该队列的URL不会再移动到其他队列。同一时刻一个URL只能在一个队列中。其实通俗的讲就是该URL处于什么状态，URL 状态的变化过程就是程序处理URL的过程。下图说明的一个URL状态的变化过程。 Spider程序会遇到三种连接：内部连接外部连接其他连接一个示例Spider类：