基于Shark-Search和Hits算法的主题爬虫研究

第２０卷．第１　期　

２０１０年儿月　

计算机技术与发展　

Ｏ０Ｍ　ＵＴＥＲ　ＴＥＣＨＮ０Ｕ０ＧＹ　ＡＮＤ　ＤＥＶＥＬ　０ＰＭ匪ＮＴ　

Ｖｏ１．２０　Ｎｏ．１１　

Ｎｏｖ．　２０１０　

基于Ｓｈａｒｋ—Ｓｅａｒｃｈ和Ｈｉｔｓ算法的主题爬虫研究　

罗林波　，陈　绮　，吴清秀２　

（１．海南大学信息科学技术学院，海南海口５７０２２８；　

２．海南软件职业技术学院，海南琼海５７１４００）　

摘要：主题爬虫是实现垂直搜索引擎的核心技术。介绍主题爬虫的两个重要爬行算法：基于网页内容评价的Ｓｈａｒｋ—　

Ｓｅａｒｃｈ算法和基于网页链接关系的Ｈｉｔｓ算法，并分析了各自的优缺点，提出了一种新的主题爬行策略：将上述两种算法的　

优点结合起来即将基于网页内容评价和基于网页链接关系算法结合起来判断待下载　的优劣，并实现了一个主题爬虫。　

这种新策略正好弥补了两个算法各自的不足。通过与Ｓｈａｒｋ一￣ａｒｃｈ算法和Ｈｉｓ算法实现的主题爬虫对比，发现用新算　ｔ

法实现的主题爬虫查准率比这两种算法高。　

关键词：主题爬虫；爬行策略；垂直搜索引擎　

中图分号：１１Ｐ３９３　文献标识码：Ａ　文章编号：１６７３—６２９ｘ（２Ｏ１０）ｌ１—００７６—０４　

Ｒｅｓｅａｒｃｈ　ｏｎ　Ｔｏｐｉｃａｌ　Ｃｒａｗｌｅｒ　ｏｆ　Ｓｈａｒｋ。。Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ　

ａｎｄ　Ｈｉｔｓ　Ａｌｇｏｒｉｔｈｍ　

ＬＵＯ　Ｌｉｎ—ｂｏｘ，ＣＨＥＮ　Ｑｉ　，ＷＵ　Ｏｉｎｇ－ｘｉｕ２　

（１．Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｉｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｉｋｏｕ　５７０２２８，Ｃｈｉｎａ；　

２．Ｈａｉｎａｎ　Ｓｏｆｔｗａｒｅ　Ｐｒｏｆｅｓｓｉｏｎ　Ｉｎｓｔｉｔｕｔｅ，Ｑｉｏｎｇｈｍ　５７１４００，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｏｐｉｃａｌ　ｃｒａｗｌｅｒ　ｉｓ　ｔｈｅ　ｅｏｒｅ　ｔｅｃｈｎｏｌｏｇｙ　ｔｏ　ａｃｈｉｅｖｅ　ｖｅｒｔｉｃａｌ　ｓｅａｒｃｈ　ｅｎｇｉｎｅ．Ｔｈｅｒｅ　ａｒｅ　ｔｗｏ　ｉｍｐｏｒｔａｎｔ　ｃｒａｗｌｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｔｏ　ｂｅ　ｉｎ—　

ｔｒｏｄｕｃｅｄ：ｃｏｎｔｅｎｔ—ｂａｓｅｄ　ｅｖａｌｕａｔｉｏｎ　ｏｆ　Ｓｈａｒｋ—Ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｌｉｎｋ—ｂａｓｅｄ　ｒｅｌａｔｉｏｎｓｈｉｐｓ　Ｈｉｔｓ　ａｌｇｏｒｉｔｈｒｍ．Ｉｔ　ａｎａｌｙｚｅｄ　ｔｈｅｉｒ　ｒｅｓｐｅｃ—　

ｔｉｒｅ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｄｉｓａｄｖａｎｔａｇｅｓ　ａｎｄ　ｐｍｐｏｓｏｄｆｌ　ｎｅｗｔｏｐｉｃａｌ　ｃｒａｗｌｉｎｇ　ｓｔｒａｔｅｇｙｔｈａｔｉｓｔｏｍｍｈｉｎｅｔｈｅｔｗｏｄｇｏｆｉｔｈｒｎｓｗｈｉｃｈｉｎｃｌｕｄｅ　ｃ０ｎ—　

