《网络信息检索》课件第3章.ppt

1、第3章 网络信息的自动搜集第3章 网络信息的自动搜集3.1 网络信息的特点3.2 网络信息搜集的原理3.3 网络信息搜集的礼貌原则3.4 高性能信息搜集3.5 专题信息搜集3.6 小结思考题第3章 网络信息的自动搜集3.1 网络信息的特点网络信息的特点网络信息有各种各样的表现形式，这些信息都在WWW(World Wide Web，万维网，简称Web)上产生、流转和消亡，其中Web页面(网页)已经成为网络信息最重要的载体。随着网络的普及，网页的数量也成倍增加。据Cyveillance公司2000年关于网页大小的调研报告称1，Web上总网页数高达21亿，每天约增加730万个网页，如果每个网页按照平

2、均15 KB来计算，约需要109 GB的存储空间；到2005年1月为止，可见的网页(surface web)在115亿左右2，还不包括估计约500倍于可见网页的深度网页(deep web)3，如动态网页或搜索引擎无法到达的网页。网页之间或者具有链接的关系，或者毫无关系、或者短期内消失。因此，要全面地搜集和管理网络信息，并不是一件容易的事情。要有效地搜集信息，需要对万维网信息的组织结构进行深入的学习和了解。掌握了网络信息的组织结构和特点，就可以采用相应的对策和方法尽可能全面地来搜集这些信息了。第3章 网络信息的自动搜集3.1.1 Web的组成的组成简单地说，Web由三部分组成：资源、资源标识和传

3、输协议。资源对应着Web页面或各种文件，资源标识则是定位和指向资源的符号，而传输协议则负责在一些实体(如客户端和服务器)之间传送资源。第3章 网络信息的自动搜集1 资源资源Web上包含许多可用的资源，如文本、图像、视频片段和程序等。目前Web最主要的信息资源组织方式是HTML文档。HTML(HyperText Markup Language)是超文本标记语言，它由一系列的标签(tag)组成，说明网络信息的具体内容及网络信息的表现形式。HTML文档的名字后缀一般是htm或html。HTML文档包含的信息内容可以通过Web浏览器(Browser)来显示。Web浏览器可以对HTML文档进行解析，并将

4、内容按照标签指示，在浏览器中一页页地显示出来。第3章 网络信息的自动搜集HTML是简单的标识语言，用来创建万维网上使用的超媒体文档。HTML使用标签来标识HTML元素，例如标题、段落、列表、粗体或斜体文本，及其他类似的特性。标签通常成对出现，前面的标签为tag，后面的标签是/tag。Web浏览器分析原始HTML语言，并创建为一个用户可读的文档版本。HTML文档之所以称为超文本，就是因为它与一般的文本不同，它可以创建指向其他文档的超链接(hyperlink)。链接的定义是通过a标识。例如以下是一个指向文件peter.html的链接：a href=peter.htmlPeter的页面/a第3章 网

5、络信息的自动搜集在a与/a标签对之间的文本是链接用的文字，也称为锚文本(anchor text)。浏览器使用不同的颜色或字体显示这些链接。在用户选择一个链接时，浏览器便显示由链接指向的文档。锚文本在网络信息检索中起着非常重要的作用。关于HTML的详细介绍，请参考HTML标准维护者W3C组织4发布的HTML语言规格标准或其他相关文献资料。第3章 网络信息的自动搜集2 资源标识符资源标识符Web页面通过HTML文档指明它的内容和表现形式，呈现给读者。但是Web页面如此众多，如何找到这些网页，定位这些资源呢？Web上的资源是通过通用资源标志符(Universal Resource Locator，U

6、RL)来定位的。URL唯一地指明了一个Web页面的位置。它的语法构成如下：accessmethod：servername：port/directory/name第3章 网络信息的自动搜集其中，“accessmethod”是指资源服务器的服务方式，称为“使用协议”。在WWW系统中，最常用的就是HTTP(Hypertext Transfer Protocol，超文本传输协议)，也可以是FTP(File Transfer Protocol，文件传输协议)、NEWS等其他应用协议。“servername”指服务器域名，即接入到Internet中供访问的服务器，一般都有一个专用的域名，用户要访问服务器上

7、的资源，必须指明服务器的域名，也可以使用IP地址代替。“port”是一个服务的端口号，用数字表示，例如 HTTP服务对应的缺省端口值是80。“directory”指文件所在服务器的目录或路径。“name”是文件名，在缺省的情况下，首先会调出称为“主页”的文件，如index.html。第3章 网络信息的自动搜集一般而言，URL可分为两种类型，一种是绝对URL，另一种是相对URL。绝对URL就是指明需要访问的信息或资源的绝对位置，上面的URL语法定义实际上是绝对URL。相对URL就是定位资源的相对路径，所谓“相对路径”，就是所需资源相对于当前位置的路径。例如，如果服务器中的一个路径中有多个文件需要

