网络蜘蛛基本原理

网络蜘蛛基本原理

关键字: 网络蜘蛛 爬虫 spider 网络蜘蛛即Web Spider，是一个很形象的名字。把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从 网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网 站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。

　　对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之 四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的问题，如 果按照每个页面的平均大小为20K计算（包含图片），100亿网页的容量是100×2000G字节，即使能够存储，下载也存在问题（按照一台机器每秒下载 20K计算，需要340台机器不停的下载一年时间，才能把所有网页下载完毕）。同时，由于数据量太大，在提供搜索时也会有效率方面的影响。因此，许多搜索 引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。

　　在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先。

   广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方式，因为这个 方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页， 继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。两种策略的区别，下图的说明会更加明确。

　　由于不可能抓取所有的网页，有些网络蜘蛛对一些不太重要的网站，设置了访问的层数。例如，在上图中，A为起始网页，属于0层，B、C、D、 E、F属于第1层，G、H属于第2层， I属于第3层。如果网络蜘蛛设置的访问层数为2的话，网页I是不会被访问到的。这也让有些网站上一部分网页能够在搜索引擎上搜索到，另外一部分不能被搜索 到。对于网站设计者来说，扁平化的网站结构设计有助于搜索引擎抓取其更多的网页。

　　网络蜘蛛在访问网站网页的时候，经常会遇到加密数据和网页权限的问题，有些网页是需要会员权限才能访问。当然，网站的所有者可以通过协议让网 络蜘蛛不去抓取（下小节会介绍），但对于一些出售报告的网站，他们希望搜索引擎能搜索到他们的报告，但又不能完全**的让搜索者查看，这样就需要给网络蜘 蛛提供相应的用户名和密码。网络蜘蛛可以通过所给的权限对这些网页进行网页抓取，从而提供搜索。而当搜索者点击查看该网页的时候，同样需要搜索者提供相应 的权限验证。

　网站与网络蜘蛛

　　网络蜘蛛需要抓取网页，不同于一般的访问，如果控制不好，则会引起网站服务器负担过重。去年4月，淘宝 http://www.taobao.com）就因为雅虎搜索引擎的网络蜘蛛抓取其数据引起淘宝网服务器的不稳定。网站是否就无法和网络蜘蛛交流呢？其实 不然，有多种方法可以让网站和网络蜘蛛进行交流。一方面让网站管理员了解网络蜘蛛都来自哪儿，做了些什么，另一方面也告诉网络蜘蛛哪些网页不应该抓取，哪 些网页应该更新。

　　每个网络蜘蛛都有自己的名字，在抓取网页的时候，都会向网站标明自己的身份。网络蜘蛛在抓取网页的时候会发送一个请求，这个请求中就有一个字 段为User－ agent，用于标识此网络蜘蛛的身份。例如Google网络蜘蛛的标识为GoogleBot，Baidu网络蜘蛛的标识为BaiDuSpider， Yahoo网络蜘蛛的标识为Inktomi Slurp。如果在网站上有访问日志记录，网站管理员就能知道，哪些搜索引擎的网络蜘蛛过来过，什么时候过来的，以及读了多少数据等等。如果网站管理员发 现某个蜘蛛有问题，就通过其标识来和其所有者联系。下面是博客中http://www.blogchina.com）2004年5月15日的搜索引擎访问 日志：

　　网络蜘蛛进入一个网站，一般会访问一个特殊的文本文件Robots.txt，这个文件一般放在网站服务器的根目录 下，http://www.blogchina.com/robots.txt。网站管理员可以通过robots.txt来定义哪些目录网络蜘蛛不能访 问，或者哪些目录对于某些特定的网络蜘蛛不能访问。例如有些网站的可执行文件目录和临时文件目录不希望被搜索引擎搜索到，那么网站管理员就可以把这些目录 定义为拒绝访问目录。Robots.txt语法很简单，例如如果对目录没有任何限制，可以用以下两行来描述：
　　User-agent: *
　　Disallow:

　　当然，Robots.txt只是一个协议，如果网络蜘蛛的设计者不遵循这个协议，网站管理员也无法阻止网络蜘蛛对于某些页面的访问，但一般的网络蜘蛛都会遵循这些协议，而且网站管理员还可以通过其它方式来拒绝网络蜘蛛对某些网页的抓取。

　　网络蜘蛛在下载网页的时候，会去识别网页的HTML代码，在其代码的部分，会有META标识。通过这些标识，可以告诉网络蜘蛛本网页是否需要被抓取，还可以告诉网络蜘蛛本网页中的链接是否需要被继续跟踪。例如：表示本网页不需要被抓取，但是网页内的链接需要被跟踪。

　　

　　现在一般的网站都希望搜索引擎能更全面的抓取自己网站的网页，因为这样可以让更多的访问者能通过搜索引擎找到此网站。为了让本网站的网页更全 面被抓取到，网站管理员可以建立一个网站地图，即Site Map。许多网络蜘蛛会把sitemap.htm文件作为一个网站网页爬取的入口，网站管理员可以把网站内部所有网页的链接放在这个文件里面，那么网络蜘 蛛可以很方便的把整个网站抓取下来，避免遗漏某些网页，也会减小对网站服务器的负担。

　　内容提取

　　搜索引擎建立网页索引，处理的对象是文本文件。对于网络蜘蛛来说，抓取下来网页包括各种格式，包括html、图片、doc、pdf、多媒体、 动态网页及其它格式等。这些文件抓取下来后，需要把这些文件中的文本信息提取出来。准确提取这些文档的信息，一方面对搜索引擎的搜索准确性有重要作用，另 一方面对于网络蜘蛛正确跟踪其它链接有一定影响。

　　对于doc、pdf等文档，这种由专业厂商提供的软件生成的文档，厂商都会提供相应的文本提取接口。网络蜘蛛只需要调用这些插件的接口，就可以轻松的提取文档中的文本信息和文件其它相关的信息。

　　HTML等文档不一样，HTML有一套自己的语法，通过不同的命令标识符来表示不同的字体、颜色、位置等版式，如：、、等，提取文本信息时需 要把这些标识符都过滤掉。过滤标识符并非难事，因为这些标识符都有一定的规则，只要按照不同的标识符取得相应的信息即可。但在识别这些信息的时候，需要同 步记录许多版式信息，例如文字的字体大小、是否是标题、是否是加粗显示、是否是页面的关键词等，这些信息有助于计算单词在网页中的重要程度。同时，对于 HTML网页来说，除了标题和正文以外，会有许多广告链接以及公共的频道链接，这些链接和文本正文一点关系也没有，在提取网页内容的时候，也需要过滤这些 无用的链接。例如某个网站有“产品介绍”频道，因为导航条在网站内每个网页都有，若不过滤导航条链接，在搜索“产品介绍”的时候，则网站内每个网页都会搜 索到，无疑会带来大量垃圾信息。过滤这些无效链接需要统计大量的网页结构规律，抽取一些共性，统一过滤；对于一些重要而结果特殊的网站，还需要个别处理。 这就需要网络蜘蛛的设计有一定的扩展性。

　　对于多媒体、图片等文件，一般是通过链接的锚文本（即，链接文本）和相关的文件注释来判断这些文件的内容。例如有一个链接文字为“张曼玉照片 ”，其链接指向一张bmp格式的图片，那么网络蜘蛛就知道这张图片的内容是“张曼玉的照片”。这样，在搜索“张曼玉”和“照片”的时候都能让搜索引擎找到 这张图片。另外，许多多媒体文件中有文件属性，考虑这些属性也可以更好的了解文件的内容。