ｔｅａ＇ｌｔ—ｂａｓｅｄ　ｅｖａｌｕａｔｉｏｎ　ａｎｄ　ｌｉｎｋ—ｂａｓｅｄ　ｒｅｌａｔｉｏｎｓｈｉｐｓ，ｔｏ　ｊｕｄｇｅ　ｗｈｅｔｈｅｒ　ｔｔｒｌ　ｔｏ　ｂｅ　ｄｏｗｎｌｏａｄｅｄ　ｉｓ　ｇｏｏｄ　ｏｒ　ｂａｄ，ａｎｄ　ｉｍｐｌｅｍｅｎｔｓ　ａ　ｔｏｐｉｃａｌ　

ｃｒａｗｌｅｒ．Ｔｈｉｓ　ｎｅｗ　ｃｒａｗｌｉｎｇ　ｓｔｒａｔｅｇｙ　ｃａｎ　ｍａｋｅ　ｕｐ　ｆｏｒ　ｔｈｅ　ｄｅｆｉｃｉｅｎｃｉｅｓ　ｏｆ　ｔｈｅ　ｔｗｏ　ａ￣ｏｒｉｔｈｍｓ．Ｗｉｔｈ　ｔｈｅ　Ｓｈａｒｋ—Ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｔｈｅ　

ａｌｇｏｒｉｔｈｍｏｆｔｈｅＨｉｔｓ　ｃｏｎｔｒａｓｔ．ｉｔｉｓｉｎｆｅ￣ｅｄｔｈａｔｔｈｅ　ｅｆｆｅｃｔｏｆｕｓｉｇｔｎｈｅｎｅｗｔｏｐｉｃａｌ　ｃｒａｗｌｉｇ　ａｌｎｇｏｒｉｔｈｍ

ｃｙ　ｉｓ　ｂｅｔｔｅｒ　ｔｈａｎ　ｔｈｏｓｅ　ｔ、Ｊｌ，ｏ　ａｌｇｏｒｉｔｈｍｓ．　

Ｋｅｙｗｏｒｄｓ：ｔｏｐｉｃａｌ　ｃｒａｗｌｅｒ；ｃｒａｗｌｉｎｇ　ｓｔｒａｔｅｇｙ；ｖｅｒｔｉｃａｌ　ｓｅａｒｃｈ　ｅｎｇｉｎｅ　

ｗｈｉｃｈ　ｒｅａｃｈｅｓｔｈｅｄｅｇｒｅｅｏｆ　ｓｃｏｕｒｓ—　

Ｏ　引　言　

当前互联网正以惊人的速度不断发展，据２０１０年　

第二十五次中国互联网报告显示：２００９年我国网页总　

切需要一种更专业的搜索技术，将网上的信息更好地　

展现出来。于是垂直搜索引擎便诞生了，它被视为解　

决传统搜索引擎局限性的一种潜在方案，垂直搜索引　

擎已成为研究的热点Ｌ２Ｊ。　

数已达３３６亿，较上一年增长１０８％，７３．３％网民通过　

搜索引擎获取信息…１。ｗｅｂ信息的急速膨胀，在给人　

垂直搜索是面向特定主题（领域）的搜索引擎，是　

搜索引擎的细分和延伸，其特点就是“专、精、深”。主　

题爬虫（Ｔｏｐｉｃａｌ　Ｃｒａｗｌｅｒ）又称聚焦爬虫（Ｆｏｃｕｓｅｄ　

们提供丰富信息的同时，又使人们面临挑战，一方面网　

上的信息多种多样、丰富多彩，而另一方面用户通过传　

统搜索引擎来获取信息却越来越困难。因此，人们迫　

收稿日期：２０１０—０３—０９；修回日期：２０１０一Ｏ６一ｌ２　

Ｃｒａｗｌｅｒ）［３Ｊ，是垂直搜索引擎中核心的部分，就是根据　

一

定的网页内容和链接分析算法过滤与预定主题无关　

的链接，保留与主题相关的链接并将其放入待抓取的　

ＵＲＬ队列中；然后根据一定的策略从队列中选取下一　

基金项目：海南省自然科学基金资助项目（６０９００３）；海南大学科研　

项目（ｈｄ０９ｘｍ８４）　

作者简介：罗林波（１９８２一），男，湖北黄冈人，硕士研究生，研究方向　