8、访问，第一个访问文件已经指明了绝对路径，余下的仅需指明文件名就可以了。第3章 网络信息的自动搜集3 传输协议传输协议传输协议在Web中起着举足轻重的作用，通过它，信息资源才能够在网络上流转，起到信息共享的目的。目前支撑互联网络运转的是TCP/IP(Transmission Control Protocol/Internet Protocol)协议簇，它由很多协议构成，这些协议分别在TCP/IP模型的4个层次上起作用。图3-1是TCP/IP协议簇的示意图。第3章 网络信息的自动搜集图3-1 TCP/IP协议栈分层示意图第3章 网络信息的自动搜集HTTP是建立在TCP协议之上的应用层协议，用来在W

9、WW上传递文本网页或各种其他资源，如图片、音频或者视频等。HTTP协议采用请求/响应模式工作。在这个模式中，客户端发起HTTP请求，服务器端负责处理请求并发回HTTP响应。HTTP客户端的一个典型例子是Web浏览器，HTTP服务器，也叫Web服务器，著名的Web服务器有Tomcat5、Apache6和IIS7等。图3-2是HTTP工作原理示意图。第3章 网络信息的自动搜集图3-2 HTTP工作原理示意图第3章 网络信息的自动搜集HTTP请求和响应的报文格式相似，而且都是基于字符的，这两种报文遵循以下格式：(1)一个起始行；(2)零或若干个报头行；(3)一个空白行；(4)可选的消息主体。其中的起

10、始行，对于请求和响应报文是不同的。HTTP请求的起始行的结构为：Method Request-URI HTTP-Version CRLF第3章 网络信息的自动搜集Method表示请求的方法，比如get或者post，注意需要大写。HTTP的主要方法以及描述如表3-1所示。Request-URI 表示一个统一资源标识符；HTTP-Version 表示请求的HTTP协议版本；CRLF表示回车换行(对应的ASCII值分别为13和10)。例如：GET/somedir/page.html HTTP/1.1。HTTP响应的起始行称为状态行。HTTP响应的状态行的结构为 HTTP-Version Status

11、-Code Reason-Phrase CRLF第3章 网络信息的自动搜集其中：HTTP-Version表示服务器HTTP协议的版本；Status-Code表示服务器发回的状态码；Reason-Phrase表示状态码的文本描述；CRLF表示回车换行。状态码由3位数字组成，表示请求是否被理解或被满足。状态码分五种类型，由第一位数字表示：1xx：信息，请求收到，继续处理；2xx：成功，行为被成功地接受、理解和采纳；3xx：重定向，为了完成请求，必须进一步执行的动作；4xx：客户端错误，请求包含语法错误或者请求无法实现；5xx：服务器错误，服务器不能实现一种明显无效的请求。状态码的具体含义如表3-2

12、所示。例子：HTTP/1.1 200 OK。第3章 网络信息的自动搜集第3章 网络信息的自动搜集第3章 网络信息的自动搜集一个HTTP报文具有零到若干个报头字段，每个报头字段由字段名和值组成，独占一行，不同的报头字段，描述着该HTTP报文的独特属性。消息主体表示的是报文要传达的主要消息，它可以是ASCII字符或者是二进制数据。每一行之间，需要以回车和换行(CRLF)来分割。HTTP报头行的格式为 报头字段名：值HTTP请求的报头字段很多，下面只介绍一些基本的以及与网络信息搜索密切相关的字段。(1)User-Agent：这个报头字段存在于请求报文中，用于说明是什么客户端软件发出请求。服务器接收到

13、请求报文后，可以根据这个字段了解到发出请求的软件名字，从而回应不同的内容以避免不兼容等问题。第3章 网络信息的自动搜集(2)Content-Type：用于指明消息主体内所包含内容的类型。对于不同的类型，浏览器有不同的处理方法。如果是图像，则调入相应的图像处理函数进行处理；若是文字，则直接显示出来。(3)Content-Length：用于指明消息主体的长度。(4)If-Modified-Since：这个字段存在于请求报文中，此字段的值是一个时间。当一个请求报文包含此字段时，服务器检查所请求的资源的修改日期，如果发现修改日期比字段中提供的日期晚，则返回整个资源文件，否则仅返回报头信息。这对于优化速