　　动态网页一直是网络蜘蛛面临的难题。所谓动态网页，是相对于静态网页而言，是由程序自动生成的页面，这样的好处是可以快速统一更改网页风格， 也可以减少网页所占服务器的空间，但同样给网络蜘蛛的抓取带来一些麻烦。由于开发语言不断的增多，动态网页的类型也越来越多，如：asp、jsp、php 等。这些类型的网页对于网络蜘蛛来说，可能还稍微容易一些。网络蜘蛛比较难于处理的是一些脚本语言（如VBScript和javascript）生成的网 页，如果要完善的处理好这些网页，网络蜘蛛需要有自己的脚本解释程序。对于许多数据是放在数据库的网站，需要通过本网站的数据库搜索才能获得信息，这些给 网络蜘蛛的抓取带来很大的困难。对于这类网站，如果网站设计者希望这些数据能被搜索引擎搜索，则需要提供一种可以遍历整个数据库内容的方法。

　　对于网页内容的提取，一直是网络蜘蛛中重要的技术。整个系统一般采用插件的形式，通过一个插件管理服务程序，遇到不同格式的网页采用不同的插件处理。这种方式的好处在于扩充性好，以后每发现一种新的类型，就可以把其处理方式做成一个插件补充到插件管理服务程序之中。

　　更新周期

　　由于网站的内容经常在变化，因此网络蜘蛛也需不断的更新其抓取网页的内容，这就需要网络蜘蛛按照一定的周期去扫描网站，查看哪些页面是需要更新的页面，哪些页面是新增页面，哪些页面是已经过期的死链接。

　　搜索引擎的更新周期对搜索引擎搜索的查全率有很大影响。如果更新周期太长，则总会有一部分新生成的网页搜索不到；周期过短，技术实现会有一定 难度，而且会对带宽、服务器的资源都有浪费。搜索引擎的网络蜘蛛并不是所有的网站都采用同一个周期进行更新，对于一些重要的更新量大的网站，更新的周期 短，如有些新闻网站，几个小时就更新一次；相反对于一些不重要的网站，更新的周期就长，可能一两个月才更新一次。

　　一般来说，网络蜘蛛在更新网站内容的时候，不用把网站网页重新抓取一遍，对于大部分的网页，只需要判断网页的属性（主要是日期），把得到的属性和上次抓取的属性相比较，如果一样则不用更新。


            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类：



            一个简单的Spider例子 （JAVA）

 

 

import java.awt.*;

import java.net.*;
import java.io.*;
import java.lang.*;
import java.util.*;


class node{
  private Object data;
  private node next;
  private node prev;
  public node(Object o){
data = o;
prev = next = null;
  }
  public String toString(){
if(next!=null)return data.toString() + "\n"+ next.toString();
return data.toString();
  }
  public node getNext(){return next;}
  public void setNext(node n){next = n;}
  public node getPrev(){return prev;}
  public void setPrev(node n){prev = n;}
  public Object getData(){return data;}
}

class linkedlist{
  node head;
  node tail;
  public linkedlist(){
tail = head = null;
  }
  public String toString(){
if(head==null)return "Empty list";
return head.toString();
  }
  public void insert(Object o){
if(tail==null){
  head = tail = new node(o);
}else{
  node nn = new node(o);
  tail.setNext(nn);
  tail=nn;
}
  }
  public boolean contains(Object o){
for(node n = head;n!=null;n=n.getNext()){
  if(o.equals(n.getData()))return true;
}
return false;
  }
  public Object pop(){
if(head==null)return null;
Object ret = head.getData();
head = head.getNext();
if(head==null)tail = null;
return ret;
  }
  public boolean isEmpty(){
return head==null;
  }
}