步要抓取的网页ＵＲＬ，并重复上述过程，直到满足系　

统的某一条件时停止。　

主题爬虫以何种策略抓取ｗｅｂ信息，成为近年来　

主题爬虫研究的焦点之一【引。　

为数据挖掘；陈绮，副教授，博士，硕士生导师，研究方向为数据挖　

掘。　

第１ｌ期　罗林波等：基于Ｓｈａｒｋ—Ｓｅａｒｃｈ和Ｈｉｔｓ算法的主题爬虫研究　・７７・　

１主题爬行策略　

目前常用的主题爬行策略主要分两大类　』：一种　

是基于内容评价的爬行策略　Ｊ，以Ｄｅ　Ｂｒａ、Ｈｅｒｓｅｏｖｉｃｉ　

等人的研究Ｆｉｓｈ—Ｓｅａｒｃｈ￣　］及Ｓｈａｒｋ～Ｓｅｍｒｃｈ　等算法　

为代表；另一种是基于ｗｅｂ链接评价的策略，以　

ＰａｇｅＲａｎｋ［　］和ＨｉｔｓＥ　。］等算法为代表。　

基于内容评价的爬行策略，主要是计算网页内容　

以及锚文本等与预定主题的相似度来评价待下载链接　

价值的高低，并依此决定其爬行策略，相似度的评价通　

常采用如下公式：　

（硼　×ｗｉｋ）　

Ｓｕｎ（ｄ　，ｄ　）＝—　＝ｋ＝＝ｌ＝＝＝＝＝＝＝＝＝　（１）　

＾／（∑叫　）（∑　）　

其中ｄ　为新文本的特征向量，ｄｊ为第Ｊ类主题的　

中心向量，　则为特征向量的维数，ｗ　为向量的第Ｋ　

维。　

基于ｗｅｂ链接评价的策略主要是依据网页之间　

的链接引用关系来判断网页之间的重要程度。目前的　

Ｗｅｂ链接分析大多基于以下两个条件：　

（１）从网页Ａ指向网页Ｂ的超级链接是网页Ａ作　

者对网页Ｂ的推荐；　

（２）如果一条超链接将网页Ａ和网页Ｂ相互连接　

起来，则网页Ａ和网页Ｂ一般有共同的主题［ｕ］。　

下面分别介绍Ｓｈａｒｋ—Ｓｅａｒｃｈ算法和Ｈｉｔｓ算法。　

１．１　Ｓｈａｒｋ—Ｓｅａｒｃｈ算法　

在Ｆｉｓｈ—Ｓｅａｒｃｈ算法的基础上，Ｈｅｒｓｏｖｉｃｉ提出了　

Ｓｈａｒｋ—Ｓｅａｒｃｈ算法。Ｓｈａｒｋ—Ｓｅａｒｃｈ算法对ＦｉＳｈ—　

Ｓｅａｒｃｈ的一个重要改进就是利用所谓的“相似性引擎”　

对网页与主题的相关性进行模糊评分。子结点的主题　

相关性评分受３个因素影响：锚文本、锚文本附近的文　

字以及对父结点相关性的继承。Ｓｈａｒｋ—Ｓｅａｒｃｈ算法　

中对主题相关性的计算利用向量空间模型，取０～１之　

间的实数，ＵＲＬ列表中的每一个ＵＲＬ的得分由（１）式　

计算。　

Ｐｏｔｅｎｔｉａｌ—ｓｃｏｒｅ（ｃｈｉｌｄ—ｕｒ１）＝　＊ｉｎｈｅｒｉｔｅｄ（ｃｈｉｌｄ—　

ｕｒ１）＋（１一　）＊ｎｅｉｇｈｂｏｒｈｏｏｄ（ｃｈｉｌｄ—ｕｒ１）　（系数７＜１）　

（２）　

当父结点与主题相关时，从父结点继承到的相关　

性评分ｉｎｈｅｒｉｔｅｄ（ｃｈｉｌｄ—ｕｒ１）由预定主题ｑ和父结点网　

页的相似性计算得到，其中ｃｕｒｒｅｎｔ—ｕｒｌ为ｃｈｉｌｄ—ｕｒｌ结　

点的父节点，８为衰减因子且小于１：　

ｉｎｈｅｒｉｔｅｄ（ｃｈｉｌｄ—ｕｒ１）＝　