14、度是有很大作用的。一般浏览器会把搜集过的资源缓存在本地磁盘上，当同样的资源被再次请求时，如果资源没有被修改过，则可以直接利用本地磁盘上保存的内容来加速浏览。浏览器就是利用这个字段，把本地磁盘上资源的日期发送到服务器。当服务器认为资源没有被修改过时，就不需要发送资源的主体，大大节省了网络开销。对于搜索引擎而言，在提高网络信息搜集速度方面同样可以利用此字段。第3章 网络信息的自动搜集下面举例介绍一个HTTP会话的过程，如图3-3所示。图3-3 一次简单的HTTP会话过程第3章 网络信息的自动搜集此会话描述的是访问华南理工大学网站的流程，是从客户浏览器发出请求，到服务器发出回应的一个完整过程。第一步

15、：客户在浏览器地址栏键入http：/；第二步：客户端连接服务器的80端口，建立到服务器上的TCP连接；第三步：客户端在这个连接上发送请求；第四步：服务器从客户请求中知道请求的客户端使用的是HTTP 1.1的协议，且需要搜集根路径上的资源。服务器就将对应的网页内容以响应报文的方式发送给客户机；第3章 网络信息的自动搜集第五步：客户端的浏览器发现响应码为200，知道请求成功，从Content-length得到消息主体的长度并从Content-Type获知这是文本性的网页，从消息主体上就可获得网页对应的HTML代码。这些信息经浏览器解释后显示给用户。在较早版本的HTTP协议中，每完成一个请求，就要断

16、开底层的TCP连接，这对于传输数目众多的小文件来说，效率不佳，需要频繁地建立新连接。为此在HTTP 1.1版本中，可以使用Connection：Keep-Alive来指定不要断开连接，继续使用该连接传输后面的其他请求内容。第3章 网络信息的自动搜集3.1.2 Web的特点的特点目前，万维网上存在着上万亿网页，有些网页之间通过超链接连接起来，有些网页却孤零零的，和其他网页无任何关系。如果把一个网页看做一个节点，而把超链接看做边，就可以得到一张巨大的Web图。研究者从数学角度对这张图及其派生进行了许多研究，获得了很多有意义的结论8-10。这些结论揭示了Web的一些统计规律，帮助我们从宏观上、抽象层

17、面上更好地认识Web。从网络信息搜索技术的角度来看，了解信息的来源Web的规律，有助于我们改善网络信息搜索的速度和质量。在讨论Web图的规律之前，有必要先来学习一些图的基本概念。第3章 网络信息的自动搜集由点集合V和点与点之间的连线的集合E所组成的集合对(V，E)称为图，用G(V，E)表示。节点之间，可以存在若干条边，如果这些边是有方向的，则这个图为有向图，反之则称为无向图。把每个网页看做单个节点，此网页内的超链接就可看做射出的边，这样就构成了Web图；也可以以一定的方法把一类的网页聚集在一起，把这个网页的集合看做一个节点，这个集合内的网页指向集合外网页的超链接看做射出的边。第3章 网络信息的

18、自动搜集Web图是有向图。以某节点v为起点的边的条数称为节点v的出度，以其为终点的边的条数称为v的入度。当从某节点A出发，通过边到达节点B，然后又从节点B出发，通过其上的边到达节点C，最后到达节点Z，我们称经过的边的集合为节点A到节点Z的路径。两个点之间可能存在不同的路径，路径上的边的数目称为路径的长度，两节点之间具有最少长度的路径称为最短路径。在图中，最长的任意两点的最短路径称做图的直径。第3章 网络信息的自动搜集1 Web的幂律分布的幂律分布幂律(power law)指的是两个变量x，y之间，存在着关系y=Cx。当一个概率分布的密度函数满足幂律时，称此分布为幂律分布。在Web上，幂律分布无

19、处不在：网页的大小、网页的连接度和浏览网页的行为等都被研究人员证实为满足幂律分布8-9，11-14。当幂律分布被用于对数据进行分级时，通常称为Zipf分布或者Pareto-Zipf分布。例如，在语言研究领域，把词与它们在日常生活中出现的频率进行分级所产生的分布总是满足幂律分布的。离散的幂律分布有以下形式：P(X=k)=Ck(1，k=1，2，3，)(3-1)第3章 网络信息的自动搜集而对于连续的幂律分布，则有以下的密度函数：f(x)=Cx，x1，+)(3-2)如前所述，幂律分布存在于很多方面。在Web上，人们也发现了不少的满足幂律分布的数据。Huberman和Adamic8 曾对几个著名搜索引擎