class list{
protected node tail;
protected node ptr;
private boolean stop;
public list(){
ptr=tail=null;
stop=false;
}
public boolean isEmpty(){return tail==null;}
public void reset(){
stop=false;
ptr=tail;
}
public String toString(){
if(tail==null)return "Empty list";
String ret="";
for(node n = tail.getNext();n!=tail;n=n.getNext())ret+=n.getData().toString()+"\n";
ret+=tail.getData().toString();
return ret;
}
public Object get(){
if(ptr==null)return null;
ptr = ptr.getNext();
if(ptr==tail.getNext()){
  if(stop)return null;
  stop=true;
  return tail.getNext().getData();
}
return ptr.getData();
}
public void insert(Object o, boolean attail){
node nn = new node(o);
if(tail==null){
  nn.setNext(nn);
  nn.setPrev(nn);
  ptr=tail=nn;
  return;
}
if(attail){
tail.getNext().setPrev(nn);
  nn.setNext(tail.getNext());
  tail.setNext(nn);
  nn.setPrev(tail);
  tail=nn;
}else{
  nn.setNext(tail.getNext());
  nn.setPrev(tail);
  tail.setNext(nn);
  nn.getNext().setPrev(nn);
}
}
public void insert(Object o){}
}

class stack extends list{
public stack(){super();}
public void insert(Object o){insert(o, false);}
}
class queue extends list{
public queue(){super();}
public void insert(Object o){insert(o, true);}
public String peek(){
  if(tail==null)return "";
  return tail.getNext().getData().toString();
}
public Object pop(){
if(tail==null)return null;
Object ret = tail.getNext().getData();
if(tail.getNext()==tail){
  tail=ptr=null;
}else{
  if(tail.getNext()==ptr)ptr=ptr.getNext();
  tail.setNext(tail.getNext().getNext());
}
return ret;
}
}


class hashtable{
  private Vector table;
  private int size;
  public hashtable(){
size = 991;
table = new Vector();
for(int i=0;i<size;i++){
  table.add(new linkedlist());
}
  }
  public void insert(Object o){
int index = o.hashCode();
index = index % size;
if(index<0)index+=size;
linkedlist ol = (linkedlist)table.get(index);
ol.insert(o);
  }
  public boolean contains(Object o){
int index = o.hashCode();
index = index % size;
if(index<0)index+=size;
return ((linkedlist)(table.get(index))).contains(o);
  }
  public String toString(){
String ret ="";
for(int i=0;i<size;i++){
  if(!((linkedlist)(table.get(i))).isEmpty()){
ret+="\n";
ret+=table.get(i).toString();
  }
}
return ret;
  }
}

class spider implements Runnable{
public queue todo;
public stack done;
public stack errors;
public stack omittions;
private hashtable allsites;
private String last="";
  int maxsites;
  int visitedsites;
  int TIMEOUT;
  String base;
  String []badEndings2 = {"ps", "gz"};
  String []badEndings3 = {"pdf", "txt", "zip", "jpg", "mpg", "gif", "mov", "tut", "req", "abs", "swf", "tex", "dvi", "bin", "exe", "rpm"};
  String []badEndings4 = {"jpeg", "mpeg"};

  public spider(String starturl, int max, String b){
TIMEOUT = 5000;
base = b;
allsites = new hashtable();
todo = new queue();
done = new stack();
errors = new stack();
omittions = new stack();
try{
  URL u = new URL(starturl);
  todo.insert(u);
}catch(Exception e){
  System.out.println(e);
  errors.insert("bad starting url "+starturl+", "+e.toString());
}
maxsites = max;
visitedsites = 0;
  }

  /*
  * how many millisec to wait for each page
  */
  public void setTimer(int amount){
TIMEOUT = amount;
  }

  /*
  * strips the '#' anchor off a url
  */
  private URL stripRef(URL u){
try{
  return new URL(u.getProtocol(), u.getHost(), u.getPort(), u.getFile());
}catch(Exception e){return u;}
  }