ｓｉｅｒ（ｑ，ｃｕｒｒｅｎｔ—ｕｒ１），ｉｆ（ｓｉｍ（ｑ，ｃｕｒｒｅｎｔ—ｕｒ１））＞　

…　

１　６．ｉｈｎｅｒｉｔｅｄ（ｃｕｒｒｅｎｔ—ｕｒ１），ｏｔｈｅｒｗｉｓｅ　¨　

邻近链接ｎｅｉｇｈｂｏｒｈｏｏｄ（ｃｈｉｌｄ—ｕｒ１）的评分与锚文　

本及锚文本附近的文字有关。根据锚文本，以及锚文　

本附近的文字与主题ｑ的相似性ｓｉｍ（ｑ，ａｎｃｈｏｒ）和ｓｉｎ１　

（ｑ，ａｎｃｈｏｒ—ｔｅｘｔ）可以简单地计算出邻近链接的主题相　

关性得分：　

ｎｅｉｇｈｂｏｒｈｏｏｄ（ｃｈｉｌｄ—ｕｒ１）＝卢。ｓｉｍ（ｑ，ａｎｃｈｏｒ）＋（１　

）・ｓｉｍ（ｑ，ａｎｃｈｏｒ—ｔｅｘｔ）　（４）　

１．２　Ｈｉｔｓ算法　

Ｈｉｔｓ算法是由Ｋｌｅｉｎｂｅｒｇ提出的基于超链接关系　

判断网页重要性的算法，目前主要用于搜索结果排序　

方面，引入了Ａｕｔｈｏｒｉｔｙ（权威）页面和Ｈｕｂ（中心）页面　

两个重要的概念。通常好的Ｈｕｂ页面指向许多好的　

Ａｕｔｈｏｒｉｔｙ页面；好的Ａｕｔｈｏｒｉｔｙ页面总是被许多好的　

Ｈｕｂ页面所指向，这种Ｈｕｂ与Ａｕｔｈｏｒｉｔｙ页面的相互加　

强关系，可用于Ａｕｔｈｏｒｉｔｙ页面的发现，这就是Ｈｉｔｓ算　

法的基本思想。　

Ｈｉｔｓ首先根据查询的关键词确定一网络子图Ｇ　

（Ｖ，Ｅ）（Ｖ为网路子图的结点集，Ｅ为边集），然后通过　

迭代计算得出每一个网页的权威值和中心值，具体步　

骤可分为三步：　

（１）通过搜索引擎获得与主题最相关的Ｋ个网页　

（Ｋ＝２００）的集合，称之为ｒｏｏｔ集。　

（２）通过链接分析扩展ｒｏｏｔ集，扩展后得到的集合　

称之为ｂａｓｅ集，扩展方法是对于ｒｏｏｔ集中任一网页Ｐ，　

加入所有Ｐ中所包含的链接到ｒｏｏｔ集，加人最多ｄ（ｄ　

＝

５０）个指向Ｐ的链接到ｂａｓｅ集。　

（３）计算ｂａｓｅ集中所有页面的中心值和权威值：　

若Ｇ中有７／个结点，设　维向量ａ、ｈ，其中口（ｉ）、　（ｉ）　

分别表示结点ｉ的权威值和中心值。算法如下：用１初　

始化向量ｎ、ｈ，ａ０＝１，ｈ０＝１，然后进行Ｉ，Ｏ操作：　

Ｉ操作：ｎ　（　）＝　ｈＨ（Ｗ）　（５）　

（＂，　）∈Ｅ　

ｏ操作：ｈ　（　）＝　口Ｈ（Ｗ）　（６）　

（４）规范化口（“），ｈ（　），ａ　（　）＝　ａ　（　）　

’　

（７）　

重复计算上面的Ｉ、ｏ操作和规范化操作，直到　

“（“），ｈ（　）收敛。　

２算法分析及改进　

以Ｆｉｓｈ—Ｓｅａｒｃｈ为基础的爬行策略其优点是具有　

较好的理论基础，而且计算比较简单，但是这类方法忽　

略了链接结构信息，这类在距离相关页面集较近的地　

・

７８・　计算机技术与发展　第２Ｏ卷　

方搜索时表现出良好的性能ｌ也　；但由于页面中的文本　

式（４）计算每条链接的ｎｅｉｇｈｂｏｒｈｏｏｄ（ｃｈｉｌｄ—ｕｒ１），将边ｃｕｒ．　