20、抓取的好几百万的网页记录进行分析，发现当以页面数量去衡量网站大小时，网站的大小遵循幂律分布，其中在1.61.9之间。这个发现使得我们可以估算出一定大小的网站的数量。除了网站的大小之外，Web图中节点的度，无论是有向的情况还是无向的情况，都满足幂律分布。例如，一项根据对印第安纳Notre Dama大学所在域的抓取结果进行的研究9指出，其网页的出度满足幂律分布，大约为2.45；而入度也同样满足幂律分布，为2.1。第3章 网络信息的自动搜集2 小世界理论小世界理论另外一个关于Web图的经验性理论就是小世界(Small world)理论。通过实验，人们发现Web图的直径相对于整个Web图来说，是很小的

21、。这个理论开始于著名心理学家Milgram在1967年对社交网络的研究15。Milgram认为，当地球上任意两个人需要通信或者转交物品时，可以通过托付给熟人的形式进行，而被托付人也可以再继续托付熟人，当最终完成通信或者交换物品时，托付链的长度一般不会超过6，这就是著名的六度分割(Six Degrees of Separation)理论16。如果从图论的角度来看，也就回到了图的直径的问题上：在社交网络图中，网络直径一般不会超过6。因此社交网络就是一个小世界网络。第3章 网络信息的自动搜集然而Web图实在是太大了，要精确地计算出Web图的直径或者平均最短路径长度很困难。一般地，在图中寻找任意两点的

22、最短长度需要O(n2)，即使使用了Cormen17的根据Web的稀疏特性提出的动态规划算法，也需要O(n logn)。由于n非常大，还是无法在合理的时间内完成计算。为此，人们在研究Web图的直径时通常采用采样的办法。不过需要注意的是，使用这种办法无法保证获取精确的最长的最短路径，也就是无法精确获取整个Web图的直径。通过生成具有同样的链接幂律分布的随机图，Albert等人发现9，两节点之间的平均距离为(3-3)d=0.35+2.06 logn第3章 网络信息的自动搜集例如，假设Web图的节点数n=109，根据这个公式计算得到d=E l=18.89，相对于数10亿节点规模来说，Web图直径太小了

23、，是一个小世界网络。这个例子说明，用户通过19次点击可从一个网页到达另外一个目的网页。这个研究结果在一定程度说明了万维网的可用性和可管理性，否则当我们为获取一个信息需要大量点击时，互联网将变得很难管理和使用。这个距离也为设计高效的搜索引擎的信息自动搜集系统提供了理论依据。第3章 网络信息的自动搜集3 蝴蝶结理论蝴蝶结理论Web图的另外一个著名规律是蝴蝶结理论，研究人员把注意力放在了部件(component)间的关系研究上。这里的部件，是指一些网页的集合。Broder等人的研究10表明，万维网上的网页可以根据连接性分为四类。第一类称为强互连部件(Strong Connected Componen

24、t，SCC)，这类部件的特点是每一个在此集合内的网页都可以通过超链接组成的路径彼此到达，这类部件内的网站大多是一些著名的公共站点；第二类部件称为IN部件，这里面的网页都有超链接到达SCC，然而不能从SCC内的网页到达自身；第三类称为OUT部件，这类部件与IN部件恰恰相反，能从SCC部件出发到达自身，但是不能从自身到达SCC；最后一类是由不能归纳为以上任何一类的网页组成的，然而，它们或者能从IN部件中出发最后到达自身或者能从自身出发，最后到达OUT部件，表现为图3-4中的触须(tendril)或管道(tube)，还有少部分的网页不算在以上四个类别中，称为孤立部件(disconnected com

25、ponent)。第3章 网络信息的自动搜集图3-4 万维网的蝴蝶结形状10第3章 网络信息的自动搜集通过上述的定义和Web本身数据的分析，Web可以被描述成图3-4的宏观图，这就是Broder给出的万维网的宏观写照。由于它酷似蝴蝶结，也被称为蝴蝶结图，Web的这个特性或规律也被称为蝴蝶结理论。第3章 网络信息的自动搜集3.2 网络信息搜集的原理网络信息搜集的原理网络信息的自动搜集实质是利用一种专用程序，向不同的Web服务器发出请求，以获取一个Web文档及递归地获取其指向的文档信息。这些专用程序俗称网络爬虫(crawler)，还有其他不同的名称，如网络蜘蛛(spider)、网络机器人(robot

26、)、网络漫游者(web wanderers)、网络蠕虫(web worm)等，其中的网络蠕虫因为容易引起误解，已经很少在这个意义上使用。如果要区分的话，网络蜘蛛是用来下载网页，如浏览器一样分析HTML的源码；网络爬虫是用来发现网页上的所有链接，它的工作是决定网络爬虫的爬行方向。在本文中，并不严格区分网络蜘蛛和网络爬虫，而是把采集程序统称为网络爬虫。第3章 网络信息的自动搜集最早(20世纪90年代中叶)的网络爬虫主要用来进行网络统计分析、网络维护、镜像等，较早的用来搜索信息的网络爬虫是“fish search mechanism”，这是面对Mosaic(第一个Web浏览器)用户的搜集器，而且针对