  /*
  * adds a url for future processing
  */
  public void addSite(URL toadd){
if(null!=toadd.getRef())toadd = stripRef(toadd);
if(!allsites.contains(toadd)){
  allsites.insert(toadd);
  if(!toadd.toString().startsWith(base)){
omittions.insert("foreign URL: "+toadd.toString());
return;
  }
  if(!toadd.toString().startsWith("http") && !toadd.toString().startsWith("HTTP")){
omittions.insert("ignoring URL: "+toadd.toString());
return;
  }

  String s = toadd.getFile();
  String last="";
  String []comp={};
  if(s.charAt(s.length()-3)=='.'){
last = s.substring(s.length()-2);
comp = badEndings2;
  }else if(s.charAt(s.length()-4)=='.'){
last = s.substring(s.length()-3);
comp = badEndings3;
  }else if(s.charAt(s.length()-5)=='.'){
last = s.substring(s.length()-4);
comp = badEndings4;
  }
  for(int i=0;i<comp.length;i++){
if(last.equalsIgnoreCase(comp[i])){//loop through all bad extensions
    omittions.insert("ignoring URL: "+toadd.toString());
    return;
}
  }
  
  todo.insert(toadd);
}
  }

  /*
  * true if there are pending urls and the maximum hasn't been reached
  */
  public boolean hasMore(){
return !todo.isEmpty() && visitedsites<maxsites;
  }

  /*
  * returns the next site, works like enumeration, will return new values each time
  */
  private URL getNextSite(){
last = todo.peek();
visitedsites++;
return (URL)todo.pop();
  }

  /*
  * Just to see what we are doing now...
  */
  public String getCurrent(){
return last;
  }

  /*
  * process the next site
  */
  public void doNextSite(){
URL current = getNextSite();
if(current==null)return;
try{
  //System.err.println("Processing #"+visitedsites+": "+current);
  parse(current);
  done.insert(current);
}
catch(Exception e){
  errors.insert("Bad site: "+current.toString()+", "+e.toString());
}
  }

  public void run(){
while(hasMore())doNextSite();
  }

  /*
  * to print out the internal data structures
  */
  public String toString(){return getCompleted()+getErrors();}
  private String getErrors(){
if(errors.isEmpty())return "No errors\n";
else return "Errors:\n"+errors.toString()+"\nEnd of errors\n";
  }
  private String getCompleted(){
return "Completed Sites:\n"+done.toString()+"\nEnd of completed sites\n";
  }

  /*
  * Parses a web page at (site) and adds all the urls it sees
  */
  private void parse(URL site) throws Exception{
String source=getText(site);
String title=getTitle(source);
if(title.indexOf("404")!=-1 ||
  title.indexOf("Error")!=-1 ||
  title.indexOf("Not Found")!=-1){
  throw new Exception (("404, Not Found: "+site));
}
int loc, beg;
boolean hasLT=false;
boolean hasSp=false;
boolean hasF=false;
boolean hasR=false;
boolean hasA=false;
boolean hasM=false;
boolean hasE=false;
for(loc=0;loc<source.length();loc++){
  char c = source.charAt(loc);
  if(!hasLT){
hasLT = (c=='<');
  }

  //search for "<a "
  else if(hasLT && !hasA && !hasF){
if(c=='a' || c=='A')hasA=true;
else if(c=='f' || c=='F')hasF=true;
else hasLT=false;
  }else if(hasLT && hasA && !hasF && !hasSp){
if(c==' ' || c=='\t' || c=='\n')hasSp=true;
else hasLT = hasA = false;
  }

  //search for "<frame "
  else if(hasLT && hasF && !hasA && !hasR){
if(c=='r' || c=='R')hasR=true;
else hasLT = hasF = false;
  }else if(hasLT && hasF && hasR && !hasA){
if(c=='a' || c=='A')hasA=true;
else hasLT = hasF = hasR = false;
  }else if(hasLT && hasF && hasR && hasA && !hasM){
if(c=='m' || c=='M')hasM=true;
else hasLT = hasF = hasR = hasA = false;
  }else if(hasLT && hasF && hasR && hasA && hasM && !hasE){
if(c=='e' || c=='E')hasE=true;
else hasLT = hasF = hasR = hasA = hasM = false;
  }else if(hasLT && hasF && hasR && hasA && hasM && hasE && !hasSp){
if(c==' ' || c=='\t' || c=='\n')hasSp=true;
else hasLT = hasF = hasR = hasA = hasM = hasE = false;
  }
  
  //found "<frame "
  else if(hasLT && hasF && hasR && hasA && hasM && hasE && hasSp){
hasLT = hasF = hasR = hasA = hasM = hasE = hasSp = false;
beg = loc;
loc = source.indexOf(">", loc);
if(loc==-1){
    errors.insert("malformed frame at "+site.toString());
    loc = beg;
}
else{
    try{
  parseFrame(site, source.substring(beg, loc));
    }
    catch(Exception e){
  errors.insert("while parsing "+site.toString()+", error parsing frame: "+e.toString());
    }
}
  }

  //found "<a "
  else if(hasLT && hasA && hasSp && !hasF){
hasLT = hasA = hasSp = false;
beg = loc;
loc = source.indexOf(">", loc);
if(loc==-1){
    errors.insert("malformed linked at "+site.toString());
    loc = beg;
}
else{
    try{
  parseLink(site, source.substring(beg, loc));
    }
    catch(Exception e){
  errors.insert("while parsing "+site.toString()+", error parsing link: "+e.toString());
    }
}
  }
}
  }
  