ｒｅｎｔ—ｕｒＩ＿＞ｃｈｉｌｄ—ｕｒｌ加入Ｇ—Ｅｄｇｅｓ，将ｃｈｉｌｄ—ｕｒｌ作为节　

点加入Ｇ—ｎｏｄｅｓ；　

信息缺乏“全局性”，很难反映ｗｅｂ的整体情况，使得　

这类网络蜘蛛普遍存在“近视”的缺点［１３］。　

Ｈｉｔｓ算法是一种依赖于查询（ｑｕｅｒｙ—ｄｅｐｅｎｄｅｎｔ）　

的主题提取算法。它首先利用搜索引擎从整个ｗｅｂ　

中选取与用户查询相关的部分网页来构成ｗｅｂ链接　

结构子图，然后在此链接结构子图上进行相应分析计　

算，由于Ｗｅｂ链接结构具有自组织性，在互联网中具　

｝　

通过搜索引擎将指向链接ｃｕｒｒｅｎｔ—ｕｒｌ的最多ｄ（ｄ　

：５０）个链接加入Ｇ—ｎｏｄｅｓ中，并将相应的边加入Ｇ—　

Ｅｄｇｅｓ；　

｝　

有相同或耗关的主题内容的网页之间往往通过超链接　

Ｉｆ（下载网页数量达到２００）｛　

相互连接形成一个个ｗｅｂ社区（ｃｏｎｗｎｕｎｉｔｓ）Ｈ　Ｊ，因此　

链接结构子图代表了互联网上某一主题的ｗｅｂ社区，　

当用户查询的主题较宽（甚至是多个主题）时，链接结　

构子图可能因多个子主题形成多个相对紧密的ｗｅｂ　

社区。因为Ｈｉｔｓ算法是一种基于迭代的算法，紧密链　

接区域中的页面的权值必定增加，从而影响了结果，这　

种现象通常被称为“主题漂移”（Ｔｏｐｉｃｄｒｉｆｔ）　５Ｊ现象。　

针对此，文中将Ｓｈａｒｋ—Ｓｅａｒｃｈ算法与Ｈｉｔｓ算法结　

合，在计算待下载ｕｒｌ的价值时除了依据网页内容、锚　

文本和锚文本附近的文字外还引入了依据Ｈｉｔｓ算法　

计算出的网页的权威值，既弥补了前者缺乏Ｗｅｂ全局　

性之不足，又消除了后者容易产生“主题漂移”的现象。　

则计算待下载ｕｒｌ值的公式变为：　

Ｐｏｔｅｎｔｉａｌ—ｓｃｏｒｅ（ｃｈｉｌｄ—ｕｒ１）＝Ａ＊ｉｎｈｅｒｉｔｅｄ（ｃｈｉｌｄ—ｕｒ１）＋　

Ｂ・ｎｅｉｇｈｂｏｒｈｅａ（ｃｈｉｌｄ　ｕｒ１）＋Ｃ・ａ　（　）　（８）　

其中系数Ａ、Ｂ、Ｃ为正数且满足Ａ＋Ｂ十Ｃ＝１，　

其他参数的意义同前。　

如果将扩充后的所有连接都加入下载队列必导致　

下载队列过于臃肿从而影响爬虫的性能，故设定一个　

阈值　，只有潜在价值大于　的链接才加入下载队列　

中。　按如下公式计算得出：　

ｐ＝∑ｕｒ１　／ｎ　（９）　

：１　

新算法描述如下：　

（１）通过关键字匹配从馊索弓ｌ擎获取前ｋ个链接　

并给链接赋初始值，然岳将链接加入待下载队列　

ＷａｔｅＱｕｅｕｅ中ｏ　

（２）ｗｈｉｌｅ（ＷａｔｅＱｕｅｕｅ不为空）ｉ　

Ｗｈｉｌｅ（保存的网页数量没有达到ｎ１）　

从ＷａｔｅＣ￣ｍｕｅ中取出得分最商的链接ｃｕｒｒｅｎｔ—ｕｒｌ下　

载该链接的网页ｃｕｒｒｅｎｔ—ｐａｇｅ并计算出该网主题相关度　

值ｉｎｈｅｒｉｔｅｄ（ｃｈｉｌｄ—ｕｒ１）；　

Ｉｆ（ｉｎｈｅｒｉｔｅｄ（ｃｈｉｌｄ—ｕｉｉ）：，ａ）｛　