27、用户提交的查询，立刻到Web上搜集相关信息，即使下一个用户查询同样的东西，也需要再次到Web上进行信息搜集。虽然网络爬虫很形象地描述了这些程序在Web爬行以搜集网络信息，但它并不真正在Web上爬行，而是充当客户端，向众多的Web服务器发出请求，并获得相应的Web页面文档。第3章 网络信息的自动搜集3.2.1 信息搜集的基本流程信息搜集的基本流程从Web上搜集信息，就是遍历整个图的各个节点，向各节点URL请求网页，并对其进行解析。图3-5给出了网络爬虫的基本流程图。网络爬虫最主要的一个数据结构是待处理URL列表，国外一些文献将它称为Frontier，在信息采集流程开始的时候，Frontier被起

28、始网页URL(种子URL)填充，接着进入信息采集循环流程，在采集流程中，URL列表不断被更新。信息采集开始时，首先判断循环是否应该结束。对于不同目的的网络爬虫，可能有不同的停止条件。例如待处理URL列表为空，且无正在工作的网页信息采集分析的线程，就可以作为网络爬虫停止的条件；又如某网络爬虫仅仅是搜集某方面的信息，当发现已经搜集足够满足需求的资料时，就停止搜集。第3章 网络信息的自动搜集图3-5 网页信息搜集的基本流程图第3章 网络信息的自动搜集接下来从列表中选取一个URL，根据遍历策略的不同，有不同的选取方法。对于简单的队列或者堆栈来说，只需要出队或出栈即可。对于复杂的实现，可能还需要通过计算

29、，才能确定从待处理URL中挑选出哪个URL进行抓取。选取了待处理的URL之后，网络爬虫一般使用HTTP协议来获取指定URL对应的网页内容。这一步虽然比较直接简单，但由于需要遍历的Web太大，以及存在网络时延的原因，为了提高效率，通常都需要通过采用并行技术来优化该项工作。第3章 网络信息的自动搜集接下来对采集到的网页进行解析。将网页的基本内容进行处理、存储和索引；另外需要分析出网页中是否含有新的URL，对URL进行处理和去重，将无重复的新的URL加入到待处理URL列表中；这一步还可以进行一些网页的统计信息处理等。从图3-5来看，似乎网络信息的采集流程比较简单。确实如此，如果不考虑太多效率、性能的

30、问题，单单完成信息采集的网络爬虫只是一个小小的程序而已。但实际上网络信息采集是一个复杂的工程问题，我们将完成信息采集任务的系统称之为网络信息搜集系统。如果要写一个相对完美、性能优越的网络信息搜集系统，就要考虑到方方面面的问题，比如遍历的策略、停止的条件、URL去重处理等等。第3章 网络信息的自动搜集3.2.2 遍历策略遍历策略如前所述，可以将Web世界看做一个庞大的图，网络爬虫的任务就是从某个起始网页集出发，沿着网页中的超链接，试图以某种策略遍历Web图，从而获取Web上的全部信息。对于图的遍历，可以采用“广度优先(Breadth First)”、“深度优先(Depth First)”这两个基

31、本策略。第3章 网络信息的自动搜集1 广度优先遍历策略广度优先遍历策略已知图G=(V，E)和一个源节点s，广度优先搜索以一种系统的方式探寻G的边，从而“发现”从s出发能到达的所有节点，并计算s到所有这些节点的距离(最少边数)，采用这种策略可产生一棵根为s且包括所有可达节点的宽度优先树。对从s可达的任意节点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。采用广度优先策略的遍历算法被称为宽度优先算法，它的本质是自始至终通过已找到和未找到节点之间的边界向外扩展，就是说，算法首先搜索与s距离为k的所有节点，然后再去搜索与s距离为k+1的其他节点，其中k是自然数。第3

