【www.rzshzz.com--主题班会】
摘 要
随着web上信息的迅速扩展，各项基于web的服务也逐渐繁荣起来。作为这些信息服务的基础和重要组成部分，web信息采集正应用于搜索引擎、站点结构分析、页面有效性分析、web图进化、用户兴趣挖掘以及个性化信息获取等多种应用和研究中。然而，随着人们对提供的各项信息服务要求越来越高，传统的基于整个web的信息采集也越来越力不从心，它无法及时地采集到足够的web信息，也不能满足人们日益增长的个性化需求。为此，本文展开了对web上局部范围内信息的有效采集研究，也就是基于主题的web信息采集研究。
根据我们在信息采集领域的长期积累以及国内外在基于主题的信息采集领域的发展，本文在综述了基本情况后提出了一个基于主题的web信息采集结构模型，这包括主题与起始url选择、spider采集、页面分析、url与主题的相关性判定、以及页面与主题的相关性判定等一系列步骤。我们分别给出了相关的处理算法和流程以及相应的数据结构，并针对研究过程中遇到的问题，提出了多个新的算法、判定规则和规律：
在hub特性、linkage/sibling locality特性、站点主题特性、tunnel特性的基础上，总结出了主题页面在web上的分布规律。
在定义主题和提出分类主题的基础上，给出了主题选择的方法。
采用client/server结构的spider系统，允许多机同时采集，实现了全面、高效并且灵活的信息搜集。
在分析了html语法的基础上，给出了对html页面的主题、链接、标题的提取算法。
在url与主题的相关性判定中，在扩展元数据方法rw、rwb和链接分析方法pagerank的基础上提出了ipagerank算法。
在页面与主题的相关性判定中，应用在自然语言处理中比较成熟的基于关键词的向量空间模型计算页面与主题的相似度。
试验结果显示，我们的工作是有效的，我们的系统有很强的实用价值，特别是url与主题的相关性判定中的ipagerank算法，有较大的突破。
关键词：web，信息采集，主题，受限，搜索引擎，pagerank，ipagerank
目 录
第一章 引言……………………………………………………………………………….1
1.1 背景... 1
1.2 本文安排... 2
第二章 web信息采集概述………………………………………………………………4
2.1 web信息采集系统的基本原理... 4
2.2 web信息采集系统的基本结构... 4
2.3 web信息采集面临的主要困难和相应的技术手段: 6
2.4 采集系统实例... 8
第三章 web信息采集的研究现状………………………………………………….. ...11
3.1 基于整个web的信息采集... 11
3.2 增量式web信息采集: 12
3.3 基于主题的web信息采集: 12
3.4 基于用户个性化的web信息采集... 13
3.5 基于agent的信息采集... 14
3.6 迁移的信息采集... 15
3.7 基于元搜索的信息采集: 15
3.8 小结... 15
第四章 基于主题的web 信息采集基本问题研究………………………………… ...17
4.1 基于主题的web信息采集的定义... 17
4.2 基于主题的web信息采集的优点... 17
4.3 基于主题的web信息采集的分类... 18
4.4 主题页面在web上的分布特征... 19
4.5 相关性判别算法研究... 21
第五章 基于主题的web 信息采集系统模型及我们的对策……………………… ...37
5.1 系统模型... 37
5.2 模型中的关键问题及我们的策略... 37
第六章 主题选择………………………………………………………………………...41
6.1 主题的定义... 41
6.2 主题分类目录... 41
6.3 web上的主题分类目录的特点... 42
6.4 主题选择策略... 42
第七章 spider采集……………………………………………………………………44
7.1 spider的系统模型... 44
7.2 采集算法及实现... 45
第八章 页面分析……………………………………………………………………...…49
8.1 html语法分析... 49
8.2 页面中正文的提取... 49
8.3 页面中链接的提取... 50
8.4 页面中标题的提取... 51
第九章 url、页面与主题的相关性判定…………………………………………...…52
91 url与主题的相关性判定——ipagerank算法... 53
9.2 页面与主题的相关性判定——向量空间模型算法... 56
第十章 系统的实现与总结…………………………………………………………...…58
10.1 系统实现情况... 58
10.2 系统测试结果... 58
103 进一步的工作... 62
10.4 结论... 62
1.1 背景
随着internet/intranet的迅速发展，网络正深刻地改变着我们的生活。而在网上发展最为迅猛的www（world wide web）技术，以其直观、方便的使用方式和丰富的表达能力，已逐渐成为internet上最重要的信息发布和传输方式。随着信息时代的到来和发展，web上的信息如雨后春笋般迅速增长起来。截止到2000年7月，internet上的网页数量就已经超过21亿，上网用户超过3亿，而且网页还在以每天700万的速度增加[徐泽平 2001]。这给人们的生活提供了丰富的资源。
然而，web信息的急速膨胀，在给人们提供丰富信息的同时，又使人们在对它们的有效使用方面面临一个巨大的挑战。一方面网上的信息多种多样、丰富多彩，而另一方面用户却找不到他们所需要的信息。因而基于www的网上信息的采集、发布和相关的信息处理日益成为人们关注的焦点。
为此，人们发展了以web搜索引擎为主的检索服务。为了解决网上信息检索的难题，人们在信息检索领域进行了大量的研究，开发了各种搜索引擎(如google、yahoo)。这些搜索引擎通常使用一个或多个采集器从internet上收集各种数据(如www、ftp、email、news)，然后在本地服务器上为这些数据建立索引，当用户检索时根据用户提交的检索条件从索引库中迅速查找到所需的信息[bowman 1994]。作为这些搜索引擎的基础和组成部分，web信息采集正发挥着举足轻重的作用，并且随着应用的深化和技术的发展，它也越来越多的应用于站点结构分析、页面有效性分析、web图进化、内容安全检测、用户兴趣挖掘以及个性化信息获取等多种服务和研究中。简单说，web信息采集是指通过web页面之间的链接关系，从web上自动地获取页面信息,并且随着链接不断向所需要的web页面扩展的过程。
传统的web信息采集的目标就是尽可能多地采集信息页面，甚至是整个web上的资源，而在这一过程中它并不太在意采集的顺序和被采集页面的相关主题。这样做的一个极大好处是能够集中精力在采集的速度和数量上，并且实现起来也相对简单，例如google采集系统在并行4个采集器时的速度可以达到每秒100页，从而它配合搜索引擎给网络用户带来了很大的便利。但是，这种传统的采集方法也存在着很多缺陷。
随着www信息的爆炸性增长，信息采集的速度越来越不能满足实际应用的需要。最近的试验表明，即使大型的信息采集系统，它对web的覆盖率也只有30-40%。解决这一问题的直接办法是升级信息采集器的硬件，采用处理能力更强的计算机系统，然而这种方法的扩展性有限，性价比也不高。一个更好的解决方法是采用分布式方法来提高并行能力，但是并行不但增加了系统的开销和设计的复杂性，并且并行换来的效益也随着并行采集器数目的增加而显著地减小。目前，一般的大型采集系统都采用了并行机制，但并行带来的改善效果仍远不能满足人们的需要。人们需要从其它角度改善目前的困境。比如说对整个web分块采集，并将不同块的采集结果整合到一起，以提高整个web的采集覆盖率。
internet信息的分散存储、管理和动态变化也是困扰着信息采集的问题之一。由于信息源随时可能处于变化之中，信息采集器必须时常地刷新数据，但仍无法避免采集到的页面失效的情况。对于传统的信息采集来说，待刷新页面数量的巨大使得很多采集系统刷新一遍需要数周到一个月的时间[aggarwal et al. 2001][brin&page 1998]，这使得页面的失效率非常地巨大。selberg和etzioni在1995年的调查发现，通过internet中最常用的一些搜索引擎查询到的结果url中，14.9%的目标页面已经失效了[selberg&etzioni 1995]。一个显然的缓解办法就是减小采集页面的数量，从而减小刷新一遍的时间，进而减小页面已采集页面的失效率。
传统的基于整个web的信息采集需要采集的页面数量十分浩大，这需要消耗非常大的系统资源和网络资源，而对这些资源的消耗并没有换来采集到页面的较高利用率，事实上，它们中有相当大的一部分利用率很低。这是因为，用户往往只关心其中极少量的页面，并且这些页面往往集中在一个主题或几个主题内，而采集器采集的大部分页面对于他们来说是没有用的。尽管许多用户合起来的效果提高了整个采集到页面的利用率，但仍然显得利用率偏低，这显然是对系统资源和网络资源的一个巨大浪费。为了有效的提高它们的利用效率，我们有必要另辟蹊径。
对于用户的一般信息查询检索要求，传统信息采集器所组成的搜索引擎能够提供较好的服务，但对于用户更多的具体要求，这种传统的基于整个web的信息采集所提供的服务就难以令人满意。对于每个用户来说，尽管他们输入同一个查询词，但他们渴望得到的查询结果却是不一样的，而传统的信息采集和搜索引擎却只能死板地返回相同的结果，这是不合理的，需要进一步提高。
这些问题主要都源于两点：采集页面的数量过于庞大和采集页面内容的过于杂乱。对整个 web页面进行分类，按类别采集，基于主题进行采集的思想应运而生。它有效的减少了采集页面的数量，增加了采集页面的规整程度，进而有效的缓解了上述问题。因此需要开展对基于主题的web信息采集研究。
1.2 本文安排
第二章概述了web信息采集的基本结构、所面临的主要困难和相应的技术手段。在第三章里，讨论了web信息采集的研究现状和热门的发展方向，并通过论述指出基于主题的web信息采集的迫切性和必要性。在第四章里，我们讨论了基于主题的web信息采集的基本问题，重点是对主题页面在web 上的分布和相关性判定算法的研究。第五章给出了我们设计的基于主题的web信息采集系统的结构模型，并就搭建一个这种采集系统所面临的关键问题和相应对策做了简单的描述。在接下来的四章中(从第六章到第九章)，我们按照结构模型中的主要部分主题选择、spider采集、页面分析、url和页面与主题的相关性判定分别作了较为详细的论述，并给出了我们的设计方案和算法。最后，在第十章里，我们给出了系统的实验结果和进一步需要研究的问题。
第二章 web信息采集概述
在研究基于主题的web信息采集之前，让我们先来看看web信息采集的基本情况，这包括web信息采集的基本原理、基本结构和主要难题。它们是从各类web信息采集系统中抽象出来的，因此代表了比较本质和共性的特征，而对于每个实际的采集系统来说，又与它们有所差别。为了更好的了解采采集系统，我们在本章的最后列举了两个实例。
2.1 web信息采集系统的基本原理
web信息采集（web crawling），主要是指通过web页面之间的链接关系，从web上自动的获取页面信息,并且随着链接不断向所需要的web页面扩展的过程。实现这一过程主要是由web信息采集器（web crawler）来完成的。根据应用习惯的不同，web信息采集器也常称作web spider、web robot和web worm。粗略的说，它主要是指这样一个程序，从一个初始的url集出发，将这些url全部放入到一个有序的待采集队列里。而采集器从这个队列里按顺序取出url,通过web上的协议，获取url所指向的页面，然后从这些已获取的页面中提取出新的url,并将他们继续放入到待采集队列里，然后重复上面的过程，直到采集器根据自己的策略停止采集。对于大多数采集器来说，到此就算完结，而对于有些采集器而言，它还要将采集到的页面数据和相关处里结果存储、索引并在此基础上对内容进行语义分析。
2.2 web信息采集系统的基本结构
如图2.1所示，web信息采集系统基本上可以划分为七个部分:url处理器、协议处理器、重复内容检测器、url提取器、meta信息获取器、语义信息解析器和数据库，它们协调起来从web上获取信息。图中的箭头表示数据走向。
2.2.1 url处理器
这个部件主要给待采集的url排序，并根据一定的策略向协议处理器分配url。按照采集系统规模的不同，url可以是多个采集队列，也可以是一个url server。比如，天罗web采集系统采用了多个采集队列，而google采集系统则使用了url server，以达到更快的处理速度。url处理器主要有三个数据来源：1)初始的种子url集，如图中的粗箭头所示；2)从url提取器传输过来的url集,它们是从已经采集到的页面中提取出来的；3)页面的meta、主题以及摘要等信息，来自meta信息获取器，它们主要用来显示从url提取器中传输过来的url的重要性，为在这里排序提供依据。另外，url处理器还有一个任务就是dns解析。
图2.1 web信息采集系统基本结构
2.2.2 协议处理器
这个部件处于系统的底层，主要通过各种web协议来完成数据的采集。一般来说协议包括http、ftp、gopher以及bbs,也有些采集系统根据应用的需要采集web chat、icq等特殊信息。但从主流上看，仍以http为主。
2.2.3 重复内容检测器
web上存在着大量的镜像页面和内容，最近的研究表明，将近30%的页面是重复的。这极大的浪费了网络的带宽和影响了系统的效率。所以，重复内容检测变成了采集系统，特别是大型采集系统的重要组成部分。要采用的检测方法，根据系统的需要，从简单的段落匹配到复杂的相似度比较中选择。
2.2.4 url提取器
对于采集到的页面，经过重复内容检测后，需要分析其中的链接，并对链接进行必要的转换，这些任务由url提取器来完成。首先判别页面类型，对类型为“text、html、shtml和htm”等的页面进行分析链接。页面的类型可由应答头分析得出，有些www站点返回的应答信息格式不完整，此时须通过分析页面url中的文件扩展名来判别页面类型。需要分析的标记包括<a href=……>、<area href=……>、<base href=……>、<frame src=……>、<img src=……>、<body background=……>和<applet code=……>等。页面链接中给出的url可以是多种格式的，可能是完整的包括协议、站点和路径的，也可能是省略了部分内容的，或者是一个相对路径。为处理方便，一般先将其规格化成统一的格式。
2.2.5 meta信息获取器
这里所要获取的内容包括已采集页面的meta信息、anchor信息、页面的标题、页面的摘要等。获取它们的主要目的是力图在没有对页面内容语义信息进行理解的前提下，尽可能多的挖掘meta、结构等的语义信息，来为从这些页面中提取出来的url的好坏，给出一个度量。度量的结果传输到url处理器，用于排序。
2.2.6 语义信息解析器
根据采集策略的不同,有些采集器还有语义信息解析器。这里所说的语义信息解析就是指对文本内容建立简单的索引。因为它在一定程度上挖掘了页面内容的语义，所以叫做语义信息解析器。对于一些大型的信息采集器，比如alta vista，由于采集的信息量很大，对语义挖掘的深度要求较高，所以一般将页面语义挖掘与信息采集独立开来，而用专门的indexer等部件进行处理。对于一些轻量级的采集系统，比如基于用户个性化的采集，因为采集的信息量不大（这样语义信息解析就不太影响采集效率）和采集过程中更需要语义信息制导，所以它们也常用到语义信息解析器。
2.2.7 数据库
经过重复内容检测后的页面数据、提取出来的meta信息、主题和摘要等都要存入数据库，以备其他应用使用。比如，对于google这样的搜索引擎，这个数据库中的内容将用于建立索引。如果系统有语义信息解析器，则解析出来的内容也存入数据库。由于数据较多，所以在存入数据库之前，数据一般要进行压缩。
2.3 web信息采集面临的主要困难和相应的技术手段:
粗看起来，采集的过程似乎比较简单，但实际上，它却存在着许多技术上和工程上的挑战。在分析这些挑战之前，先看一下web的特点。
2.3.1 web的特点
web与传统的信息媒介相比，主要存在以下几个特点：1)信息容量的巨大性，在1998年7月，web上的静态文本大约有3亿5千万个，并且以每月600gb的速度增长[kahle 1997]；2)web的动态性，每天web中的内容和web的结构都在变化着；3)web的异构性，web中包含的文件类型各式各样，包括图像、图片、声音、文本以及script等；4)web页面的重复性，最近的研究表明，将近30%的页面是重复的；5)高链接性，平均每个页面有超过8个链接指向别的页面；6)多语种性，现在web上的页面语种超过了100个。这为web的有效采集，特别是为搜索引擎的采集提出了巨大的难题。
2.3.2 web采集面临的技术困难和相应手段
从技术角度看，挑战主要有以下几点：第一，web信息容量的巨大性使得采集器不可能采集到所有的web页面，而且很多采集系统也没有足够大的空间来存放采集到的所有页面。如何提高采集的效率，即在单位时间内采集到尽可能多的高质量页面，是采集系统面临的一个难题。目前，有五种页面质量高低的计算方法：1).similarity(根据页面和指导采集的问题之间的相似度)；2).backlink(根据这个页面在web图中的入度大小)；3).pagerank(根据指向它的所有页的平均权值之和,一页的平均权值定义为这页的权值除以这页的出度)；4).forwardlink(根据这个页面在web这个图中的出度的大小)，5).location(根据这个页面的位置信息)。cho中对比了宽度优先方法、backlink方法和pagerank方法[cho, molina & page 1999]，并根据试验比较得出pagerank方法最好。这是因为pagerank方法反映的是一种全局的页面质量分布，它能够较快的发现全局的高质量页面。
第二，并行性问题。页面的采集速度一直是影响采集器性能的重要原因。一方面，web中的页面数量非常庞大，另一方面，网络中的连接速度又非常缓慢，这客观上要求系统需要并行。然而，要并行又引入新的问题：1).重复性(overlap)，多个不同的采集器或采集线程在同时采集的时候增加了重复页面；2).质量问题(quality)，单个系统能够根据算法采集到全局最优的页面。而如果并行，每个采集线程只能看到局部页面，它能够采集到的页面质量有所下降；3).通信带宽代价（communication bandwidth），为了并行，各个采集线程之间不可避免的要有一些通信。一般来说，采集系统采用两种模式来并行：局域网并行模式(所有的采集线程都运行在同一个局域网内，它们之间通过高速的内连接进行通信)和分布式并行模式(采集系统被分布在地域上较远的internet上，通过网络进行远程通信)。在并行时，采集系统也可选用以下三种方式合作：1).独立方式，各个采集器之间独立的采集各自的页面，互不通信；2).动态分配方式，有一个中央协调器，动态的协调分配url给各个采集器；3).静态分配方式，将url按事先划分分配给各个采集器。对于静态分配方式，存在一种跨区链接(inter-link，指一个采集器在提取链接时遇到的不属于自己采集范围的链接)。难题在于跨区链接并不一定能被它所属于的采集器发现，如果本采集器采集了则可能重复采集，如果不采集则可能漏采。近期的研究工作针对这种情况比较了三种模式: 1).防火墙模式,完全不采集inter-link页面；2).交叉模式，采集遇到的inter-link页面；3).交换模式(exchange mode)当采集到inter-link，就将这些链接保存起来，积累到一定数量后传输给相应的采集器进行采集。实验结果和我们的直觉一样:交换模式最好：交换模式最好[cho 2001]。
第三,刷新问题。为了保持采集到的页面是最新的，采集系统不得不对已经采集过的页面进行周期性的更新。而随着web的爆炸性膨胀，这个问题几乎变成了不可逾越的鸿沟。最近的一项报告显示，甚至流行的web搜索引擎，页面刷新一次甚至持续数月[lawrence&giles 1999]。同时，这份报告也显示，14%的搜索引擎提供页面是无效的。cho试图用泊松过程(poisson process)来描述页面变化率，并研究和对比了三种页面刷新策略：固定顺序的刷新，随机刷新和纯随机刷新策略。直觉上，更多的刷新应该分配给更那些更新快的页面。但研究表明，用较高的频率刷新更新快的页面并不一定是明智之举，对各种页面采用相同的刷新周期效果更好，而效率最佳的点在这两种刷新策略中间。这是因为，过高频率的刷新更新快的页面，使得其它页面有较少的刷新机会，反而造成总体刷新质量下降[cho 2001]。
2.3.3 web采集面临的工程困难和相应手段
从工程角度看：第一，正如前面分析的，web中的信息是完全异构、混乱和无序的，文件格式各式各样，网络状况也随时间变化莫测。所有的这些不确定性因素，为系统实现带来了极大的困难。这就要求采集系统有完善的异常处理和故障恢复机制，充分考虑到实际网络环境中可能出现的各种情况。
第二，多线程与并行机制使系统变得非常复杂。在这种复杂的环境下，系统的许多瓶颈变得异常突出，并需要采用多种设计技巧来解决。比如说，对一个网站的采集不能过分集中，以防止造成网站负担过重，google中的页面采集就是同时采集多个站点。在google中，系统为每一个采集器都配了一个dns缓存服务器，以加快dns解析的速度。
2.4 采集系统实例
下面就以两个实际的采集系统为例来具体说明，它们即有一般采集器的共同特点，也有自己的特色。
2.4.1 mercator信息采集器的基本结构和工作过程
mercator信息采集器是一个由康柏研究中心研制的面向整个web的分布式多线程信息采集系统[heydon&najork 1999]。它的基本结构如下图2.2所示，采集步骤是从1)到8)不断循环。步骤1)就是从多个线程共享的url frontier中移出绝对路径的url来。绝对路径的url中指明了这个url采用什么方式下载。具体和协议相关接口的实现在protocol modules中。并且，用户可以通过设置文件来告诉系统装载哪些协议接口。
在步骤2)中,系统选择了相应的协议,通过了dns解析并从web上下载了页面，然后将页面放入3)rewindinputstream（ris）中，ris相当于一个缓存，能够多次快速的读内容。一旦文件被放进ris,这个工作线程就启动内容检测模块看是否此页面已经被采集过，这就是步骤4)。如果采集过，系统就抛弃此页并跳至步骤1)。
如果此页没有采集过，就进入步骤5)processing modules,在这里对页面进行初步的分析，比如提取标题、摘要和链接。缺省状况下，页面中的所有链接都被提取出来，并转换成绝对url。然后进行步骤6),也就是根据用户要求对url进行过滤(filtering)。如果url通过了过滤器，则检查此url是否已经在url待采集库中(步骤7)。如果此url没有，则将它加入到url frontier中,等着被选中进入下一轮循环(步骤8)。
图2.2 mercator信息采集器结构
2.4.2 天罗信息采集系统的基本结构和工作过程
天罗信息采集系统是在国家“863”计划下由曙光公司开发的智能导航系统的子系统。本采集系统最初的目标是面向整个web的信息采集，随着web服务向个性化主动服务等领域的拓展，本采集系统的后续版本在中科院计算所领域前沿青年基金资助下正在向基于主题的采集方向发展。
如图2.3所示，天罗web信息采集系统从功能上看可分为两个部分：采集器部分和控制部分，中间的竖立虚线将他们分开。采集器部分主要负责实际采集，它分为三个部分。1).站点采集。把整个web以站点为单位划分成若干个连通子图是合乎人们的浏览习惯的，并且也是利于存储的。天罗web信息采集系统的设计就是根据这一点，对web上的页面以站点为单位进行采集。2).页面采集。尽管系统从粗粒度上看，采集是以站点为单位的，但是从细粒度上讲，每次只采集一页。这个部分考虑的重点就是对采集每页相关的协议的处理和实时网上异常的处理。3).存储库，主要存储采集到的数据、站点结构信息以及相关的有用信息。
图2.3天罗信息采集系统结构
控制部分主要负责采集以外的协调、策略以及与应用的接口，它分为五个部分。1).采集系统设置，主要用于系统管理员对采集系统的控制，包括设置采集起点和采集策略。2).采集系统控制，这是采集系统最具有全局观念的一个子系统，它主要负责总体控制和其他各子系统之间的协调和连接,另外它还集中式的控制多个采集器并行。3).存储库，主要负责存储一致化处理后的各项数据以及在此基础上进行索引等处理的数据。4).采集策略处理，负责处理采集系统在理论上最难的一个部分——如何有效的采集和动态的刷新。5).安全开关，在实际应用系统中，采集器往往直接和web相连，而同时又与内部的应用服务器相连，如果不加安全处理，web对于应用服务器是非常危险的。为此，本采集系统设计了低成本高效率的安全开关。当与应用系统交换数据时，采集系统与web断开；当在web上采集数据时，采集系统与应用系统断开。这也是本采集系统的特色之一。图中的箭头描述了数据流向。
为了提高采集的效率，天罗web采集系统采用服务器(采集系统控制)/采集器的结构使采集系统具有很好的可扩展性。管理员可根据系统采集规模的变化动态地调整采集器的数量，在保证系统性能的前提下尽量减少系统开销，达到最佳的性能/价格比。而且在规模动态变化的过程中，系统能维持一致的管理和数据输出接口。
第三章 web信息采集的研究现状
目前，web信息采集技术的发展正如火如荼，在传统的web信息采集技术的基础上，又出现了许多轻型的各具特色的采集技术。我们根据国内外流行的看法，结合我们在这方面长期积累的实际经验，把web信息采集的发展方向分为以下几种：基于整个web的信息采集(scalable web crawling)，增量式web信息采集(incremental web crawling)，基于主题的web信息采集(focused web crawling)，基于用户个性化的web信息采集(customized web crawling)，基于agent的信息采集(agent based web crawling),迁移的信息采集(relocatable web crawling)，基于元搜索的信息采集(metasearch web crawling)。实际系统往往是以上几个采集技术的结合。下面分别予以介绍。
3.1 基于整个web的信息采集
这种信息采集在国外也常叫做scalable web crawling，是一种较传统的采集思想。主要是指目标为从一些种子url扩充到整个web的信息采集。这种信息采集主要是作为门户搜索引擎和大型的web服务提供商的数据收集部分。对于这类信息采集来说，由于采集的范围和数量都非常巨大，所以对采集速度和存储空间要求很高；由于目标是采集整个web，所以对采集页面的顺序要求相对较低；由于待刷新的页面太多，尽管并行很多的采集器，但仍需数周乃至数月的时间来刷新一次，而且，随着并行采集器数量的增加，整个系统能力的提高越来越小，稳定性却越来越低。但是，这类信息采集又不能没有，人们不光有个性化需求和具体主题的需求，还有许多广泛主题的需求，而由这类web信息采集器构建的搜索引擎，恰恰适合搜索广泛的主题。事实上，这类信息采集仍有很强的应用需求，目前在实际应用中占较为主流的地位。下面通过简要分析三个实例google[brin&page 1998][cho, molina &page 1999]、mercator[heydon&najork 1999]和internet archive[burner 1997]来进一步说明这类信息采集。
google crawler是一个分布式的基于整个web的采集器，主要在美国stanford大学用c/c++设计。它并没有采用多线程技术，而是采用异步i/o管理事件来实现并行。它有一个专门的url server 来为并行的多个采集器维护url队列。为了保持高速的获取页面，每个采集器一次同时打开大约300个连接。在使用4个采集器时，系统的峰值速度大约是每秒100页，相当于每秒大约600k的数据。由于dns解析压力很大，google为每个采集器分配一个dns cache，这样不需要在每次采集页面时都做一次dns解析。google还使用了许多算法对系统性能进行优化，最著名的就是pagerank算法。在权衡了时空代价后，google选用了zlib 压缩格式压缩采集到的数据。
康柏系统研究中心研究实现了mercator web crawler。与google不同，它主要使用java实现的，在并行机制上，则采用了多线程技术，一般情况下，每个采集器能够启动数百个线程。mercator也有一个单独的url处理器，用于收集和合并从采集到的页面中提取出来的url。它有一个ris部件，用于去除相同内容的页面，因此有较低的文件重复率8.5%。mercator的另一大特点就是可扩展性，例如扩展一种新的采集协议。设计者声称，在双533mhz cpu、2g内存和118g硬盘环境下，mercato采集速度是每秒112个文件。
internet archive 使用异步i/o技术来并行采集整个web，它的目标就是为整个web存档。为此，每个采集器被分配64个站点，同时每个站点的所有页面都被分配给同一个采集器。在提取链接时，如果提取出的链接仍属于这个采集器，就将这个链接放入相应的待采集队列里，否则将它存在log文件中，积累一段时间后，再按所属站点传输给相应的采集器。
3.2 增量式web信息采集:
这种信息采集在国外也常叫做incremental web crawling。传统上，web采集器根据自己的需要采集足量的信息后停止采集，当一段时间后这些数据过时后，它会重新采集一遍来代替原有的采集信息，这种采集器称作周期性web采集器(periodic web crawler)。而另外一种方法，对待旧的页面采用增量式更新，也就是说，采集器只需要采集新产生的或者已经发生变化的页面，而对于没有变化的页面不进行采集。理想状况中，已采集到的信息应该和web中的信息是一致的，然而实际上web的动态性、异构性和复杂决定了采集到的信息在相当短的时间内就可能过时，那种理想是不实现的，我们能够做的就是尽量逼近这种理想。和周期性信息采集相比，增量式信息采集能极大地减小数据采集量进而极大地减小采集时空开销，因此它成为实际采集系统的首选。前面所说的google、mercator和internet archive都是增量式信息采集系统。但是，增量式信息采集在减小时空开销的同时，却增加了算法的复杂性和难度，同时又面临新的难题，例如如何根据页面的变化快慢分配系统的采集能力。在最近的一项实验中[cho et al. 2000]，随机选择了270个站点(包括132个.com站点，78个.edu站点，30个站点和30个.gov站点)并下载了72000个页面，发现超过40%的.com页面每天变化，.net和.org变化适中，而.edu和.gov变化最为缓慢。ibm设计完成的信息采集器webfountain是一个典型的增量式系统[edwards et al. 2000]。它采用了一个优化模型来控制采集策略。这个模型没有对web页面变化的统计行为做任何假设，而是采用了一种适应性的方法，根据先前采集周期里采集到的结果的实际变化率进行调整。作者也提到为更新频率较快的页面提高刷新频率。
3.3 基于主题的web信息采集:
这种信息采集器在国外叫做focused crawler，是指选择性的搜寻那些与预先定义好的主题集相关页面的采集器，对它的研究现在比较热门。它也是本文所要讨论的重点，我们将在以后的章节里详细论述。在这里，先看看国际上流行的此类信息采集系统。
印度理工大学(iit)和ibm研究中心的研究人员开发了一个典型的基于主题的web信息采集器[chakrabarti et al. 1999]。它的主题集是用样本文件来描述的。为了达到采集时主题制导的目的，设计者设计了两个文本挖掘的部件来指导采集。一个是分类器(classifier),用于评价采集文本是否与主题相关。另一个是精炼器(distiller)，用于识别能够在较少的链接内就连接到大量相关页面的超文本节点。采集系统首先保存一个经典的主题分类（例如yahoo的主题分类），并且为每一个主题分类都保存若干个内容样本，用于详细的刻画这一类主题。用户在使用本采集器搜索与主题相关的页面时，必须在系统的主题分类树中先选择一个主题，用于指导采集。由于要选择和剪枝，采集速度并不太快，在双333mhz pii cpu，256m内从 scsi硬盘下，每个采集器的采集速度为每小时6000页。
aggarwal则提出了一种针对两个假设的基于主题的web信息采集方法[aggarwal et al. 2001]：1).linkage locality,即被相关于某一主题的页面链接到的页面趋向于拥有同一主题。 2).sibling locality,对于某个链接到某主题的页面，它所链接到的其它页面也趋向于拥有这个主题。这样，在采集器接到一个主题采集请求命令后，它就从自己保存的关于这个主题的起点出发，按照两个假设蔓延，并利用指向备选页面中的url结构以及其他一些meta信息使用统计学习的方法进行修剪，使采集的页面很快接近主题。
web上80%的内容是动态产生的，并且呈增长趋势[steve lawrence 1998]，而这些内容却几乎没有被采集下来。美国stanford大学的hidden web exposer project就是要建立一个采集这些动态页面的采集器[raghavan& garcia-molina 2000]。因为很多隐式页面要通过填写表单等人工手段才能获取，所以采集器在采集之前需要人工辅助来事先填好领域信息，然后进行基于主题的采集。尽管主题信息的填写工作较繁琐，但同一主题的信息结构较相似，只要用户填写一次基本上就可以实现自动采集了。
menczer则评价了三种关于基于主题采集的策略[menczer et al. 2001]：1).best first crawler(通过计算链接所在页面与主题的相似度来得到采集优先级)；2).pagerank(通过每25页计算一遍pagerank值来得到采集优先级，pagerank值计算方法前面已经说过)；3).infospiders（通过链接周围的文字，利用神经网络和遗传算法来得到采集优先级）。经过试验作者发现，bestfirst最好，infospiders次之，pagerank最差。一向被给予高度评价的pagerank算法之所以表现不佳，作者认为是它选出的高质量页面是基于广泛主题的，而对于特定主题来说页面的质量可能就不高了。
3.4 基于用户个性化的web信息采集
不同的用户对一个搜索引擎提交同一个检索词，他们期望的返回结果是不同的，然而搜索引擎却只能返回相同的检索结果，这显然不能完全满足用户的需要。为此，采集系统的设计者把目光投向了基于用户个性化的web信息采集(customized web crawling)。这是一种轻量级的采集系统，它的目标就是通过用户兴趣制导或与用户交互等灵话手段来采集信息。系统根据实际需要可以直接把采集结果提供给用户，也可以先存储起来等到以后再提供。这种个性化信息一般有两个来源，第一个是用户手工在系统提供的个性化设置页面里设置，这里主要考虑的问题是如何全面灵活简单的提供这种设置，使得用户的各种喜好都能够表达。第二个是系统自动获取，通过跟踪用户的浏览习惯和兴趣等。sphinx是一个java工具包组成的环境交互式信息采集器[miller&bharat 1998]。它是一个典型的此类采集系统，用户的个性化设置嵌在工作台里，并针对指定的站点进行个性化采集。[kamba 1995]中介绍了一种新闻的个性化采集，这是个性化和主题采集应用结合的一个实例。
3.5 基于agent的信息采集
随着智能agent技术的发展，agent与信息采集相结合的技术也逐渐热门起来，这种采集技术叫做agent based crawling。智能agent系统是指一种处于一定环境下包装的计算机系统，为了实现设计目的，它能够在该环境下灵活地自主地活动。它除了具有自治性(agent运行时不直接由人或其它东西控制，它对自己的行为和内部状态有一定的控制权)、社会能力(多个agent体之间信息交换和协作)、反应能力(对环境的感知和影响)和自发行为(agent的行为是自主的)，还具有一般人类所有的知识、信念、意图和承诺等心智状态,这使得智能agent系统具有人类的社会智能。它的这些特点使得它在面临诸如基于主题和用户个性化的采集时，更加方便灵活和适应力强。比如说在基于用户个性化的采集中，它能像人一样感知用户的兴趣变化，自主地灵活地智能地调整采集策略。
美国的爱荷华大学进行的arachnid研究项目就是这方面的典型代表。它主要通过模拟一个生态系统的发展和演变来设计web信息采集器infospiders[menzcer 1999]和[menczer&belew 1998]。系统的目标是从用户的角度在网上搜索最有效的页面。它的采集原理基本如下：以一个用户的书签作为采集起点，通过分析这些起点周围的小区域和链接关系来发现新的要采集的页面。它通过对采集到的页面是否真的跟采集前的相关性预期相符，来增加和减少能量，当能量很高时，还可以生出新的子树，而当能量过低时，它就死亡。它的一大好处是杜绝了过期页面。但缺点也较明显。因为它是临时到网上去搜索，而不是在已完成的索引上直接匹配，所以尽管搜索精确度甚至更好，速度却比较慢。因此，它的定位是作为门户搜索引擎的有效补充。
美国麻省理工学院的一个系统letizia是利用agent来辅助用户浏览web页面的辅助工具[lieberman 1995]。当用户通过一个浏览器浏览页面时，agent就自动跟踪了用户的浏览行为，用启发式方法来估计用户的兴趣，并根据用户当前位置，从网上采集满足当前感兴趣的页面推荐给用户。用户可以遵从这些推荐，也可以按着自己的方式浏览，而同时agent则不停地根据新的变化采集和推荐，推荐的内容紧跟当前用户的浏览页面。
美国stanford大学研究了一种基于学习agent的主题信息采集系统[balabanovic&shoham 1995]。它使用向量空间模型vsm和tf*idf来给发现的文本评分排序，并使用机器学习策略和用户反馈来修改启发式搜索。
3.6 迁移的信息采集
这种信息采集器也叫relocatable web crawler。在采集时，它并不像其他采集器在本地向web站点服务器发页面请求，而是将自己上载到它所要采集的服务器中，在当地进行采集，并将采集结果压缩后，回传到本地。这样做的一个明显优点是大量的节省了web资源，大量的剪裁工作将在被采集对象的服务器上完成。但明显的一个不利是采集器可能并不被被采集对象所信任，因为这样被采集站点会由于给访问者权限太大而易遭到病毒攻击。解决的办法是建立一种信任机制，采集器由权威的信任机构评估并授权。还有另一种方法，采集器先迁移到离被采集站点很近的地方实施采集，这种方法是迁移到被采集站点方法和不迁移方法的折衷。sphinx 信息采集器就是这种思路的尝试[miller&bharat 1998]。
3.7 基于元搜索的信息采集:
元搜索引擎（metasearch）的研究一直是搜索引擎研究的一个热点。它是这样一种搜索引擎系统，对用户提交的查询请求通过多个领域或门户搜索引擎搜索，并将结果整合后以统一的界面提交个用户。一般元搜索引擎并不保存web页面的索引文件，但对于一些复杂的元搜索引擎,它要保存为它服务的每个搜索引擎的信息特征，以便能够在用户查询到来后做出好的搜索引擎选择。作为搜索引擎先头部队的信息采集器，在元搜索引擎中有相当的退化，但仍为web采集的一个方向,叫做基于元搜索的信息采集(metacrawler)。
美国binghamton大学的研究者围绕一个元搜索引擎技术的难点：数据库选择问题进行了研究[zonghuan wu 2001]，并提出了一个解决上述问题的新方法。因为要借用其它搜索引擎的索引数据，所以叫做数据库选择。他们的方法是：就每个有代表性的问题对大量的领域搜索引擎排序，这有点像建立索引时的倒排表。当一个检索词来了后，通过相似度比较选择一个最接近的代表性问题，进而确定了要选用的搜索引擎。
美国华盛顿大学在metasearch方面的研究在[selberg&etzioni 1997]有详细的说明。作者认为，大多数搜索引擎对于同一个查询要求返回的结果很不相同，质量也参差不齐。试验发现，使用单独一个搜索引擎错过大约77%的相关页面[selberg&etzioni 1995]。所以，他们力图在提高查全率的同时，也力争利用单个搜索引擎在某一领域的优势提高平均查准率。
3.8 小结
随着人们对web服务的种类和质量要求越来越强烈，各种各样的信息采集系统也应运而生，并朝前不断发展。最初，人们希望能够设计出既大而全又质量好的信息采集系统(即基于整个web的信息采集)，这显然是一个非常困难的问题，因为两方面都要求必然造成两方面都不能做得很好。人们经过不断的努力和探索，从最初的web worm到现在的google,从基于词的语义信息理解到web链接结构信息挖掘，发展到了今天已经取得了令人瞩目的进步，优秀的基于整个web的采集器以及相关的搜索引擎，已经在很多方面为人们利用web信息提供了大量帮助。然而，随着人们对web服务的种类和质量要求越来越高，基于整个web的信息采集也越来越显得力不从心，一方面它们不得不为越来越庞大的数据提高采集速度、增加存储空间、优化采集算法，而一方面又越来越不能满足用户对个性化数据的需求，人们需要寻找新的出路。目前采用的基于词的语义信息理解显然不能准确把握整个文章的语义，而要上升到对句子甚至段落信息的理解却还有待于自然语言理解的大发展，现在这一方面困难重重；基于已有结构信息的挖掘(例如google的pagerank算法)也已基本达到饱和，很难有新的算法达到较大突破；而对于纷乱的web制定新的标准，减少不确定性以提高性能，这一方面的发展也不能寄予过高的期望；随着web服务逐渐向基于主题以及用户个性化的方向迈进、agent的技术发展、迁移式思想的出现，单纯的为了检索的信息采集技术必将向着基于主题以及个性化主动信息采集服务方向全方位拓展。因此，有必要开展基于主题的web信息采集技术的研究。
第四章 基于主题的web 信息采集基本问题研究
在本章里，我们主要围绕基于主题的web信息采集基本问题展开了研究，这主要包括主题的web信息采集的定义、优点、分类，主题页面在web上的分布特征以及相关性判别算法，后两者是本章的重点。它们为在下一章中提出我们设计的基于主题的web信息采集结构模型提供了必要的准备。
4.1 基于主题的web信息采集的定义
在web信息采集的大家庭中，有一类非常重要，它就是基于主题的web信息采集，在国外也叫做focused crawling。它主要是指选择性的搜寻那些与预先定义好的主题集相关的页面的采集行为。
4.2 基于主题的web信息采集的优点
和传统的基于整个web的信息采集相比，基于主题的web信息采集是一个新兴的领域，主要有以下几个优点：第一，从很大程度上，它缓解了信息采集开放性难题刷新问题所带来的弊端。整个web的实时性使得数据在采集到的同时就面临着过时的风险，为了降低这种风险，信息采集器必须不停的对采集过的信息重新采集已达到对数据的刷新。刷新问题就是指在对页面数据的刷新过程中，这种风险只能降低，不能消除。随着web的急速膨胀，传统的基于整个web的信息采集的刷新问题变得异常地尖锐。尽管人们不断的提高单机的性能，通过分布式增加并行能力，通过算法优化刷新策略，但是刷新问题还远不能令人满意。许多门户搜索引擎查新一次需要数周甚至数月的时间。selberg和etzioni在1995年的调查发现，通过internet中最常用的一些搜索引擎查询到的结果url中，14.9%的目标页面已经失效了[selberg &etzioni 1995]。而对于基于主题的信息采集，这个问题好处理的多。随着采集页面数量的极大降低，页面的刷新周期极大的变短，因此数据过时的风险也就极大的减小了。
第二，它极大的节省了资源和提高了资源的利用率。整个web上的信息是十分浩大的，想对web整个采集或完全镜像的采集器，先不说它们能否做到这一点，就其在采集过程中所使用的硬件资源和网络资源来说，花费是十分巨大的。事实上，许多采集到的页面信息很少被使用，这是一个极大的浪费。而基于主题的web信息采集就是在采集过程中对url根据需要有所剪枝。这种采集剪枝，不仅使剪枝掉的url数目远大于被采集的url数目，甚至差别是几个量级的，还使得剪枝后采集到的页面有较高的利用率。因此，这极大的节省了硬件和网络等资源以及提高了资源的利用率。
第三，它更灵活，更利于为用户服务。采集的目的就是为了服务于用户，对于每个用户来说，他们根本不关心整个web上的数据，而只是其中很小的一部分。事实上，这部分数据往往集中在很小的几个或者一个主题领域内。基于主题的web信息采集恰恰可以满足这些用户的需求，而且，由于采集的页面数量少，页面内容也更有针对性，所以能够更好的针对需要为用户提供服务。也正是由于采集的页面数量少，系统更加灵活。
第四，通过各个基于主题的web信息采集器的协作和共同努力，它可以提高整个web的页面采集覆盖率。随着www信息的爆炸性增长，信息采集的速度越来越不能满足实际应用的需要。最近的试验表明，即使大型的信息采集系统，它对web的覆盖率也只有30-40%。解决这一问题的直接办法是升级信息采集器的硬件，采用处理能力更强的计算机系统，然而这种方法的扩展性有限，性价比也不高。一个更好的解决放法是采用分布式方法来提高并行能力，但是并行不但增加了系统的开销和设计的复杂性，并且并行换来的效益随着并行采集器数目的增加而显著的减小。而基于主题的采集，由于采集的页面总数少，并且对于这个主题内的页面挖掘能力更强，所以和传统的基于整个web的信息采集器相比，它在这个主题内往往采集到更多更全面质量更好的页面。当多个主题采集器按照主题分类目录对主题页面进行分类采集和协同工作后，他们的综合采集页面对web的覆盖率也就更高了。
4.3 基于主题的web信息采集的分类
4.3.1 广泛主题和具体主题的web信息采集
按照采集主题的范围和规模，基于主题的web信息采集可分为广泛主题的web信息采集和具体主题的web信息采集。
广泛主题是指那些涵盖面较宽，并且和其他主题相比有较强的独立性的一类主题。广泛主题的web信息采集也称作领域web信息采集。用户在采集这类主题时，往往并没有太具体的要求。一般这类信息采集所需要采集的页面数量较多，为了达到较高的召回率，在进行url过滤的时候所设定的阈值较低、限制较宽，因此它的页面的内容相对于其它基于主题的web信息采集来说也相对较杂，采集页面与主题的平均相关度也较低。
与之相对应，具体的主题涵盖面较窄，因此意义也比较明确，采集页面的规模也较小。这类采集一般可直接服务于用户，为此，它在进行url过滤的时候所设定的阈值较高、限制较严。这类信息采集对用户来说，更加灵活，对每个用户有更强的针对性。在操作方式上，此类信息采集的设置有点像给搜索引擎提交查询词。
如果按照主题分类目录来划分它们二者的话，广泛主题往往集中在主题树的根结点附近，而具主题则集中在主题树的叶子节点附近。
4.3.2 固定主题和可变主题的web信息采集
按照采集时能否指定主题，基于主题的web信息采集分为固定主题的web信息采集和可变主题的web信息采集。
顾名思义，固定主题的web信息采集在采集前和采集的过程中都不能进行主题的变更。它一般是针对比较广泛的主题，并且这类主题要有较强的代表性和采集价值。，这类采集一般服务于领域搜索引擎，不直接服务于用户。通过领域搜索引擎的标引和加工，以类似于门户搜索引擎的服务方式提供给用户。它的页面内容比基于整个web信息采集的页面内容有强得多的主题特性，因此领域搜索引擎要比门户搜索引擎有更好的检索效果。
可变主题的web信息采集是指用户在采集前可设定采集主题、在采集过程中可改变主题的一种采集方式。这类采集往往设定的主题较具体，采集页面的规模也较小，提供给用户的操作方式比较灵活。另外，多个此类信息采集器进行合作，分别采集不同的主题，能够完成一些更高级和复杂的服务。
4.4 主题页面在web上的分布特征
整个web上的页面分布是杂乱无章的，但透过这个杂乱无章的表面，我们能否找到同一个主题在web上分布的一些规律呢？答案是肯定的。我们将这些分布规律总结为四个特性：hub特性、sibling/linkage locality特性、站点主题特性、tunnel特性。通过对它们的研究，我们希望能够发现一些在基于主题的采集过程中对无关url和页面过滤有用的规律。
4.4.1 hub特性
美国康奈尔大学的教授jon m. kleinberg发现web上存在大量的hub页面，这种页面不但含有许多outlink链接(指出链接)，并且这些链接趋向于相关同一个主题。也就是说，hub页面是指向相关主题页面的一个中心。另外，他还定义了权威页面(authority)的概念,即其它许多页面都认为相关于这一主题有价值的好页面。好的hub页面一般指向多个authority的页面，并且所指向的authority页面越权威hub页面的质量也越好；反过来，hub页面的质量越好，它所指向的每个页面也趋向于越权威。根据这个思想，他还提出了hub/authority 算法，这个算法我们将在后面的章节中介绍。这个算法对于计算广泛的和概念模糊的主题效果不错，但由于算法会产生概念扩散现象，使得计算后的中心页面和权威页面不太适合具体主题。
4.4.2 sibling/linkage locality特性
在hub特性的基础上，人们又提出了sibling/linkage locality特性[aggarwal et al. 2001]。1).linkage locality,即页面趋向于拥有链接到它的页面的页面主题；2).sibling locality,对于链接到某主题页面的页面，它所链接到的其它页面也趋向于拥有这个主题。这实际上是hub特性的变形，主要是从页面的设计者设计的角度考虑的。一个页面的设计者趋向于把本页面指向于与本页面相关的其他页面。
4.4.3 站点主题特性
我们发现，一个站点趋向于说明一个或几个主题，并且那些说明每个主题的页面较紧密地在此站点内部链接成团，而各个主题团之间却链接较少。我们认为，这主要与网站的设计者的设计思路有关。每个网站在设计时都有目标，而这种目标往往就集中在一个或几个主题中。而网站的浏览者往往也有一定的目的性，这个目的性一般体现在用户趋向于浏览同一主题的页面。为了满足浏览者的这一需求,网站设计者需要将相关内容紧密地链接在一起。
为了发现和研究站点内页面的主题团特性，余智华对站点结构进行了分析[余智华 1999]，他通过基于关键词的向量空间模型算法为每个页面分类，并在站点内部结构特征的基础上，对站点页面树按照自底向上进行主题聚类，这样一个站点所要说明的一个主题或多个主题就确定了(如果聚为一个类，说明站点只有一个主题，如果聚为多个类，则说明站点有多个主题)。显然，聚的每一个类就是站点内页面的一个主题团。在聚类过程中，他要区别每个链接和页面对页面树结构的贡献，为此他为站点定义了两种结构(物理结构合逻辑结构)，并且把站点内的链接分为六类(下行链、上行链、水平链、交叉链、外向链、框架链)，把站点内的页面分为四类(主页、索引页面、内容页面、参考页面)，他为每一类链接和页面在聚类过程中赋予不同的权重。我们的试验也证明了站点中存在着许多主题页面团，或者说许多中心页面。
4.4.4 tunnel特性
在web中还有一类现象，就是尽管存在很多主题页面团，但是在这些页面团之间，往往需要经过较多的无关链接才能够到达。这些无关链接就想一个长长的隧道一样，连接着两个主题团，因此我们也把这种现象叫做“隧道现象”。在基于主题的页面采集过程中，tunnel的存在极大地影响着采集的质量。为了提高采集页面的准确率，我们需要提高url与主题相关性判定以及页面与主题相关性判定的阈值，而阈值的提高将过滤掉大量的tunnel，使得采集系统很可能丢失tunnel另一端的主题团，进而影响了查全率(或者说资源发现率)。反过来，为了提高查全率，就得大量发现tunnel,就得降低url与主题相关性判定以及页面与主题相关性判定的阈值，但是阈值的降低使得在得到tunnel的同时，也混进了大量的其它无关页面，从而大大降低了页面的准确率。这是一个两难问题，但关键还是不能有效地区别tunnel和其它大量无关页面，事实上两个主题团之间的隧道数也较少。为此，我们这样设计算法：判断某个链接和页面与主题的相关性低于阈值时，给它一个概率p不被剪枝，为了提高tunnel的发现率，这个概率p值一般要大于tunnel出现的估计概率值；另一方面，我们对链接和页面相关性判定的阈值进行动态的调整，当目前采集页面的准确率较高时，将阈值变低，而当目前采集页面的准确率较低时，将阈值变高，以使得能够有效的在查全率和查准率之间有一个有效的折衷。详细的算法在url与主题的性关性判定那一章里介绍。
4.4.5 四个特性的关系
web中的页面对于主题来说是杂乱的，但也存在一些规律。hub特性说明了主题容易成团出现的现象，linkage/sibling locality特性进一步对成团的特征有所扩展，站点主题特性说明了主题团所在的位置(即大部分分布于站点的内部)，而tunnel特征说明了主题团在web 上的分布并不稠密，并且由较少的链接和tunnel连接。
4.5 相关性判别算法研究
基于主题的web采集系统最大的特点就是在采集的同时要对待采集的url进行剪枝、对已经采集的页面进行过滤，而做这些事情的核心问题就是页面、url与主题的相关性判别问题，为此，我们在这里对于相关性判别算法进行了详细的研究，它主要分为以下四个大类：1).根据元数据的判定；2).根据扩展元数据的判定；3)根据链接分析的判定；4).根据页面内容语义判定。
4.5.1 根据元数据的判定(元数据演算)
4.5.1.1 元数据演算基本概念
元数据（metadata）是指关于数据的数据，关于信息的信息 [marchiori 1998]。人们在研究web信息检索的早期就发现，利用元数据(metadata)来增加html的结构特征对web信息检索有帮助。因此，html 规范从2.0版本开始引入了<meta>这一tag [html30 1995][html32 1997]，用于为web页面标注metadata，一般形式为：<meta name=“...” content=“...”>。
例如:
<html>
<head>
<title>my interests</title>
<meta name=”author” content=”li shengtao”>
< meta name =”description” content =”i love basketball game”>
< meta name =”keyword” content =”basketball,game”>
</head>
<body>
…
</body>
</html>
图4.1 html中的元信息标注
图4.1表示该页面的作者为li shengtao，关键词是basketball和game,而对本页面的描述是”i love basketball game”。这种元数据显然对本页面的主题有相当大的说明作用。
4.5.1.2 演算机制
元数据演算（又称为meta演算）最初是海量信息、多媒体数据ir等中的技术, 今天日益成为web研究中的重要一支，并成为基于主题的web信息采集时剪枝的一个依据。meta演算的核心思想是构造一个比原始被标引数据结构化程度更好、更便于计算的中间层次（元信息层次），在此基础上提供各种更加优化智能的服务。meta演算以web的异构性作为突破口，试图借助元信息引入结构性和有序性，从而提供更优质的检索服务。它的机制主要是标引和演算，两部分相互配合共同发挥作用。[冯国珍 2001]
4.5.1.3 标引
标引的目的是为演算提供比原始数据更加结构化的标引数据。标引工作的前提是制定一套标引标准，分为表现方式和标引工作方法两部分。表现方式包括标引数据的格式、属性、取值范围、标准值、存放规范等；标引方法体现为对标引属性和标准用值的含义解释，取值规定，和具体流程等。
标引工作的进行过程是为被标引对象即原始数据确定适用的标引属性并给出具体取值。这必须在理解的基础上进行，是理解归纳的工作。在web这一应用环境中，标引的目的具体地包括消减自然语言的模糊性、歧意性，以及降维等，总之是在自然语言的基础上改善规范化和形式化程度。
4.5.1.4 演算
metadata演算的目的是为了提供各种服务，因而随着需求的不同具体计算方法千差万别，但我们可以将metadata演算的基本模式抽象为：以结构化程度更高的标引数据为对象，结合用户信息进行深度演算。metadata演算一般不是工程或科学计算，而是智能领域的服务，如主动推送信息，信息自动分类，信息检索，主题制导采集等，强调对原始数据的归纳理解和人机交互的方式[冯国珍 2001]。
4.5.1.5 元数据的层次标准
标引的目的是构造比原始数据更加结构化、更加有序，便于计算的中间层，因此标引必须遵循一致标准。标准的制定是有关meta演算的国际组织的一项重要工作内容。meta标准可以分为以下三个层次：
l 元信息格式。即元信息书写格式。html和xml都支持在页面中直接标注元信息， xml对元信息的页面标注支持方式结合rdf标注定义。[[rdf10 1999]]
l 元信息标准取值。这定义的是有哪些属性的元信息，各属性的标准命名；每个属性有那些有效取值，每个取值用什么标准符号表示。
l 演算模型。即基于元信息这一中间层次向上提供服务的计算模型。
为web页面制定元信息标准是一项十分困难的任务，因为web所涉及的学科领域，语种，国家地域，文体都非常多，目前meta标准在第一层次基本取得成功，html和xml页面中标注元信息的格式得到了各方的承认和执行。再向上，在第二层次，只就各种页面都共有的最基本属性的确定和命名制定了比较广泛接受的标准，即doublin core(简称dc)[dc]，该标准定义了15个辅助web ir的标准属性，如“author”, “abstract”, “date”等。进一步，虽然各学科专有属性的确定以及各属性有效范围的确定存在不少提案，但没有获得普遍接受形式的标准。至于meta演算，由于应用于不同目的时相应采用不同的算法和技术，因此无法抽象出统一的演算模型[冯国珍 2001]。
4.5.1.6 基于主题的信息采集对metadata 演算的利用
通过以上分析我们发现，metadata演算的一套思路和方法，都是为了更加有效地支持web检索而产生的，基于主题的信息采集的本质就是将搜索引擎技术里原来放在采集数据之后的一些检索技术应用到了采集数据的过程中，因此metadata演算对于基于主题的信息采集时的url过滤和页面过滤是有用的。事实上，已经有一些系统尝试使用meta数据来进行url预测。但是，元数据演算却有一个致命的病源：这种减轻web上信息的弱结构性和异构性的方法，需要人们事先按照标准书写html页面，这增加了人们的页面写作代价，而人们在习惯了原来简洁的方式后，很难遵从元数据标准。同时，对于不同的领域，ontology标准的制定也有所不同，实施起来也困难重重。因此，像许多搜索引擎甚至领域搜索引擎一样，它在主题采集领域内应用并不多。因此，在我们的系统中，并没有利用任何的元数据。当然，这并不说明此类方法没有前途，随着web的新一代语言xml的发展，meta演算也逐渐有了新的发展空间，但是，它需要人们对增加页面结构信息的渴望付诸行动，也就是共同遵守metadata书写协议，这需要时间。
4.5.2 根据扩展元数据的判定
4.5.2.1 基本概念
尽管目前元数据演算并不理想，人们却发现利用其它html标记anchor等信息能够有效的指导检索和基于主题的信息采集。我们把这些标记信息统称为html扩展元数据，相应的计算叫做扩展元数据演算。
4.5.2.2 html扩展元数据
在html页面中，主要有4种超链接：1).anchor(<a>) tags；2).image(<img>) tags；3).map and area tags；4). frame and iframe tags。
archor标记是最常用的，主要包括name，title，alt，on-mouse-over和href等几种属性。而image标记则包括name，alt，src，dynsrc，lowsrc，onabort，onload和onerror等几种属性。对于map和area标记，它们的属性与anchor标记基本相同。frame和iframe一般与frameset一起使用，共同对网页进行分割。它们主要包括accesskey，align，application，bgcolor，frameborder，language，marginwidth，name，scrolling，src，style和title等属性。
如果把页面看作点，这些超链接看作边，则web构成一个有向图。直觉上，这些链接所含的信息对页面的语义有重要的解释作用。因此，我们对主要的链接属性作了分析。
4.5.2.3 html扩展元数据类型在web中的分布
我们研究了一个超过10000页的页面集，目的是了解在web中，各个扩展元数据类型所占的比例。这个页面集合是通过天罗信息采集系统按照随机给定的种子页面集采集的。所有的页面共包含了超过90000个超链接，这些链接中即包含内部链接(此链接所指向的页面仍然在这个页面集中)又包含外部页面(此链接所指向的页面不在这个页面集中)。
分布
类型
链接比例
页面比例
href
86%
89%
anchor text
74%
78%
surrounding text
35%
52%
name
12%
19%
onmouseover
5.3%
9.6%
src
1.7%
4.2%
title
0.8%
2.3%
image text
0.5%
1.4%
map & area text
0.1%
0.3%
frame text
0
0
图4.2 扩展元数据类型在web中的分布
在图4.2中，列出了几种有代表性的html扩展元数据类型，它既有超链接的属性，也有超链接标记的文字。链接比例主要是指在所有的链接中，含某种html扩展元数据类型的比重(即用所有含此扩展元数据类型的链接数比上所有的链接数)，链接比例实际刻画的是一个链接中含某种扩展元数据类型的可能性。页面比例是指在所有的页面中，含某种html扩展元数据类型的比重(即用所有含此扩展元数据类型的页面数比上所有的页面数)，页面比例实际刻画的是一个页面中含某种扩展元数据类型的可能性。
因为一个链接或者一个页面并不只含有一种html扩展元数据类型，所以，所有类型的链接比例和页面比例分别加起来都超过了100% 。另外，由于一个页面中通常包含多个链接，所以页面比例一般都要比链接比例高。
试验数据显示，对于链接比例和页面比例来说，类型都是按href，anchortext，surrounding text，name，onmouseover，src，title，image text，map & area text和frame text降序排列的。这个排列顺序说明了整个web中的页面和链接中html扩展元数据类型使用的比例。因此，我们在下面的算法中只要关注几个比例较高的扩展元数据类型，就能够把握整个扩展元数据对本这面中链接所指向的页面主题的预测。
4.5.2.4 基于html扩展元数据类型的判定算法
这些算法是利用链接的扩展元数据来为每一个链接计算权值，在进行基于主题的信息采集时，优先采集权值高的链接，并对权值较低的链接进行剔除。整个扩展元数据类型可以分为3个大类：1).url（包括href，onmouseover，src等）；2).text(包括anchor text，image text，map&area text，frame text和surrounding text等)；3)title(包括title，name等)。根据这3个大类，我们设计了算法。这些算法包含url启发式算法(url heuristics or uh)、text启发式算法(text heuristics or teh)、title启发式算法(title heuristics or tih)、扩展元数据启发式算法(all metadata heuristics or amh)、相关性权重算法(relevance weighting or rw)和有提升的相关性权重算法(relevance weighting with boosting or rwb)[ysh 2000]。
4.5.2.4.1 url启发式算法(url heuristics or uh)
在web中，如果一个url中包含某个主题词，则这个url所指向的页面很可能是跟这个主题词密切相关的。比如这个url包含的内容就很可能是关于basketball的。因此我们定义计算公式：
公式4.1
直觉上，根据这个公式计算的值 如果为1，则这个链接所指向的页面与主题相关的准确性很高，但算的值 如果为0，这个链接所指向的页面与主题无关的准确性并不高。也就是说此算法给许多实际相关的页面并没有赋权值1。
4.5.2.4.2 text启发式算法(text heuristics or teh)
在web中，如果anchor text，image text，map&area text，frame text或surrounding text等中包含某个主题词，则这个url所指向的页面很可能是跟这个主题词密切相关的。比如<a href="content1.htm" >科研</a>包含的内容就很可能是关于“科研”。因此我们定义计算公式：
公式4.2
url的text指的就是此链接的anchor text，image text，map&area text，frame text或surrounding text，显然，在一个链接中，这些text是不可能同时出现的。直觉上，同url启发式算法类似，根据这个公式计算的值 如果为1，则这个链接所指向的页面与主题相关的准确性很高，但算的值 如果为0，这个链接所指向的页面与主题无关的准确性并不高。不过与url启发式算法相比，它没有赋权值1的相关与主题的页面要少一些。
4.5.2.4.3 title启发式算法(title heuristics or tih)
在web中，如果一个链接中的title包含某个主题词，则这个url所指向的页面很可能是跟这个主题词密切相关的。比如<a href="; title="me scuba diving">me scuba diving last summer</a>这个url中，title包含的内容me scuba diving就很可能是关于这个url所指向的页面的内容。因此我们定义计算公式：
公式4.3
4.5.2.4.4 扩展元数据启发式算法(all metadata heuristics or amh)
将所有的扩展元数据综合在一起，就得到扩展元数据启发式算法公式：
公式4.4
其中a，b，c为3个大于等于零小于等于一的常数，用于控制每类扩展元数据在整体中的权重。显然，0 1。
4.5.2.4.5 相关性权重算法(relevance weighting or rw)
另一种综合所有的扩展元数据来计算权重的公式如下：
公式4.5
其中，m(url)指与此url相关的所有扩展元数据集合， 是指扩展元数据中的一个词与主题的相关度。c为用户设定的相关性阈值。此方法与amh算法最大的不同在于相关度的计算。amh方法是看扩展元数据中是否包含主题词或者主题词的同义词，这样会漏掉许多相关页面；而rw方法则是看扩展元数据中词与主题词之间的相似度，同义词之间的相似度100%，近义词之间的相似度50%~100%,远义词之间的相似度0%~50%，这样大大降低了漏判相关页面的可能性，同时也增加了错判相关页面(不相关的页面判断为相关页面)的可能性，它的相关与否是通过阈值来决定的(大于等于阈值为相关，小于阈值为不相关)。另外，rw算法需要增加一个词语相关性词库。
4.5.2.4.6 有提升的相关性权重算法(rwb)
公式4.6
在web中，有时在某两个相关于主题的页面之间会有若干个不相关于主题的页面存在，我们把这种现象称为“隧道现象”。这样在采集到前面一个相关于主题的页面时，根据rw算法很容易将隧道及隧道后面的相关于主题的页面抛弃掉。为了减少这种因为“隧道现象”而漏采相关于主题页面的损失，对rw算法进行扩展，产生了有提升的相关性权重算法rwb公式4.6。其中t(url)表示包含这个url的文本，t指文本中的每个词，c与前面一样，为用户设定的相关性阈值，d为用户设定的提升阈值。p1，p2为随机变量，它们在0和1之间变化。
它的原理就是当一个链接url的 值小于相关性阈值c时，随机产生一个提升因子p1，当p1大于等于提升阈值d时，此url就获得了一个重新评判相关性的机会，这次评判不只是用扩展元数据，而是用包含此url的整个页面内容。当重新评判的值大于相关性阈值c时，则用此值，表明这个url链接到的页面是相关的。如果重新评判的值仍然小于相关性阈值c，则给第三次机会，其值等于随机产生的变量p2，由于p2可能大于相关性阈值c，所以此url链接到的页面仍有可能被判断为相关的。这两次机会减少了rw算法的漏判(相关的页面被判断为不相关)和对“隧道现象”的错判，但同时也增加了相关性页面的误判(不相关的页面被判断为相关)。rwb算法的另一大优点就是解决了“停滞现象”。它总能找到相关页页面，而不因为没有相关页面采集停滞。
4.5.3 根据页面间链接分析的判断
web是基于internet的超文本（hypertext）系统，超文本系统与普通文档信息库的最大区别就在于前者中存在着大量的超链接。研究表明，利用web中丰富的超链接（hyperlink）信息，可以挖掘出web中许多重要的信息，这些信息对进一步理解超文本语义以及提供给用户更优质的服务有相当大的帮助。我们把这些研究超链接的工作称为链接分析，或叫做结构分析（structure analysis）。
链接分析的研究思路基于这样一个假设：即把超链接看作是对它所指向的页面的赞许[chakrabarti 1999]。在这样的假设之下，当页面a通过超链接指向页面b时说明两点：1).页面b与页面a的主题是有关的；2).页面b是质量较好值得关注的页面。单个链接并不是完全可靠可价值判断，因为超链接中也有纯粹起导航作用的（如“主页”，“下一页”），或者是广告链接，或表示不赞同（“我不同意这个观点”），或者是为了某种目的的欺骗性链接。不过，从宏观总体上来看，web上整个链接集合所反映的情况则是比较可靠和准确的，因为不良链接的整体效应远没有重要链接的整体效应强。当然，为了有效和准确的评估链接，在进行具体的算法分析之前需要识别和去除 “噪音”链接，这也是许多链接分析算法的共同特点。
如果将页面看作顶点，链接看作有向边，整个web就可以看作是一个有向图，称为web图（web graph），可以用复杂网络理论来进行研究和分析。在上述背景下，通过链接对web的研究可以分为以下三种类型：1).对web宏观性质的研究，比如说通过每个页面的出度和入度数来研究web中团的直径和web的宏观结构。这类研究往往用生态学（ecology）和社会学（sociology）的规律来来揭示web的发展。2).对web中单个页面的性质的研究。就像经济社会一样，有宏观问题，也有微观问题，web中的每个页面的作用是不相同的，有些页面非常重要和非常有权威，很多人都关注它，而有些页面则是垃圾，除了浪费被骗人的时间外，几乎没有任何存在的意义。现在比较好的计算页面重要程度的方法为pagerank算法和authorities/hubs算法，我们将在下面的章节中详细介绍。事实上，对web中单个页面的性质的研究非常使用，许多搜索引擎都采用了pagerank算法和authorities/hubs算法，以提高检索结果的准确性。3).对web隐藏信息的挖掘。现在，仍然有许多可用的web信息没有被挖掘出来，比如说有关共同话题的页面“社区”的问题[kumar (1) 1999] [kumar(2) 1999] [mendelzon 1995] [mendelzon 1997]，这些问题的解决有待于对web隐藏信息的进一步挖掘。
4.5.3.1 相关度和重要度
4.5.3.1.1 相关度
在搜索引擎技术中，相关度是个重要的概念。它描述了检索结果和检索请求之间的相关程度。相关度的计算方法有很多，但每一种方法基本上都是定量地计算检索请求与检索结果之间的语义关联程度，并且根据这种关联程度的数值高低排列搜索引擎返回给用户的结果。与之类似，基于主题的web信息采集的相关度是指页面或链接和主题之间在语义上的相互关联程度。
事实上，搜索引擎的这种排序后的返回结果并不令人满意。原因除了由于相关度计算方法的误差导致的排序错误外，还主要有一点：相关度不太高的页面不一定质量不高，相关度很高的页面不一定有高的质量。比如，一个文本对于一个主题来说，可能并太相关，但却出自一个权威作家之手，它有相当高的有用信息量；而另一个文本对于这个主题可能是非常相关的，因为它讨论的确实是这个主题，但是，这个文本由于出自一个初学者之手，只包含很少的有用信息量；更有甚者，一个质量较差的网页的作者，由于了解搜索引擎的工作方式，利用在网页中大量重复重要关键字的做法，提高它在搜索引擎检索中的相关度。实际上，用户需要的不只是语义上最相关的页面，而且是用途上质量高的页面，也就是说，是相关度和质量因素综合较高的页面。为此，信息检索的研究者们提出了另一个重要的衡量指标——重要度。
与信息检索情况类似，基于主题的web信息采集在进行主题相关性判定时也面临两个衡量指标。需要最先采集的链接，一方面，要在语义上与主题十分相关，另一方面，它要有较高的权威性和质量。这种权威性和质量往往能够使得采集到页面具有较大的有用性和较高的发现其它高相关度页面群的能力。我们在评价基于主题的web信息采集系统url预测方法时，也提出了另一个衡量指标——重要度。
4.5.3.1.2 重要度的概念
在信息检索中，重要度定义为：检索结果中，某文本的相对重要程度[杨志峰 2001]。我们在此处对重要度进行扩展：在一个文本集合中，某文本的相对重要程度。重要度刻画的是一篇文本实际的质量和有用性，相关度则刻画一篇文本和一个主题或者查询在语义方面的相联程度。尽管从统计概念的角度说，它们之间有较强的相关性(也就是说，统计上页面表现出来的规律是：重要度高的页面很可能相关度也高，反之，相关度高的页面很可能重要度也高)，但从实际意义上看它们并无太大联系，只是从两个不同的角度对本页面的评价。一个不太恰当的比喻是马克思对商品的看法：商品是价值和使用价值的统一体。在这里，我把相关度比作价值，重要度比作使用价值，二者相关，但也有很大的不同。
计算页面相关性的方法丝毫不能评估页面的重要性，那么我们如何得到对页面重要性的评估呢？链接分析给我们指明了道路。事实上，整个web上的指向页面的链接数恰恰反映了页面的可用程度和质量，也就是页面的重要度。如果一个页面质量好或可用程度高，那么就会有很多页面指向它，如果一个页面不好或可用程度低，就只有很少的页面指向它。这说明链接关系不仅仅反映了页面的重要度，还因为排除了个别用户或临时行为的干扰而使得这种重要度有较强的可信度。
因此人们用链接分析算法来评估页面的重要度，流行的算法有pagerank和authorities/hubs算法，在后文我们设计的基于主题的ipagerank算法，就利用了重要度的概念。
4.5.3.2 pagerank算法
pagerank是著名搜索引擎google的一个重要检索算法，它有效的帮助搜索引擎识别那些重要的页面并且将它们排在检索结果的前列。google是美国斯坦福大学计算机科学系研究开发的一个大型搜索引擎。它的设计目标，是提供千万页面级的搜索引擎，每天可以应付数以百万计的查询请求，并且，最重要的是提供了相对令人满意的检索结果。
4.5.3.2.1 pagerank函数定义
world wide web上的无数页面互相链接，构成了一个巨大的链接有向图。也许是受论文引用排名的启发，google的设计者们发现这个有向图中包含了非常有用的引用信息，而这种资源以前从未被人注意过。
设计者的思路是：被别人大量引用(也就是被链接)的网页，一定是好网页。从这个观点出发，他们构造了以下的基本公式：
给定一个网页a，假设指向它的网页有t1，t2，…，tn。令c(a)为从a出发指向其它网页的链接数目，pr(a)为a的pagerank，d为衰减因子(通常设成0.85)，则有
公式4.7
设计者声称，pr(a)可以用简单的迭代算法进行计算；在一台中等规模的工作站上，2600万个网页的pr函数值可以在几小时内完成。
4.5.3.2.2 pagerank的直观解释
假设web上有一个随机的浏览者，从一个任意给定的页面出发，从来不执行“back”操作，按照页面上的链接前进，我们假设浏览者选择本页中任意一个链接前进的概率是相等的。在每一个页面，浏览者都有可能不再对本页面的链接感兴趣，从而随机选择一个新的页面开始新的浏览。这个离开的可能性设为d。这样，pagerank(即函数pr(a))就是它访问到本页面a的概率。因为用户是趋向于浏览重要页面的，所以这个概率就反映了此页面的重要程度。从直观上看，如果有很多页面指向一个页面，那么这个页面的pagerank就会比较高；如果有pagerank很高的页面指向它，这个页面的pagerank也会很高。这样，从“随机浏览者”模型出发的pagerank函数就在直观上同web上的实际情形相对应了。
4.5.3.2.3 对pagerank公式的修正
从随机浏览者解释思路看，公式8.7的形式是不准确的。有人认为应该修正为以下形式[杨志峰 2001]：
公式4.8
公式中，(1-d)(pr(ti)/c(ti))代表随机浏览者从页面ti进入页面a的概率，所有概率值相加得到随机浏览者从某个链接进入页面a的概率；d/(ctotal-1)代表随机浏览者离开当前页面，随机开始一个新页面，从而选中页面a的概率。这两个概率相加，即得到进入页面a的总概率。
因为d/(ctotal-1)约等于0，所以我们认为公式4.7中的d并不表示随机浏览者离开当前页面的选择一个新页的概率，而只是起到调高pr(a)值以便计算的作用，实际公式中的d/(ctotal-1)由于为0已被省略了。
4.5.3.3 权威中心页面算法(authorities/hubs)
4.5.3.3.1背景
该算法主要在ibm的almaden研究开发中心研制的clever系统中实践和应用。他们认为，web页面的数量正呈指数形增长，但人们可以接受的信息数量几乎保持不变。因此，没有必要把所有的页面都进行索引、分类以供检索。他们的目标是主题提取(topic distillation)：给定一个覆盖面比较广的主题，筛选出这个主题下面质量最高的一小部分web页面。
clever系统把链接分析的深度又提高了一层。在这个系统中，首次提出了两个重要的概念：hubs和authorities。从这两个概念的名称可以推想到，authorities是重要的页面，hubs就是指向众多重要页面的中心点。
hubs和authorities之间是相互加强的关系。一个好的hub必然指向许多好的authorities，一个好的authorities必然被许多好的hub链接。当然，一个页面可以同时是hub和authorities。
4.5.3.3.2 权威中心页面算法(authorities/hubs)
下面是clever算法的示意性算法描述。
1. 用户给定一个查询以后，clever把它提交给一个通用的基于关键字查询技术的搜索引擎，例如altavista。从这个搜索引擎返回的结果称为基本集(initial set)。基本集不超过200页。
2. 向基本集中增加页面。被增加的页面必须或者是基本集中的页面所链接的页面，或者是它们链接到基本集中的页面。扩展后的页面集合称为根集(root set)。
3. 对根集中的每个页面p，赋给两个权值：a(p)，代表authority权值；h(p)，代表hub权值。它们初始值设为1。
4. 迭代计算每个页面的权值。
a) 对于页面p，令 ，其中qi为页面p链接的页面。
b) 对于页面p，令 ，其中ri是链接到页面p的页面。
5. 重复执行若干次迭代，每次迭代后进行规格化。
最终，取a(p)最高的页面为最好的authorities页面，取h(p)最高的页面为最好的hubs页面，每个页面的authority值就是这个页面的重要度。从算法中我们可以得知：根据authorities/hubs算法得到的权威页面是基于主题的，也就是说得到的权威页面是这个主题的权威页面。但由于根集中扩展进了许多主题相关性较低的页面和算法初始化各个页面的authorities值相同(都为1)，这个算法一般只适用于较广泛的主题。
4.5.4 根据页面语义信息的判定
最好的判断url和页面与主题的相关性方法还是要基于语义的理解，尽管这样做往往要花费更高的时空代价。目前，判断文本和主题相关性的方法仍然是基于关键词的，主要有以下几种方法：全文本扫描，布尔模型，扩展布尔模型，向量空间模型，概率模型。它们都是ir领域里经典方法。
4.5.4.1 全文本扫描
对于检索来说，要检查某个检索串的位置，最简单有效的办法恐怕是全文检索，也就是从头到尾扫描手中掌握的文本，检查这些串是否存在于其中。相应地，要判定是否页面与主题相关，最简单的方法也是全文扫描，在进行分词、去除停用词、词根还原（stemming）等简单的预处理之后，看看主题中的关键词是否都在本页面中出现，如果出现则相关，否则不相关，出现的频率越高，则相关度越大。
如果系统支持带正则表达式的查询，那么情况会复杂一些，需要判断文本中的字符串是否符合指定的模式。一般来说，可以构造一个和正则表达式对应的有限自动机，用它检测字符串是否满足要求。
全文本扫描的优点，在于这种方法非常简单，不需要预先对文本进行处理，不需要耗费空间存储索引，自然也不需要花代价维护索引。它的缺点在于，这是一种非常低效的方法，任何字符串的查找都要遍历所有的文本。不仅响应时间太长，而且极其耗费cpu时间和磁盘io时间。所以不适合大规模应用。但是，如果数据量不大，全文本扫描不失为一种有效的简便方法。
4.5.4.2 布尔逻辑模型
该模型构成了几乎所有信息检索和数据库系统的基础，直到今天仍然如此。采用这种模型的检索系统，用户查询词用布尔操作符“与”（and）、“或”（or）、“非”（not）进行连接，系统则返回满足上述词项组合的文档[cooper 1988]。对于判定页面与主题的相关性来说，将主题表示成若干个关键词并用布尔操作符相连，然后与页面进行相关性判定，一般可采用全文扫描的方法。
4.5.4.3 扩展布尔模型
图4.3 p-norm模型
经典的布尔逻辑模型的最大缺点是只有0和1，没有ranking。也就是说只要整个布尔表达式中只要有一处不符合，则不相关；都符合，则相关。这种判定方式显然十分僵化：在or方式中，包含很多主题词的页面和包含少数词的页面在与主题的相关度上是等同的；在and方式中，即使缺少一个词，结果也是false，等于一个词也没有。为此建立了扩展布尔模型，在各种扩展中，p-norm模型的运行结果是最符合实际的。
如图4.3所示，当p=infinity时，p-norm模型等同于classical boolean模型，当p较低时（如在[2,5]内），and方式中一个权值低的词会使总体值大大降低，or方式中一个权值高的值会使总体值大大提高。当p=1时，变成向量空间模型(vector space model)，and和or方式实际上相同，公式变为cosine similarity。当p-norm可以得到更大的灵活性。用户可以指定某个子表达式的p值，例如一个较大的值表示对它要求比较严格。
4.5.4.4 向量空间模型
进行主题词和页面内容相关性的计算过程，实际上也是一个对页面进行分类和聚类的过程。salton 等人于60年代末提出了向量空间模型 vsm (vector space model) 的概念，即使用向量表示文本或页面。
向量空间模型的基本概念可以描述如下：1).文档：泛指一般的文本或文本的片段（段落、句群或句子），一般指一篇文章。尽管文档可以是多媒体对象，但在我们的讨论中假设为文本对象，并且对文本和文档不加以区别。
2).项（特征项）：文本的内容由一些特征项来表达，一般由文本所含有的基本语言单位（字、词、词组或短语等）来表示，即文本可以表示为 ，其中， 表示各个项。换句话说，由这些项张开了一个向量空间，每个项表示一个维度。
3).项的权重：在一个文本中，每个特征项都被赋予一个权重 w，以表示这个特征项在该文本中的重要程度。权重一般都是以特征项的频率为基础进行计算的，比如采用 tf-idf 公式表示等等。这样文本就表示为： ，简记为 ，这时我们说项 的权重为 ，其中 。
4).向量空间模型（vsm）：给定一自然语言文本 ，由于 在文本中既可以重复出现又应该有先后次序的关系，分析起来仍有一定的难度。为了简化分析，可以暂不考虑 在文本中的先后次序并要求 互异（即没有重复）。这时可以把 看成一个 n 维的坐标系，而 为相应的坐标值，因此一个文本就表示为 n 维空间的一个向量，我们称 为文本 d 的向量表示或向量空间模型。
5).相似度度量：两个文本 和 之间的相关程度常常用它们的相似度 来度量。在向量空间模型下，我们可以借助向量之间的某种距离来表示文本间的相似度。相似度常用向量之间的内积来计算：
公式4.9
或用夹角余弦表示：
公式4.10
在向量空间模型的框架下有许多算法，例如，贝叶斯算法、k-近邻算法、类中心向量最近距离判别法、支持向量机等等。
4.5.4.5 概率模型（probabilistic model）
文档与查询相关的概率这一概念很早便由maron和kuhns引入信息检索领域[maron 1960]。其核心思想是将ir系统的主要功能看作是把集合中的文档按与用户信息需求的相关度概率降序排列。但是直到70年代中期，概率排序思想才逐渐进入实践领域，并开始蓬勃发展起来[robertson 1977]。
前面介绍的几种信息检索模型中都是将文档表示词条视为相互独立的特征项，忽略了词条间的关联性，而概率模型则考虑到词条、文档间的内在联系，利用词条和词条间的概率相依性进行检索。它使用概率推理网络进行文档表示和检索。概率推理网络模拟人脑的推理思维，将文档内容与用户查询匹配的过程转化为一个从文档到查询的推理过程。基本的文档检索推理网络包含文档网络与用户查询网络两个部分，如图4.4所示。
图4.4 概率推理网络
图4.4中每个节点表示一个文档、一个查询或者一个概念，其中 为文档节点， 为文档表示节点， 为文档概念节点， 为用户查询概念节点， 为用户查询节点，有向边表示节点间的概率相依性。网络中文档节点与查询节点间的相关性可以表示为：给定文档节点与查询节点的条件概率就可以计算出查询节点的后验概率，如要估算用户查询 与文档 间的概率相关性 ，先将文档节点 置为true，然后依次计算 的相依节点的概率即可[徐泽平 2001]。
在判定主题与页面的相关性过程中，只要把页面看作文档，把主题看作查询，则可用概率推理网络进行计算。
第五章 基于主题的web 信息采集系统模型及我们的对策
5.1 系统模型
基于主题的web信息采集技术在应用需求的推动下，已经成为一个热门的研究课题，为了更好的研究这个课题，我们设计了一个基于主题的web 信息采集系统模型，如图5.1所示。为实现对基于主题的信息自动采集，我们将整个处理过程分成五大模块：主题选择和初始url选择、spider采集、页面分析、url与主题的性关性判定(链接过滤/链接预测)、页面与主题的性关性判定(页面过滤)。下边简要地说明整个系统模型中的关键问题，在后续几章里，我们将详细讨论各个模块的算法及实现。
5.2 模型中的关键问题及我们的策略
5.2.1主题的选择
为了有效的进行剪枝和采集，基于主题的web 信息采集所要解决的一个重要问题就是主题选择问题。针对随便的主题词可能较大地影响采集效果，系统一般提供给用户一个主题分类目录以供选择。为了有效地确定用户选定主题的含义，用户要提供对主题的进一步描述，比如提供若干表达主题含义的文本，当然系统也会提供一些主题文本供用户选择。我们的系统就是按照中国图书馆的分类方法的第一级目录和二级目录对主题进行分类的，并在每个主题下配备了一些主题文本，以供用户选择。
5.2.2 采集起点的选择
一般采集器是从一个种子url集出发，通过web协议向web上所需的页面扩展的。基于主题的web信息采集也不例外，也有一个起始采集的种子url集。但是，基于主题的web信息采集的采集起点选择却必须十分慎重，因为这将影响着采集的效率，尤其是刚开始采集的准确率。
基于web上的linkage/sibling locality特性，一般采集系统需要选择质量较高的主题url作为初始种子url集。为此，我们采用我们自己设计的小金手元搜索引擎为每个主题搜索页面，搜索排名前50的url作为每个主题目录下的种子url。用户在设置主题采集时可以在这50个url中进行选择，也可以将自己知道的好的主题url输入进来，以提高采集的效果。
而更高级的初始url的选择方法是根据用户兴趣制导的，这需要有一个初始的用户兴趣文件，这个文件可以由用户填写的兴趣和用户浏览器中的书签&收藏文件产生。这部分的研究也属于基于用户兴趣的采集。
图5.1 系统模型
5.2.3 spider采集
这个部分处于系统的底层，也叫“网络蜘蛛”，是系统专门与具体的web打交道的部分。主要通过各种web协议来自动采集internet上www站点内有效的信息（包括文本、超链接文本、图象、声音、影像、压缩包等各类文档）。这些web协议包括http、ftp以及bbs，还根据用户的需要采集了web chat、icq等特殊信息。这个部分主要对应于在第二章中介绍的web信息采集系统的基本结构中的“协议处理器”部分。
5.2.4页面分析
在页面采集到以后，我们要从中提取出链接来，然后根据链接与主题的相关性判定来过滤与主题无关的链接，接受与主题相关的链接并进行下一步的采集；为了有效的进行链接与主题的相关性判定，我们也要分析出页面链接中的扩展元数据(这个概念我们将在以后的章节中具体介绍)来；再者，为了进行页面与主题的相似度判定，我们也必须提取出页面中的正文和关键词来；为了其它操作的处理，我们也要进行对页面内容标题、摘要等的提取。所有的这些就是页面分析的内容：链接的提取、元数据的提取、正文的提取、关键词的提取、标题的提取、摘要的提取。它们的详细提取算法我们将在后文的相应章节中介绍。
5.2.5 url与主题的相关性判定(链接过滤/链接预测))
为了有效的提高基于主题的web信息采集的准确率和效率，系统需要对“待采集url”进行url与主题的相关性判定，也可以叫做链接过滤或链接预测。按照高预测值优先采集、低预测值(小于设定阈值)被抛弃的原则进行剪枝处理。这样可以大大减少采集页面的数量，有效的提高主题信息搜索的速度和效率。这个问题是本类采集系统的重要问题，也是本文论述的一个重点，我们将在下面相应的章节中通过大量的算法分析详细剖析这个问题。
5.2.6 页面与主题的相关性判定(页面过滤)
为了进一步提高采集页面的准确率，需要对已采集的页面进行主题相关性评价，也就是页面过滤。通过对评价结果较低的页面(小于设定的阈值)剔除，来提高所采集主题页面的准确率。这个问题是检索领域内的一个经典问题，已经有许多成熟的基于关键词的相关性判定算法。我们采取的方法就是基于关键词的向量空间模型算法。
5.2.7 数据存储
主要有三种数据库需要存储，它们是主题页面库、全局url队列和中间信息记录库。主题页面库主要存放采集器采集过的并经过页面过滤处理后的主题页面。全局url队列则是存放从采集到的页面中提取出来的url的地方，这些url在进入url队列前必须经过url预测处理，只有被预测为指向主题相关页面的链接才能进入全局url队列。在插入队列时，也要根据url与主题的预测相关性的大小排序，相关性越高，排序越前。为了有效的进行url与主题的性关性判定和页面与主题的相关性判定流程，显然需要许多中间处理结果，比如使用ipagerank算法时每个页面所拥有的ipagerank值，所有的这些中间数据，保存在中间信息记录库中。
第六章 主题选择
在我们讲基于主题的采集的时候，并没有完全弄清楚一个问题——什么是主题。针对可变主题的信息采集系统，就像用户利用搜索引擎为自己服务时必须正确地选择查询词一样，我们必须有效的进行主题选择，这样才能采集到我们真正需要的主题页面。本章在对主题和主题分类目录作了详细的说明后，给出了我们的主题选择策略。
6.1 主题的定义
一个主题就是一个“含义”，或者叫一个“概念”。它可以是一个词，也可以是一个短语，甚至是一个段落，一篇文章。这个“概念”的范围可大可小，大的时候可以非常广泛，但此时它的意义也非常模糊；小的时候它可以非常狭义，而这时它的意义却非常具体。因此，基于主题的采集系统采集的页面数量根据主题概念的大小有很大的变化。
6.2 主题分类目录
图6.1 中国图书馆分类法
一般的搜索引擎返回给用户的结果不令用户满意的一个重要原因是系统获得查询关键词并不足以反映用户的需求，这很大程度上是因为关键词选择得不合适。基于主题的信息采集也面临着主题选择的困难。现实中的主题范围太广泛，杂乱无章，混乱无序，有些主题没有实际用途上的意义(比如，“如果，和”)；而有些主题又几乎不能引起人们的采集兴趣(比如，“跑”)。为此，有必要对主题进行统一的分类。这不光有利于固定主题的信息采集系统选择合适的主题范围和主题角度进行采集，而且还为多个此类采集系统联合采集更大范围的主题页面提供了有效的依据，还可以将主题分类推荐给可变主题采集系统前的用户，使他们的选择更加明智。
目前，很多基于主题的采集采用yahoo主题分类目录，当然也可以是其它分类目录，但所选择的分类目录应该分类比较合理，并具有一定的权威性。图6.1给出了中国图书馆分类法的第一级目录对整个主题进行的分类。
当然，这些基于主题的信息采集系统，在提供给用户主题分类目录的同时，仍然允许用户自由输入主题，以提高系统的灵活性。
6.3 web上的主题分类目录的特点
web上有许多分类目录（directory）站点，如yahoo!，yellow pages。一般有以下特点：
l 基本是树形结构。每个节点（叶节点除外）有数量不等的若干子节点。少数节点有不只一个父节点，因此不构成严格的树结构。节点依据知识本体论(knowledge ontology)划分。分类目录站点的主页一般只显示一、二级节点。
l 节点命名。每个节点有一个简短的命名。非根节点的全名是从根到该节点的路径上的所有节点的名称的顺序组合，如business_and_economy/companies/travel/ agents。
l 节点内容。每个节点收集有若干url，除了叶节点之外，每个节点有若干子节点。
l 维护。分类目录的维护一般是人工进行的，由分类目录站点雇佣专人分别负责各个子类，不断跟踪web上的信息，这是大多数站点的主流做法。另一类做法是由志愿人员维护，个别站点可以有用户自己定制子树。
web上主题分类目录的这些特点决定了系统提供给用户的是一个可层层深入的树状主题结构图。
6.4 主题选择策略
在本节里我们讨论的主题选择主要是针对可变主题的信息采集系统。从前文我们已经知道，一个主题可以是一个词语，一个句子，甚至一个段落。为了让用户能够有效的表达主题采集要求，采集系统一般要提供给用户一个主题分类目录，用户可以通过它选择一个最适合的主题进行采集，这个主题可以是树根、树枝，也可以是树叶。
为了增加相似度判定时候的有效性，系统还必须为每个主题提供一定数量的最能表达主题概念的样本文本，通过提取这些文本的特征，系统定量的掌握主题的含义。同时，为了体现对用户的针对性，系统允许用户对样本文件进行选择。
为此，用户可以在三个方面进行采集主题的选择：首先，用户在主体分类目录中寻找自己所要表达的主题；其次，对系统提供的样本文件进行选择，以使得它们能够完整的准确的表达自己的主题需求；第三，如果系统提供的主题选择文本不能全面完整的刻画自己的主题需求，或者主题分类目录中根本没有自己所需要的主题，则用户必须自己输入主题词和主题样本文件。这是和一般搜索引擎的关键词输入不同的。和关键词相比，主题词用更加定量的方法来描述，一般刻画的意义更准确、更全面，刻画手段更灵活、更方便。
第七章 spider采集
信息采集系统的最前沿就是与internet相连的spider采集，也叫“网络蜘蛛”，是系统专门与具体的web协议打交道的部分。主要通过各种web协议来自动采集www站点内有效的信息（包括文本、超链接文本、图象、声音、影像、压缩包等各类文档）。这些web协议包括http、ftp以及bbs，我们还根据用户的需要，采集了web chat、icq等特殊信息。本章先就spider结构作了一个简要说明，然后详细论述了我们的相关算法。
7.1 spider的系统模型
如图7.1所示，为了能够高效地采集页面数据，我们在spider系统中采用了client / server结构。 “网络蜘蛛”由一台或多台spider构成，它们通过内部通信，由信息服务器统一管理并协同工作。由于spider的效率受采集平台、网络性能等诸多限制，为了达到比较理想的采集速度，我们采用了用多个spider同时并行采集的策略。具体并行的spider个数需要根据实际的采集速度要求和网络环境而定。
显而易见，采用服务器/采集器的结构使采集系统具有很好的可扩展性。管理员可根据系统采集规模的变化动态地调整采集器的数量，在保证系统性能的前提下尽量减少系统开销，达到最佳的性能/价格比。而且在规模动态变化的过程中，系统能维持一致的管理和数据输出接口。
我们这里所说的信息服务器主要负责对全局url队列中的url进行分发、对采集到的页面信息和文件信息进行缓存和压缩以及在采集过程中的一些协调和控制。这一部分所要处理的一个中心问题就是url的分配策略，以便能够快速的有效的利用多个spider共同高效采集。为了实现的简单性，我们采用了轮转法进行分配。并且当某个spider没有待采集的url时，它也会主动向url分发器发送url请求。
每个spider的任务就是将信息服务器分配给它的url按照到来的先后顺序插入到自己的url队列中，然后不停的从队首取出url进行采集，直到自己的url队列为空。另一种url入队的方法是根据url的主题相关性评分高低插入自己的url队列(评分最高的放在队首)，但插入队列的时间代价和入队时的互斥操作都会影响采集的效率，而此方法换来的好处“更加优先的采集评分更高的页面”也并不太影响最终采集页面的质量。因此， 我们选择了前者这种简单的方法。为了提高进一步的采集效率，在每个spider上我们采用了多线程方式。
7.2 采集算法及实现
7.2.1 url的调度策略
为了提高分布式采集的效率，一般常用两种调度策略：静态调度和动态调度。
静态调度相对比较简单，它并不看采集器当时的负载情况，而是按事先的决策进行页面的分配。目前，主要有三种方法。1).轮转法，即将待采集的页面依次分配给n个采集器，直观上看，每个采集器被分配了相同的采集页面数，但是由于每个页面的连接时间不同，页面的大小也不同，尤其在复杂多变的网络环境下，分配不均衡几乎是不可避免的。2)加权轮转法，针对刚才提到的轮转法的缺点，将导致分配不均的主要因素网络连接时间长短作为权值，来引导轮转。一般来说，初始采集很难知道页面连接的时间长短，所以此时不能用加权轮转法，但由于网络中大部分网站在一段时间内的平均连接时间变化不大，因此在刷新的时候可以用加权轮转法，试验说明此时加权轮转法好于轮转法。3).随机选择法，假设每个页面的采集时间满足指数分布，每个采集器的处理能力为c1,c2, … ,cn ，则以概率 / k=1,2, … , n 为采集器k分配待采集页面。当每个采集器的处理能力相同时，则对每个采集器按概率为1/n分配页面。
实际的web是异构的、无序的和复杂的，文件格式各式各样，网络状况也随时间变化莫测。采用静态调度策略，并不考虑web当前的负载情况这一重要信息，结果常常难以令人满意。相应的，根据当前的负载情况进行调度的策略称为动态调度，这是一种更加智能化的方法，但算法往往比较复杂，维持此方法的系统开销也较大。主要有以下几种方法：1). 最低负载法，即将页面总是分配给当前负载最低的采集器。这个算法的问题在于：收集各个采集器的当前负载会导致额外的开销，并且过时的信息可能导致误判。2).pick-2方法，在这种复杂的环境中，与其增加大量的开销以跟踪负载，倒不如简单的增加选择的随机性以模拟环境的随机性。事实上，这样反而会改善整个系统的性能。pick-2方法就是这样一个例子，它是指随机的选择两个采集器，并选择负载较低的一个采集器分配页面。同理，pick-k就是随机的选择k个采集器进行比较，当k=n时，pick-k方法就退化成最低负载法了，当k=1时，pick-k方法就变成了我们前边说的随机分配法。mitzenmacher对pick-k进行了实验分析，他认为在大多数情况下，k=2是较好的选择[马晓星&吕建]。
对于我们的系统来说，首先这是一个试验系统，试验的重点并不是分布式，而主要是测试页面和url的过滤算法和系统的整体工作运转情况；其次，我们系统中所并行的各个spider的环境较相似(网络环境和机器性能)，所以我们选择了较简单的轮转法。
7.2.2 每个spider的抓取流程
图7.2 spider的抓取流程
抓取工作流程如图7.2所示，大致步骤如下：
1) 如果采集数据达到300k(上传数据阈值),则上传数据到信息服务器。
2) 从url队列中取出一个url放入协议判断器中。如果此时url队列为空，则转入7），否则转入3)。
3) 根据url头部的协议信息，协议判断器对url所采用的协议进行判断，如果是http协议，转入4)，如果是ftp协议，转入5)，如果是bbs协议，转入6)。
4) 启动采集http协议的线程httppagecontrol，对本页通过httpconnection进行采集。采集完后保存此页，转入1)
5) 启动采集ftp协议的线程ftppagecontrol，对本页通过ftpconnection进行采集。采集完后保存此页，转入1)
6) 启动采集bbs协议的线程bbspagecontrol，对本页通过bbsconnection进行采集。采集完后保存此页，转入1)
7) 向信息服务器发送请求url指令，采集完毕。
7.2.3 抓取页面时的处理
因为所抓取的主要页面都是符合http协议的，所以我们以http协议为例，说明具体的页面抓取时的处理。在页面抓取过程中用socket实现了基本的http协议。采集器可以经由指定的代理服务器（proxy）采集目标url，并且在目标url要求身份认证时能自动用事先设置好的用户标识和口令应答。抓取页面的主要实现算法如下：
1) 分析页面url，抽出目标站点地址和端口号，若无端口号设为http默认端口80。判断该站点的连接方式设置，若设为直接连接则与该地址和端口建立网络连接；若设为穿越proxy连接则与指定的proxy地址和端口建立网络连接。
2) 若建立网络连接失败，说明该站点不可达，中止抓取该页面并将其抛弃；否则继续下一步骤获取指定页面。
3) 由页面url组装http请求头，若该站点需要用户标识和口令则将其填入请求头中，发送请求到目标站点。若超过一定时间未收到应答消息则中止抓取该页面并将其抛弃；否则继续下一步骤分析应答消息。
4) 分析应答头，判断返回的状态码：
若状态码为2xx，返回正确页面，进入步骤5)；
若状态码为301或302，表示页面被重定向，从应答头中提取出新的目标url，转入步骤3)；
若状态码为其它，说明页面连接失败，中止抓取该页面并将其抛弃。
5) 从应答头中提取出日期、长度、页面类型等页面信息。若设置了页面抓取限制，进行必要的判断和过滤，抛弃不符合要求的页面。
6) 读取页面的内容。对于长度较大的页面，采用分块读取再拼接的方法保证页面内容的完整。至此该页面的抓取完成。
7.2.4 采集数据的组织
采集的数据存储主要有两个数据库：缓存数据库，页面记录数据库。
缓存库保存采集到的站点源页面，每个页面存成单独文件。每个站点创建一独立的目录，并按照页面url中体现的层次组建本地缓存文件的目录。例如，页面在缓存库中对应文件即为目录下的“file1”文件，其中[cachebase]指缓存库的根目录。由于url可能包含文件名中不允许的特殊字符，在转换成目录和文件名时要用系统规定的转义字符替换。
所采集页面的长度、更新日期、标题等数据存储在页面记录数据库中。每个页面对应库中的一条记录，包含了页面的简要说明，在后续的某些处理过程中可以从中获得必要的信息而不必再查看源页面。
第八章 页面分析
在本信息采集的url和页面的过滤判定过程中，主要处理html页面。因此，在页面分析中我们所做的工作主要包括对html页面进行语法分析，提取出正文、链接、链接的扩展元数据及其它相关内容；再把这些内容进行简单的加工和一致性处理；最后将处理结果保存在中间信息记录库中以供url过滤处理和页面过滤处理。
8.1 html语法分析
因为采集到页面的语法分析基于html（hypertext markup language）协议[rfc 1866]。整个语法分析过程可以看作两个层次，即sgml（标记文法）层和html标记层。文法层将页面分解成正文、标记、注释等不同的语法成分，再调用标记层处理正文和标记。同时标记层维护着当前正文的各种状态，包括字体、字型等，这些状态由特定标记产生或改变。
在系统中使用的标记文法分析器的基本原理是：由标记文法构造状态转换表，根据输入流中的当前字符（无需向前看）切换状态，当到达特定状态时执行相应语义操作。这里先介绍几个概念，然后分别讨论对主要语法成分的处理：
l 文本。文本是页面的初始状态，此状态下的所有字符（除了导致切换到其它状态的）都构成页面正文的一部分交由标记层根据当前正文状态处理和保存。
l 标记。标记是出现在正文中以字符“<”开始，字符“>”结尾的一个字符串。语法分析器在遇到“<”后就创建一个标记结构，并将后续的标记名称、标记中的参数等一一填入该结构中，其中参数由多个参数名/值对组成。当遇到“>”表示标记结束，将分析出的标记结构传递给标记层。标记层在根据标记名和参数做相应动作，包括修改正文状态等。若在“<”后紧跟着字符“/”，则表明此标记是个结束标记，分析器区分开始和结束标记，但两者的配对由标记层实现。对标记的处理在后面讨论标记层时会进一步论述。
l 注释。分析器判断“<!”打头的标记并统计模式“--”的个数从而识别页面中的注释，注释直接被忽略而不作任何处理。
l 转义字符。文本中出现的形如“&#nnn”或“&xxx”（末尾可能有附加的字符“;”）的，分析器将其作为转义字符处理，查找相应对照表后将对应字符添加入正文中。
8.2 页面中正文的提取
尽管url已经被预测为和主题相关，但此url所指向的实际页面却可能与预测结果相差甚远，这就导致了采集到的页面有相当大一部份与主题无关，因此，我们需要对页面进行主题相关性判断，通过判断结果过滤掉无关页面，从而提高整个数据集中页面与主题的平均相似度值，或者说提高基于主题的web信息采集的准确率。
为此，我们需要在页面分析时提取出页面中的正文。页面的正文提取方法较简单。正文和标记都作为独立的语法成分传递给标记层，标记层根据标记区分出页面标题和内容，并根据系统需要合并出页面的正文。目前还未考虑不同字体或字型的正文的差别。也就是说，在读取页面时，找到标记<body>和</body>，将这两个标记中间的内容去除其中的所有标记即可。
8.3 页面中链接的提取
对抓取到的页面需要分析其中的链接，并对链接中的url进行必要的转换。首先判别页面类型，显然只有类型为“text/html”的页面才有必要分析链接。页面的类型可由应答头分析得出，有些www站点返回的应答信息格式不完整，此时须通过分析页面url中的文件扩展名来判别页面类型。遇到带有链接的标记如<a>、<area>、<frame>等，就从标记结构的属性中找出目标url，并从成对的该标记之间抽取出正文作为该链接的说明文字(扩展元数据)。这两个数据就代表了该链接。
对一个页面中的链接提取工作流程如下：
1) 从页面文件队列中取出一个页面文件，如果应答头中未说明文件类型，根据url中的文件扩展名补充完整。如果页面文件队列为空，跳转到7)。
2) 判断页面是否为text/html/htm/shtml文件，如果不是，抛弃此文件，转入1)，否则转入3)。
3) 从文件头按顺序读取文件，遇到如下标记<a href=……> <area href=……> <base href=……> <frame src=……> <img src=……> <body background=……> <applet code=……>等，记录其中的url连接。如果遇到文件结束符，则跳转到7)
4) 将提取出来的url链接按照预先定义的统一的格式补充完整。(页面链接中给出的url可以是多种格式的，可能是完整的、包括协议、站点和路径的，也可能是省略了部分内容的，或者是一个相对路径)
5) 记录下<a href=……> <area href=……> <base href=……> <frame src=……> <img src=……> <body background=……> <applet code=……>等后面对此链接的说明信息。在url与主题的相关性判定那一章中，我们要用到此信息，并把它定义为扩展元数据。
6) 存储此url及其扩展元数据，跳转到2)。
7) 页面url提取完毕。
此算法中，不但提取了已采集页面中的url，并且同时提取了每个url的扩展元数据信息，在下一章，我们将看到对扩展元数据的应用。
8.4 页面中标题的提取
如图8.1所示，页面中标题的提取分为三步：1).判断正文开始的位置，从文章开头开始，逐段扫描，直到某一段长度不小于设定的正文最小长度，就假定这段为正文中的一段。2). 由正文位置向前搜索可能是标题的一段，根据字体大小、是否居中、颜色变化等特征找出最符合的一段文字作为标题。3). 由所给参数调整标题所在的段，使标题提取更准确。句法、语义、统计分析标题段sttitlepara的前后几段，以准确确定标题段的真实位置；向前或向后调整几段，追加前一段或后一段。
判断正文开始的位置
由正文位置向前搜索可能是标题的一段
由所给参数调整标题所在的段，使标题提取更准确
标题