将ｃｕｎｏｅｎ！ｕｒｌ加入Ｇ～Ｉｌｏｄｆ：ｋ￣＇，　：　

保存网页ｃｕｒｒｅｎｔ—ｐａｇｅ；　

提取网页ｃ１．￣Ｔｒｅｎｔ—ｐａ《ｅ　如≮一条镀援ｃ｝ｌｌｌｄ，　，绞公　

按顺序重复执行上述公式（５）～（７）直到收敛，计算　

出每个连接的权威值ａｉ（ｖ）和中心值ｈ（ｉ）；　

ｌ　

利用公式（８）计算Ｇ—ｎｏｄｅｓ中每个链接的得分，并利　

用公式（９）计算出Ｂ；　

将得分大于Ｂ的链接加入ＷａｔｅＱｕｅｕｅ中；　

｝　

其中Ｇ—ｎｏｄｅＳ为网络子图中的结点集，Ｃ—Ｅ出　

为边集，Ｋ为首次通过搜索因为获取的连接数且必须　

Ｋ＞　，为了防止重链死链一般取２００～３００间，ｍ为　

ｒｏｏｔ集中ｕｒｌ数量，一般取１５０～２００间，ａ为主题判断　

的阈值。主题相关性判断采用的是向量空间模型方法。　

新算法流程图如图１所示。　

图Ｉ算法流程图　

第１ｌ期　罗林波等：基于Ｓｈａｒｋ－Ｓｅａｒｃｈ和Ｈｉｔｓ算法的主题爬虫研究　

９０８．　

・７９・　

３试验及分析　

根据上述思想，设计了一个主题爬虫。评价聚焦　

［３Ｊ　Ｍｅｎｃｚｅｒ　Ｆ，Ｐａｎｔ　Ｇ，Ｓｒｉｎｉｖａｓａｎ　Ｐ．Ｔｏｐｉｃａｌ　ｗｅｂ　ｃｒａｗｌｅｒｓ：ｅｖａｌｕ—　

ａｔｉｎｇ　ａｄａｐｔｉｖｅ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｎｔｅｒｎｅｔ　

Ｔｅｃｈｎｏｌｏｇｙ，２００４，４（４）：３７８—４１９．　

爬虫系统性能指标主要有查准率、查全率［引。这里主　

要计算爬虫系统抓取网页的查准率，图２是对比结果。　

［４］Ｍｅｎｃｚｅｒ　Ｆ，Ｐａｎｔ　Ｇ．Ｅｖａｌｕａｔｉｎｇ　Ｔｏｐｉｃ—Ｄｒｉｖ一　

ａｎ　Ｗｅｂ　Ｃｒａｗｌｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　

２４ｔｈ　Ａｎｎｕａｌ　Ｉｎｔｅｍａｔｉｏｎａｌ　ＡＣＭ　ＳＩＧＩＲ　Ｃｏｎ—　

ｆｅｒｅｎｃｅ　Ｏ１１　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　ｉｎ　Ｉｎ—　

ｆｏｒｍａｔｉｏｎ　Ｒｅｔｒｉｅｖａ１．Ｎｅｗ　Ｙｏｒｋ，ＮＹ，ＵＳＡ：　

［ｓ．ｎ．］，２００１：９—１２．　

［５］　欧阳柳波，李学勇．专业搜索引擎搜索策略　

综述［Ｊ］．计算机工程，２００４（７）：３２—３３．　

［６］　

黄萱菁，吴立德，石崎洋之，等．独立于语种　

的文本分类方法［Ｊ］．中文信息学报，２０００，　

１４（６）：１—７．　

［７］　

Ｂｒａ　Ｄ　Ｐ，Ｐｏｓｔ　Ｒ．Ｓｅａｒｃｈｉｇｎ　ｆｏｒ　ａｒｂｉｔｒａｒｙ　ｉｎ—　

ｆｏｒｍａｔｉｏｎ　ｉｎ　ｔｈｅ　Ｗｗｗ：ｔｈｅ　ｆｉｓｈ—ｓｅａｒｃｈ　ｆｏｒ　

ｍｏｓａｉｃ［Ｃ］／／Ｓｅｃｏｎｄ　ｗｗｗ　Ｃｏｎｆｅｒｅｎｃｅ．　

图２测试结果　