32、章 网络信息的自动搜集对于网络爬虫来说，如果把待处理的URL排成队列，广度优先策略是先进先出的搜索策略，每次从网页解析得到的新URL都添加在队列末尾，每次都从队列的头部选取URL进行解析。按照广度优先策略爬行Web页面可形象地描述为图3-6，网络爬虫先把位于同一层的网页抓取完，再抓下一层的网页，直到最底层为止，图中的数字表示网络爬虫抓取的顺序。第3章 网络信息的自动搜集图3-6 采用广度优先策略遍历的示意图第3章 网络信息的自动搜集由图3-6可知，广度优先从根网页统一地向外搜索，但需要存储前一层次的所有节点，这些节点的数量随着深度的增加呈指数增长。宽度优先是常用的网络爬虫搜索策略，下面给出采用

33、宽度优先策略的信息搜集的基本算法。在该算法中，只下载HTML页面，而不处理其他类型的信息如图片和PDF、PPT文档等。此算法描述如下：第3章 网络信息的自动搜集用已知的URL列表初始化队列Q循环直至Q为空或限定搜集时间到：从Q的前部取出一个URL：L 如果L不是HTML页面(例如后缀为.gif、.jpeg、.ps、.pdf、.ppt等)继续循环；如果已经访问过L，继续循环；下载L对应的页面P 如果无法下载P(如：404错误，机器人排斥协议)继续循环；解析P提取新的链接N 追加N到Q的后面第3章 网络信息的自动搜集2 深度优先遍历策略深度优先遍历策略假设给定图G的初态是所有节点均未曾访问过，在G

34、中任选一节点s为初始出发点(源点)，则深度优先策略的遍历可描述如下：首先访问出发点s，并将其标记为已访问过；然后依次从s出发搜索s的每个邻接点w，若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源节点s路径相通的节点(亦称为从源点可达的顶点)均被访问为止；若此时图中仍有未访问的节点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有节点均被访问为止。第3章 网络信息的自动搜集深度优先遵循先进后出的原则，和广度优先相反，每次解析得到的新URL都放在队列的头部，这样使得网络爬虫从起始页面s出发，沿着s的某一个链接一直搜索到某个不包含任何链接的文件为止，这样形成一条

35、完整的链，再返回s继续选择其他链接进行类似的访问，访问结束的标志是不再有其他超级链接可以搜索，深度优先遍历过程可用图3-7表示。深度优先相对宽度优先而言，使用的存储空间较少，存储的节点数只随深度的增加呈线性增长。但是，采用深度优先策略的网络爬虫在抓取的过程中，可能因为无限制地在一条路上抓取而导致迷航。实际应用中，可以通过设置抓取的最大深度来限制网络爬虫的抓取，避免迷航现象的发生。第3章 网络信息的自动搜集图3-7 采用深度优先策略遍历的示意图第3章 网络信息的自动搜集3.2.3 页面解析页面解析要遍历整个Web图，关键要从获取到的网页中提取超链接URL。而为了进一步地进行索引和检索，还需要从网

36、页中提取更多的信息，如整个页面的主要内容，并区分哪些是题目，标题和锚文本等。因此HTML文档解析非常重要。从HTML文档中获取主要内容，首先要对HTML标签进行分析。假设需要从一份HTML文档中提取URL和链接文本，该文档包括如下标签的内容：a href=http：/OReilly Media/a第3章 网络信息的自动搜集因为a标签的内容可能相当复杂，可以分两步实现这个任务。第一个是提取a标签内部的内容，也就是锚文本，然后从a标签中提取URL地址。最简单的方法是采用正则表达式。例如可用以下的正则表达式(Perl语言)：ab(+)(.*?)/a来分开a的内容和锚文本的内容。提取出a的内容后，就可

37、以提取URL了。注意到，URL是“href=value”属性的值。HTML允许等号的任意一侧出现空白字符，值可以以引用形式出现，也可以以非引用形式出现。第3章 网络信息的自动搜集实际上很多的网页撰写并不规范，提取出的URL也五花八门，所以需要对提取出的URL进行正规化处理，以便网络爬虫以沿着URL爬行。URL正规化主要包括以下内容：(1)大小写转换：URL一般不区分大小写，但是不同的Web服务器或网络爬虫运行的操作系统不一样，可能会给网页的抓取带来问题。所以一般需要将URL字符串的大小写统一，以避免出现意想不到的问题。方法是统一URL字符串中的协议名和域名部分的字符串，URL中的这两个部分都是