  /*
  * parses a frame
  */
  private void parseFrame(URL at_page, String s) throws Exception{
int beg=s.indexOf("src");
if(beg==-1)beg=s.indexOf("SRC");
if(beg==-1)return;//doesn't have a src, ignore
beg = s.indexOf("=", beg);
if(beg==-1)throw new Exception("while parsing "+at_page.toString()+", bad frame, missing \'=\' after src: "+s);
int start = beg;
for(;beg<s.length();beg++){
  if(s.charAt(beg)=='\'')break;
  if(s.charAt(beg)=='\"')break;
}
int end=beg+1;
for(;end<s.length();end++){
  if(s.charAt(beg)==s.charAt(end))break;
}
beg++;
if(beg>=end){//missing quotes... just take the first token after "src="
  for(beg=start+1;beg<s.length() && (s.charAt(beg)==' ');beg++){}
  for(end=beg+1;end<s.length() && (s.charAt(beg)!=' ') && (s.charAt(beg)!='>');end++){}
}

if(beg>=end){
  errors.insert("while parsing "+at_page.toString()+", bad frame: "+s);
  return;
}

String linkto=s.substring(beg,end);
if(linkto.startsWith("mailto:")||linkto.startsWith("Mailto:"))return;
if(linkto.startsWith("javascript:")||linkto.startsWith("Javascript:"))return;
if(linkto.startsWith("news:")||linkto.startsWith("Javascript:"))return;
try{
  addSite(new URL(at_page, linkto));
  return;
}catch(Exception e1){}
try{
  addSite(new URL(linkto));
  return;
}catch(Exception e2){}
try{
  URL cp = new URL(at_page.toString()+"/index.html");
  System.out.println("attemping to use "+cp);
  addSite(new URL(cp, linkto));
  return;
}catch(Exception e3){}
errors.insert("while parsing "+at_page.toString()+", bad frame: "+linkto+", formed from: "+s);
  }