Ｃｈｉｃａｇｏ：ＡＣＭ　Ｐｒｅｓｓ，１９９４：４５—５１．　

上图表明，Ｈｉｔｓ算法随着下载的网页数量的增加，　

［８］Ｈｅｒｓｅｏｖｉｃｉ　Ｍ，ｊａｃｏｖ　Ｍ，ＳＭａａｒｅｋ　Ｙ．Ｔｈｅ　Ｓｈａｒｋ—Ｓｅａｒｃｈ　Ａｌｇｏ—　

查准率一直下降，因为随着抓取网页的增加“主题漂　

ｒｉｔｈｍ～Ａｎ　Ａｐｐｌｉｃａｔｉｏｎ：Ｔａｉｌｏｒｅｄ　ｗｅｂ　Ｓｉｔｅ　Ｍａｐｐｉｇｎ［Ｊ］．ｏＣｍ　

移”现象越来越重，Ｓｈａｒｋ—Ｓｅａｒｃｈ随着下载网页增加　

ｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ　ａｎｄ　ＩＳＤＮ　Ｓｙｓｔ￣ｏ＿ｓ，１９９８，３０：３１７—３２６．　

趋于稳定，但没考虑网页的全局性查准率不高，而新算　

【９］Ｐａｇｅ　Ｌ，Ｂｒｉｎ　Ｓ，Ｍｏｔｗａｎｉ　Ｒ．Ｔｈｅ　ＰａｇｅＲａｎｋ　Ｃｉｔａｔｉｏｎ　山Ｉｌｇ：　

ＢｒｉｎｇＯｒｄｅｒｔＯｔｈｅＷｅｂ［Ｒ］．Ｓｔａｎｆｏｒｄ，ＣＡ：ＳｔａｎｆｏｒｄＵｎｉｖｅｒｓｉ．　

法随着下载网页增多趋于稳定的同时也保持了较高的　

ｔｙ，１９９８．　

查准率，且效果明显好于Ｈｉｔｓ和Ｓｈａｒｋ—Ｓｅａｒｃｈ算法。　

［１０］Ｋｌｅｉｎｂｅｒｇ　Ｊ．Ａｕｔｈｏｒｉｔａｔｉｖｅ　Ｓｏｕｒｃｅｓ　ｉｎ　Ａ　Ｈｙｐｅｒｌｉｎｋｅｄ　Ｅｎｖｉｒｏｎ—　

ｍｅｎｔ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆｔｈｅＡＣＭ，１９９９，４６（５）：６０４—６３２．　

４结束语　

［１１］康平波，田永鸿，黄铁军．智能化网页资源收集工具的设计　

文章在深入研究Ｓｈａｒｋ—Ｓｅａｒｃｈ算法和Ｈｉｔｓ算法　

与实现［Ｊ］．计算机工程，２００４，３０（４）：８８—９２．　

后，针对前者没有考虑链接关系缺乏Ｗｅｂ全局性之不　

［１２］Ｍｅｎｃａｅｒ　Ｆ．Ｃｏｍｐｌｍｅｅｎｔｉｎｇ　Ｓｅａｒｃｈ　Ｅｎｇｉｎｅｓ　ｗｉｔｈ　Ｏｎｌｉｎｅ　Ｗｅｂ　

足和后者没考虑网页内容容易产生“主题漂移”的现　

Ｍｉｎｉｇｎ　Ａｇｅｎｔｓ［Ｊ］．Ｄｅｃｉｓｉｏｎ　Ｓｕｐｐｏｒｔ　Ｓｙｓｔｅｍｓ，２００３，３５（２）：　

象，提出了将两种算法相结合的思路即文本和链接相　

１９５—２１２．　

结合的爬行策略，结果表明新策略效果明显，新算法在　

［１３］ＤｉｌｉｇｅｎｔｉＭ，ＣｏｅｔｚｅｅＦＭ，ＬａｖｃＩ￣ｎｃｅ　Ｓ，ｅｔ　ａ１．Ｆｏｃｕｓｅｄ　ｃｒａｗｌｉｇｎ　

提高查准率的同时也增加了算法的复杂性。如何在提　

ｕｓｉｇｎ　ｃｏｎｔｅｘｔ　ｇｒａｐｈｓ［Ｃ］／／Ｐｒｏｅｃｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２６ｔｈ　Ｉｎｔｅｒｎａ—　