38、不区分大小写的，但是后面的路径部分可能是大小写敏感的。例如：HTTP：/www.SCUT 网络信息的自动搜集(2)删除URL中的分块部分：在比较长的网页中，页内定位分块经常使用。一般地，http：/ 网络信息的自动搜集 以“/”开头的相对路径，从站点的根目录开始计算，那么首先需要知道站点的主机名，然后拼接成以协议名称开头的绝对路径。如在http：/页面中提取到一个URL为“/aa/index.jsp”,则应该拼接成http：/ 网络信息的自动搜集除了提取URL外，很多应用还需要从HTML文档中获取各种不同的内容，包括标题、关键词和摘要等可用来概括某个页面的主要内容。正文是原始网页中真正描述主题

39、的部分，因此在某些具体应用中用正文代替原始网页更合理。这就意味着需要对各种不同的HTML标签进行分析，从而提取出相应网页的内容。这是一个HTML解析器(parser)所要完成的工作。但是，设计一个好的HTML解析器并不是件容易的事情，因为很多网站的建设并没有严格地遵循W3C的相关标准，因此，要求HTML解析器必须能够识别不规范的甚至残缺不全的HTML文档。网络上有许多开源的HTML解析器，例如Tidy18。最早的Tidy由Dave Ragget采用C语言实现，JTidy19是Tidy的Java版本。Apache的全文检索引擎Lucene20提供了DocumentHandler接口，调用了Jti

40、dy的parseDOM方法来解析HTML文档。第3章 网络信息的自动搜集3.3 网络信息搜集的礼貌原则网络信息搜集的礼貌原则网络爬虫总是试图抓取Web上的所有信息。但是有些网站并不希望它的站点内容提供给公众，或者只希望提供部分的信息供公众检索。就像一个房子，主人的卧室不能让客人随意进入，但客厅是可以随便参观的。网络爬虫就像到访的客人，要尊重主人的隐私和意愿，不要窜到私人空间去。站点的所有者可以将自己的意愿发布出来，要求网络爬虫遵守一定的礼貌原则。目前礼貌原则的实现主要有两种机制，机器人排斥协议(Robots Exclusion Protocol)和机器人元标签(Robots META Tag)

41、。第3章 网络信息的自动搜集3.3.1 机器人排斥协议机器人排斥协议1994年，Koster21提出了机器人排斥协议，它既不是官方标准，也不属于某个商业机构。它不强制任何机构遵循，但它是一个事实标准，很多著名搜索引擎的网络爬虫都遵循这个标准。需要内容保护和指导网络爬虫礼貌搜集的网站，把名为robots.txt的文件放到网站的根目录下，礼貌的爬虫爬行到该网站，首先读取这个文件，然后再根据文件中的规则，决定是否搜集该网站或搜集哪些子目录。事实上，robots.txt文件是一些简单规则的说明，注明了该网站哪些地方不能去，哪些地方可以去。当然网络爬虫是否遵循这个协议，取决于网络爬虫程序的设计者。第3章

42、 网络信息的自动搜集robots.txt文件由若干条记录组成，记录之间用一个或多个空行隔开。其中每条记录均由两个域组成：User-agent域和Disallow域，前者指明受限的网络爬虫名称，后者指明受限的范围。每条记录由若干行组成，每行的格式如下(其中域名大小写敏感):field：value(1)User-agent(用户代理)。User-agent行用于指定网络爬虫的名字，如需要指明Google的网络爬虫程序Googlebot，则可用User-agent:Googlebot。一个robots.txt文件中至少要有一条User-agent记录。如果有多条User-agent记录，则说明有多个

43、爬虫程序会受到规则的限制。如果要匹配所有的爬虫程序，可以使用通配符“*”，即User-agent:*。第3章 网络信息的自动搜集(2)Disallow(拒绝访问声明)。在robots.txt文件中，每条记录的第二个域一定是Disallow指令行。这些Disallow行声明了该网站中不希望被访问的文件和(或)目录。例如“Disallow：email.htm”对文件的访问进行了声明，禁止网络爬虫下载网站上的email.htm文件；又如“Disallow：/cgi-bin/”则对cgi-bin目录的访问进行了声明，拒绝网络爬虫进入该目录及其子目录。Disallow声明行还具有通配符功能。例如“Dis

44、allow:/bob”则拒绝网络爬虫对/bob.html和/bob/的访问(即无论是名为bob的文件还是名为bob的目录下的文件都不允许网络爬虫访问)。Disallow记录如果留空，则说明该网站的所有部分都向网络爬虫开放。第3章 网络信息的自动搜集另外，在robots.txt文件中，凡以“#”开头的行，均被视为注解内容，这和UNIX中的惯例是一样的。下面给出robot禁止协议的一些实例：禁止所有爬虫的访问：User-agent:*Disallow:/禁止指定的目录：User-agent:*Disallow:/tmp/Disallow:/cgi-bin/Disallow:/users/paran