  /*
  * given a link at a URL, will parse it and add it to the list of sites to do
  */
  private void parseLink(URL at_page, String s) throws Exception{
//System.out.println("parsing link "+s);
int beg=s.indexOf("href");
if(beg==-1)beg=s.indexOf("HREF");
if(beg==-1)return;//doesn't have a href, must be an anchor
beg = s.indexOf("=", beg);
if(beg==-1)throw new Exception("while parsing "+at_page.toString()+", bad link, missing \'=\' after href: "+s);
int start = beg;
for(;beg<s.length();beg++){
  if(s.charAt(beg)=='\'')break;
  if(s.charAt(beg)=='\"')break;
}
int end=beg+1;
for(;end<s.length();end++){
  if(s.charAt(beg)==s.charAt(end))break;
}
beg++;
if(beg>=end){//missing quotes... just take the first token after "href="
  for(beg=start+1;beg<s.length() && (s.charAt(beg)==' ');beg++){}
  for(end=beg+1;end<s.length() && (s.charAt(beg)!=' ') && (s.charAt(beg)!='>');end++){}
}

if(beg>=end){
  errors.insert("while parsing "+at_page.toString()+", bad href: "+s);
  return;
}

String linkto=s.substring(beg,end);
if(linkto.startsWith("mailto:")||linkto.startsWith("Mailto:"))return;
if(linkto.startsWith("javascript:")||linkto.startsWith("Javascript:"))return;
if(linkto.startsWith("news:")||linkto.startsWith("Javascript:"))return;

try{
  addSite(new URL(at_page, linkto));
  return;
}catch(Exception e1){}
try{
  addSite(new URL(linkto));
  return;
}catch(Exception e2){}
try{
  addSite(new URL(new URL(at_page.toString()+"/index.html"), linkto));
  return;
}catch(Exception e3){}
errors.insert("while parsing "+at_page.toString()+", bad link: "+linkto+", formed from: "+s);
  }

  /*
  * gets the title of a web page with content s
  */
  private String getTitle(String s){
try{
  int beg=s.indexOf("<title>");
  if(beg==-1)beg=s.indexOf("<TITLE>");
  int end=s.indexOf("</title>");
  if(end==-1)end=s.indexOf("</TITLE>");
  return s.substring(beg,end);
}
catch(Exception e){return "";}
  }

  /*
  * gets the text of a web page, times out after 10s
  */
  private String getText(URL site) throws Exception
  {
urlReader u = new urlReader(site);
Thread t = new Thread(u);
t.setDaemon(true);
t.start();
t.join(TIMEOUT);
String ret = u.poll();
if(ret==null){
throw new Exception("connection timed out");
}else if(ret.equals("Not html")){
throw new Exception("Not an HTML document");
}
return ret;
  }

  /*
  * returns how many sites have been visited so far
  */
  public int Visited(){return visitedsites;}
}

class urlReader implements Runnable{
  URL site;
  String s;
  public urlReader(URL u){
site = u;
s=null;
  }
  public void run(){
try{
  String ret=new String();
  URLConnection u = site.openConnection();
  String type = u.getContentType();
  if(type.indexOf("text")==-1 && 
    type.indexOf("txt")==-1 && 
    type.indexOf("HTM")==-1 && 
    type.indexOf("htm")==-1){
//System.err.println("bad content type "+type+" at site "+site);
System.out.println("bad content type "+type+" at site "+site);
ret = "Not html";
return;
  }
  InputStream in = u.getInputStream();
  BufferedInputStream bufIn = new BufferedInputStream(in);
  int data;
  while(true){
data = bufIn.read();
// Check for EOF
if (data == -1) break;
else ret+= ( (char) data);
  }
  s = ret;
}catch(Exception e){s=null;}
  }
  public String poll(){return s;}
}