ｔｉｏｎａｌ　ｏＣｎｆｅｒｅｎｃｅ　０１３．Ｖｅｒｙ　Ｉ．，ｌｆｌ￣ｅ　Ｄａｔａｂａｓｅｓ（ＶＬＤＢ一２０００）．　

高查准率的同时降低复杂度，将是下步研究的重点。　

Ｃａｉｍ，Ｅｇｙｐｔ：［ｓ．ｎ．］，２０００．　

［１４］Ｈａｋｅ　Ｇ　Ｗ，Ｌａｗｒｅｎｃｅ　Ｓ，ＧｉｌｅＳ　Ｃ　Ｌ，ｅｔ　ａ１．Ｓｅｌ＝ｆ—Ｏｒｇａｎｉｚａｔｉｏｎ　

参考文献：　

ａｎｄ　Ｉｄｎｅｔｉｆｉｃａｔｉｏｎ　ｏｆ　Ｗｅｂ　ｏＣｍｍｕｎｉｔｉｓｅ［Ｊ］．ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ，　

［１］ＣＣＮＩＣ．第２５次中国互联网络发展状况统计报告［ＥＢ／　

２００２，３５（３）：６６—７１．　

ＯＬ］．２０１０．ｈｔｔｐ：／／ｗｗｗ．ｃｎｎｉｃ．ｃｎ／ｕｐｌｓｏｄｆｉｌｓｅ／ｐ＆ｆ／２０１０／１／　

［１５］Ｍｅｎｃｚｅｒ　Ｆ，Ｐａｎｔ　Ｇ，Ｒｕｉｚ　Ｍ　Ｅ，ｅｔ　ａ１．Ｅｖａｌｕａｔｉｇｎ　ｔｏｐｉｃ—ｄｒｉｖｅｎ　

１５／１０１６００．ｐｄｆ．（℃ＮＩＣ．　

ｗｅｂ　ｃｒａｗｌｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｇｎｓ　ｏｆ　ｔｈｅ　２４ｔｈ　ｍｕａｌ　Ｉｎｔｅｍａ—　

［２］Ｐａｎｉｄｉｓ　Ａ，Ｐｏｕｌｏｓ　Ｇ　Ｋ　Ｃ，Ｐｉｔａｓ　Ｉ．Ｃｏｍｂｉｎｉｎｇ　Ｔｅｘｔ　ａｎｄ　Ｌｉｎｋ　

ｔｉｏｎａｌ　ＡＣＭ　ＳＩＧＩＲ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　

Ａｎａｌｙｓｉｓ　ｆｏｒ　Ｆｏｃｕｓｅｄ　Ｃｒａｗｌｉｎｇ——ａｎ　Ａｐｐｌｉｃａｔｉｏｎ　ｆｏｒ　Ｖｅｉｘｉｃａｌ　

ｉｎ　Ｉｆｎｏｒｍａｔｉｏｎ　Ｒｅｔｒｉｅｖａ１．Ｎｅｗ　Ｙｏｒｋ，ＮＹ，ＵＳＡ：［Ｓ．ｎ．ｊ，　

＆　ａｒｃｈ　Ｅｎｇｉｎｅｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍ，２００７，３２（６）：８８６一　

２００１：２４１—２４９．　

（上接第７５页）　

ｐｏｒｔｔｍｉｓｔｉｃ　ｎｅｗｔｏｒｓｋ［Ｃ］／／Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　２００６　ＳＩＧＣＯＭＭ　

ｍｏｕｔｈ．ｅｄｕ／．　

Ｗｏｒｋｓｈｏｐｏｎ　Ｃｈａｌｌｅｎｇｅｄ　Ｎｅｔｗｏｒｋｓ．Ｐｉｓａ：ＡＣＭ，２００６：２１３—　

［１６］ＵＣＳＤ　ｗｉｒｅｌｅｓｓ　ｔｏｐｏｌｏｇｙ　ｄｉｓｃｏｖｅｒｙ　ｐｒｏｊｅＣｔ［ＥＢ／ＯＬ］．２００４　

２２０．　

ｈｔｔｐ：／／ｓｙｓｎｅｔ．ｕｃｓｄ．ｅｄｕ／ｗｔｄ／．　

［１５］Ｃｒａｗｄａｄｐｒｏｊｅｃｔ［ＥＢ／ＯＬ］．２００８．ｈｔｔｐ：／／ｃｒａｗｄａｄ．Ｃ８．ｄａｒｔ・