45、oid/第3章 网络信息的自动搜集禁止指定的爬虫:User-agent:GoogleBot Disallow:/允许指定的爬虫：User-agent:GoogleBot Disallow:第3章 网络信息的自动搜集3.3.2 机器人元标签机器人元标签除了机器人排除协议外，HTML文档中的META标签也可指定网络爬虫是否对本网页进行抓取、跟踪。META标签的格式如下：meta name=“robots”content=“none”其中，content的内容值可取如下这些值或它们的组合：(1)index|noindex：表示允许不允许索引这个网页；(2)follownofollow：表示允许不允许

46、跟踪这个页面上的链接；(3)all：表示允许索引这个页面，并且允许沿这个页面上的链接跟踪抓取；第3章 网络信息的自动搜集(4)none：表示既不允许索引这个页面，也不允许跟踪这个页面上的链接。例如：meta name=“robots”content=“noindex，follow”表示不允许索引这个页面，但允许跟踪这个页面上的超链接。第3章 网络信息的自动搜集3.4 高性能信息搜集高性能信息搜集前面介绍了网络爬虫的基本抓取流程和原理。一个好的网络爬虫应该具有以下特征：(1)友好的：网络服务器有潜在的和外在的用以判断一个网络爬虫是否可以访问它们的策略，网络爬虫应该遵守这些礼貌规则。(2)可扩展的

47、：网络爬虫应该能够有效利用处理器、存储器和网络带宽等各种不同的系统资源，并允许通过增加额外的机器和带宽来提高抓取速度。网络爬虫应该设计为在许多方面是可扩展的，可将任务分布到多台机器或多个处理器上并行执行，可应对新的数据格式和新的抓取协议等。第3章 网络信息的自动搜集(3)高质量的：如果抓取回来的重要网页不够全面，对于满足用户的查询需要是没有意义的，因此网络爬虫应该尽可能抓取重要的和有用的网页。(4)更新及时的：大多数的应用程序均要求网络爬虫获得所需要页面的最新版本。一个网络爬虫应该能够以接近页面更新速度的频率来抓取页面，以保证更新及时。(5)鲁棒的：网络上存在的蜘蛛陷阱(Spider Trap

48、)等可能误导网络爬虫在一个特定领域内抓取无限多的网页，网络爬虫必须设定为对这些圈套有较强的处理能力。因此，要编写一个高效的网络爬虫程序，实现高性能信息采集，还需采用适当的机制解决一些现实的问题。第3章 网络信息的自动搜集3.4.1 并行搜集并行搜集搜索引擎总是希望它的信息搜集系统所采集的信息是最新的信息，即希望更新速度足够快，以便为用户提供最新的信息。下面举个例子简单地说明网络爬虫爬行的速度22。假设广域网往返时间RTT为200 ms，服务器处理时间为100 ms，网页大小为13 KB，网络报文长1500 B，那么爬虫程序发起HTTP请求到获取某个网页需要的时间为(13 KB/1500 B)(

49、2200+100)ms4 s。如果爬虫程序昼夜不停地爬行，一天可以抓取网页246060 s/4 s=21 600个。这样算来，如果要遍历Web图，大约需要120亿/21 600=555 556天，约1522年！即使只抓取其中十分之一，也需要100多年，这样的网络信息搜集系统不具有实际应用价值。第3章 网络信息的自动搜集上面的例子也说明了这样的事实：网络爬虫消耗了大部分的时间来等候数据。所以，可以同时开启多个采集线程，以充分利用等候数据的时间，这就是并行信息采集。只要管理好这些采集线程，抓取性能可以得到大幅度的提升。仍然是刚才那个例子，假设同时开启300个采集线程，则遍历Web图需要的时间约为1

50、20亿/(21 600300)=1851天，约5年，这个时间也太长，所以可以采用更多的并行采集线程，并行多级后台管理等技术进行采集优化，让更新周期缩短到12周。并行采集的关键是如何管理协调好这些采集线程。其一是要解决多个线程之间的通信问题，其二是要解决控制多个线程对同一站点的同时访问，防止过频访问对被访问站点的冲击。第3章 网络信息的自动搜集多个采集线程并行运行，很可能出现重复的网页抓取，线程间的有效沟通可以避免这个问题。可以采用不同的方法来解决，一种解决方法叫动态分配法，之所以叫动态分配法，是因为每个线程的URL通常由一个中心管理进程来临时分配。中心管理进程负责线程间的协调沟通和负载均衡，这