public class spidergui extends Frame{

private spider s;
private Color txtColor;
private Color errColor;
private Color topColor;
private Color numColor;
private Color curColor;

public spidergui(spider spi, String title){
super(title);
curColor = new Color(40, 40, 200);
txtColor = new Color(0, 0, 0);
errColor = new Color(255, 0, 0);
topColor = new Color(40, 40, 100);
numColor = new Color(50, 150, 50);
s=spi;
setBounds(0, 0, 800, 600);
show();
toFront();
repaint();
}
public void endShow(){
System.out.println(s);
hide();
dispose();
}
public void paint(Graphics g){
super.paint(g);
s.todo.reset();
s.done.reset();
s.errors.reset();
s.omittions.reset();
String txt;
Object o;
g.setColor(curColor);
g.setFont(new Font("arial", Font.PLAIN, 18));
String cur = s.getCurrent();
if(cur.length()>80)g.drawString(
  cur.substring(0, 40)+
  " . . . "+
  cur.substring(cur.length()-30, cur.length()),
50, 50);
else g.drawString(cur, 50, 50);

g.setColor(numColor);
g.setFont(new Font("arial", Font.BOLD, 24));
g.drawString(Integer.toString(s.Visited()), 350, 80);

g.setFont(new Font("arial", Font.PLAIN, 14));
g.setColor(topColor);
g.drawString("To Do:", 100, 80);
g.drawString("Completed:", 500, 80);
g.drawString("Ignored:", 500, 250);
g.drawString("Errors:", 100, 420);

g.setColor(txtColor);
g.setFont(new Font("arial", Font.PLAIN, 12));
for(int i=0;i<23 && (o=s.todo.get())!=null;i++){
txt = Integer.toString(i+1) + ": "+o.toString();
if(txt.length()>65)g.drawString(
  txt.substring(0, 38) +
  " . . . " +
  txt.substring(txt.length()-18, txt.length()),
20, 100+13*i);
else g.drawString(txt, 20, 100+13*i);
}
for(int i=0;i<10 && (o=s.done.get())!=null;i++){
txt = Integer.toString(i+1) + ": "+o.toString();
if(txt.length()>60)g.drawString(txt.substring(0, 57)+"...", 400, 100+13*i);
else g.drawString(txt, 400, 100+13*i);
}
for(int i=0;i<10 && (o=s.omittions.get())!=null;i++){
txt = Integer.toString(i+1) + ": "+o.toString();
if(txt.length()>60)g.drawString(txt.substring(0, 57)+"...", 400, 270+13*i);
else g.drawString(txt, 400, 270+13*i);
}
g.setColor(errColor);
for(int i=0;i<10 && (o=s.errors.get())!=null;i++){
txt = Integer.toString(i+1) + ": "+o.toString();
g.drawString(txt, 20, 440+13*i);
}

}
public void run(){
repaint();
while(s.hasMore()){
repaint();
s.doNextSite();
}
repaint();
}

public static void main(String []args){
int max = 5;
String site="";
String base="";
int time=0;
for(int i=0;i<args.length;i++){
  if(args[i].startsWith("-max=")){
max=Integer.parseInt(args[i].substring(5,args[i].length()));
  }
  else if(args[i].startsWith("-time=")){
time=Integer.parseInt(args[i].substring(6,args[i].length()));
  }
  else if(args[i].startsWith("-init=")){
site=args[i].substring(6,args[i].length());
  }
  else if(args[i].startsWith("-base=")){
base=args[i].substring(6,args[i].length());
  }
  else if(args[i].startsWith("-help")||args[i].startsWith("-?")){
System.out.println("additional command line switches:");
System.out.println("-max=N     : to limit to N sites, default 5");
System.out.println("-init=URL   : to set the initial site, REQUIRED");
System.out.println("-base=URL   : only follow url's that start with this");
System.out.println("         default \"\" (matches all URLs)");
System.out.println("-time=N   : how many millisec to wait for each page");
System.out.println("         default 5000 (5 seconds)");
System.exit(0);
  }
  else System.err.println("unrecognized switch: "+args[i]+", continuing");
}
if(site==""){
  System.err.println("No initial site parameter!");
  System.err.println("Use -init=<site> switch to set, or -help for more info.");
  System.exit(1);
}

spider spi=new spider(site, max, base);

if(time>0)spi.setTimer(time);

spidergui s = new spidergui(spi, "Spider: "+site);
s.run();
System.out.println(spi);
}
}

 

评论

1 楼 blue3377 2010-04-02  

上面的代码 ，能用不哦？