（计算机软件与理论专业论文）聚焦爬虫技术研究.pdf

摘要 摘要 万维网信息的爆炸式增长使w e b 已经成为世界上最大的信息库。面对这个海量、 异构、半结构化的信息库，w e b 用户经常发现要查找到所需要的信息需要耗费大量的时 间，造成了“信息过载，知识匮乏 的问题。为了解决这个问题，在w e b 信息检索领 域提出了面向主题的聚焦爬虫技术。聚焦爬虫根据用户定义的目标主题，智能化的从 w e b 上收集主题相关的网页集合，然后采用机器学习或信息检索的方法对收集到的信息 进行智能处理和分析，最后以方便、有效的检索方式满足用户的信息检索需求。它的理 论和技术基础主要包括机器学习、信息检索、概率统计理论和w e b 新技术。在很多应 用领域，如基于w e b 的行业分析、自动构建专题数字图书馆等，主题驱动的聚焦爬虫 系统都富有应用前景。 首先研究了搜索引擎和爬虫的技术原理，工作流程以及典型的聚焦爬虫体系结构， 然后重点分析了聚焦爬虫的主题定义，网页的链接分析算法和内容分析算法，主题爬行 策略，以及存在的主要问题。 根据h i t s 算法善于发现主题社区，但是容易发生主题漂移；最佳优先算法由于忽 视超链接信息容易陷入局部最佳子空间的问题，提出了新的主题综合爬行策略。该策略 综合利用超链接价值和内容主题相关性价值计算网页的综合价值并排序。通过利用主题 页面分布特性，采用h i t s 算法计算网页的超链接价值，发现并抓取主题社区及主题相 关网页，并通过基于向量空间模型的网页主题相关度判定算法精确地量化了网页与主题 的相关程度，避免爬行过程中容易出现的主题漂移问题，提高了爬虫系统的收获率。针 对聚焦爬虫对目标主题的定义，采用文本分类方法建立主题特征词库，并提取主题特征 用于计算网页的主题相关度。 最后设计了基于综合爬行策略的聚焦爬虫的系统原型，改进了现有的聚焦爬虫的体 系结构，该系统实现了主题w e b 资源的智能化收集。通过实验测试得到爬虫系统的收 获率，验证了综合爬行策略的有效性。 关键词：垂直搜索引擎，聚焦爬虫，信息检索，链接分析，内容分析，超文本分类 a b s t r a c t a b s t r a c t w i t ht h ee x p l o s i v eg r o w t ho ft h eo n l i n ei n f o r m a t i o nr e s o u r c e s ，t h ew e bh a sb e c o m et h e m o s te n o r m o u si n f o r m a t i o nr e p o s i t o r yt od a t e c o n f r o n t e dw i t ht h i sh u g e ，h e t e r o g e n e o u sa n d s e m i - s t r u c t u r a li n f o r m a t i o nr e p o s i t o r y , w e bu s e r so f t e nh a v et os p e n dal o to ft i m ea n de f f o r t s t of i n di n f o r m a t i o nn e e d e d t h i sc o n t r a d i c t i o ni sg e n e r a l l yc a l l e d “i n f o r m a t i o no v e r l o a do n t h ew e b ”t os o l v et h i sp r o b l e m ，t o p i c d r i v e nc r a w l i n gh a sb e e np r o p o s e di nw e bi n f o r m a t i o n r e t r i e v a lc o m m u n i t yi nr e c e n ty e a r s t h es y s t e mu s e sa ni n t e l l i g e n tf o c u s e dc r a w l e rt oc o l l e c t h i g hr e l e v a n td o c u m e n t so n l i n ew i t hr e g a r dt ot h ep r e d e f i n e dt a r g e tt o p i c s a n da n a l y s i st h e i n f o r m a t i o nc o l l e c t e dt h r o u g hm a c h i n el e a r n i n ga n di n f o r m a t i o nr e t r i e v a lt e c h n i q u e s ，w h i c h r e s u l t si na ne f f i c i e n ta n dc o n v e n i e n ti n f o r m a t i o nr e t r i e v a la p p r o a c hf o rt h eu s e r s t h e f u n d a m e n t a lt h e o r ya n dt e c h n o l o g yi n c l u d em a c h i n el e a r n i n g ，i n f o r m a t i o nr e t r i e v a l ，s t a t i s t i c s a n dn e ww e bt e c h n o l o g i e s i tc a nb ea p p l i e dt ov a r i o u sa p p l i c a t i o n s ，i n c l u d i n gw e b - b a s e d i n d u s t r ya n a l y s i s ，a n da u t o m a t i cd i g i t a ll i b r a r ye t c t h i sp a p e ri n t r o d u c e s t h et h e o r ya n da r c h i t e c t u r eo ft h es e a r c he n g i n e sa n df o c u s e d c r a w l e r , a n di te m p h a t i c a l l ya n a l y z e st h et o p i cd e f i n i n g ，w e bh y p e r l i n ka n a l y z ea n dc o n t e n t a n a l y z ea l g o r i t h m s ，a n dt h ec r a w l i n gs t r a t e g yo ft h ef o c u s e dc r a w l e r h i t si sg o o da td i s c o v e rt o p i cw e bc o m m u n i t y , b u ti to f t e no c c u r s “t o p i cd r i f t ”p r o b l e m t oa v o i dg e r i n gi n t ot h el o c a lo p t i m u mo ft h eb e s tf i r s ts e a r c h ，t h i sp a p e rp r o p o s e san e w t o p i cc r a w l i n gs t r a t e g y i tc o m b i n e st h eh y p e r l i n kr a n ka n dc o n t e n tt o p i cr e l e v a n c et o c a l c u l a t et h et o t a lr a n ko ft h et a r g e tp a g e s i tu s e st h eh i t sa l g o r i t h mt oc o m p u t et h e h y p e r l i n kr a n ko ft h eu r l s ，d i s c o v e r sa n df e t c h e st h ew e bc o m m u n i t ya n da u t h o r i t yp a g e s ，a n d u s e st h et o p i cr e l e v a n c ed e c i s i o na l g o r i t h mb a s eo nv s mm o d e lt oa c c u r a t e l yq u a n t i z i n gt h e r e l e v a n c eo ft h ec r a w l e dp a g e s i ti n c r e a s e st h eh a r v e s tr a t eo ft h ec r a w l e rb e c a u s eo fa v o i d i n g t oo c c u rt h e “t o p i cd r i f t ”a c c o r d i n gt ot h et a r g e tt o p i cd e f i n i t i o no ft h ef o c u s e dc r a w l e li t u s e st e x tc a t e g o r i z a t i o na l g o r i t h mt ob u i l dat o p i cc h a r a c t e r i s t i cl e x i c o n ，a n de x t r a c t st o p i c c h a r a c t e r i s t i c st oc o m p u t et h er e l e v a n c eo ft h ew e b f i n a l l y , af o c u s e dc r a w l e rs y s t e mp r o t o t y p eb a s eo ns y n t h e s i z e dc r a w l i n gs t r a t e g yi s d e s i g n e d i ti m p r o v e st h ea r c h i t e c t u r eo ft h ee x i s t i n gf o c u s e dc r a w l e r a n dt h i ss y s t e m i m p l e m e n t st h ei n t e l l i g e n tc o l l e c t i o no ft h et o p i cw e br e s o u r c e s t h eh a r v e s tr a t eo ft h e s y s t e mg o tf r o me x p e r i m e n ts h o w st h ev a l i d i t yo ft h es y n t h e s i z e dc r a w l i n gs t r a t e g y k e y w o r d s ：v e r t i c a ls e a r c he n g i n e ，f o c u s e dc r a w l e r , h y p e r l i n ka n a l y z e ，c o n t e n ta n a l y z e ， h y p e r t e x t c l a s s i f i c a t i o n 独创陛声明 本人声明所呈交的学位论文是蠢人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意 签名：1 钆1 财、 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名：1 别姣 导师签名： 第一章绪论 1 1 课题研究的背景 第一章绪论 随着i n t e m e t 的迅速发展，网络对我们的影响己经越来越大。而在网上发展最为迅 猛的w w w ( w o r l dw i d ew e b ) 技术，以其直观、方便的使用方式和丰富的表达能力，已 逐渐成为i n t e m e t 上最重要的信息发布和传输方式。从1 9 9 0 年出现世界上第一个真正意 义上的网页i lj ，至今网页数量一直呈指数增长。我国的万维网也在快速发展中，截止到 2 0 0 7 年6 月底，中国大陆地区域名总数己达到9 1 8 万个，网站数量达到1 3 l 万个。图l 中列出了近五年来我国网站数量的增长情况1 2 j 中国网站数量增长情况 2 0 0 2 0 6 2 0 0 2 1 22 0 0 3 0 62 0 0 3 1 2 2 0 0 4 0 6 2 0 0 4 1 22 0 0 5 0 6 2 0 0 5 1 22 0 0 6 0 6 2 0 0 6 1 2 2 0 0 7 0 6 ( 孀( w w w c n n i c c 1 3 。2 0 0 7 0 6 图1 - 1中国网站数量增长情况 f i g 1 - 1t h eg r o w t ho f t h ec h i n aw e b s i t en u m b e r 随着网络信息资源的急剧增长，越来越多的信息涌到人们的面前，搜索引擎就是在 这样的背景下出现的，并且已经发挥出不可替代的作用，成为帮助人们从浩瀚的信息海 洋中获取自己想要的信息的有效工具和一种举足轻重的网络应用手段。c n n i c 报告显 示，4 4 7 1 的网民经常使用( 每天多次使用) 搜索引擎，可见近半数网民高度依赖搜索引 擎提供的服务。另外，每天使用一次搜索引擎的用户也占到1 7 2 ，这意味着每同使用 搜索引擎用户数高达6 1 9 1 。由此可见，网民的搜索依赖性呈现增强趋势。 现今，搜索引擎所解决的问题不论在质量还是数量上都达到了令人惊叹的地步。搜 索引擎是为了解决如何在知识海洋中邀游而出现的技术。搜索引擎以一定的策略在互联 网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务， 从而起到信息导航的目的。搜索引擎提供的导航服务已经成为互联网上非常重要的网络 服务，搜索引擎已经成为人们在网络中的“导游 。搜索引擎技术因而成为计算机工业 界和学术界争相研究、开发的对象。 作为搜索引擎的基础和核心组件，w e b 信息采集正发挥着举足轻重的作用，并且随 啷 喊 8 6 4 2 0 卜0 0 0 0 o 0 0 0 刖 坦 佃 8 6 4 2 江南人学硕+ 学位论文 着应用的深化和技术的发展，它也越来越多的应用于站点结构分析、页面有效性分析、 w e b 图进化、内容安全检测、用户兴趣挖掘以及个性化信息获取等多种服务和研究中。 通用搜索引擎信息采集的目标就是尽可能多地采集信息页面，甚至是整个w e b 上 的资源。随着w w w 信息的爆炸性增长，信息采集的速度越来越不能满足实际应用的 需要。最近的研究数据表明，即使大型的搜索引擎，它对w e b 的覆盖率也只有3 0 4 0 p j 。 另外，通用搜索引擎还具有其他的局限性【4 j 。 ( 1 ) 不同领域、不同背景的用户往往具有不同的检索目的和需求，通用搜索引擎所返 回的结果包含大量用户不关心的网页。 ( 2 ) 通用搜索引擎的目标是尽可能大的网络覆盖率，有限的搜索引擎服务器资源与 无限的网络数据资源之间的矛盾将进一步加深。 ( 3 ) 万维网数据形式的丰富和网络技术的不断发展，图片、数据库、音频视频多媒体 等不同数据大量出现，通用搜索引擎往往对这些信息含量密集且具有一定结构的数据无 能为力，不能很好地发现和获取。 ( 4 ) 通用搜索引擎大多提供基于关键字的检索，难以支持根据语义信息提出的查询。 针对上述情况，另一种形式的搜索引擎悄然出现，它可以在较小的范围内取得比通 用搜索引擎更令人满意的结果，以满足某些特定用户的需要，这就是主题式垂直搜索引 擎。垂直搜索引擎【5 ，6 ，7 ，8 】只搜索某一个行业或者某一个主题的信息，因此垂直搜索引擎 更具有针对性，也就能满足针对某一个行业或者某一个主题的特殊需求。垂直搜索引擎 通过对特定行业、主题的领域知识，可以提供根据语义信息的查询，从而满足用户的特 殊搜索需求；另外它更加专业，关注范围也比较小，所以返回的结果也更具有针对性， 并且只需要索引小部分万维网数据，所以可以只用很少的服务器资源覆盖绝大部分某一 特定行业、主题的数据。 聚焦爬虫作为垂直搜索引擎的核心组件，根据既定的抓取目标主题，有选择的访问 互联网上的网页与相关的链接，搜集所需要的信息。近几年来在面向主题的搜索领域中， 聚焦爬虫收到了极大的关注，如g o o g l e ，b a i d u 等推出的视频搜索、图书搜索、学术搜 索等主题搜索服务纷纷采用聚焦爬虫技术。 1 2 研究现状 目前面向主题的网络聚焦爬虫主要有两种技术： 一是基于w e b 链接分析的搜索。9 0 年代木期，国外信息检索研究者开始以s o c i a l n e t w o r k 为模型对互联网进行模拟。一些学者认为网页之间的超链接引用关系同社会网 络中的关系有相似之处，特别是与传统的引文索引非常类似。通过对链接进行分析，可 以找出网页之间的引用关系，由于引用网页与被引用网页内容一般都比较相关，所以就 可以很容易的按照引用关系来进行大量网页的分类。在美国，很多基于这种超链接分析 的检索系统原型已经产生。 二是基于w e b 内容分析的搜索。这类搜索方式是传统的信息检索技术的延伸。他 2 第一章绪论 的主要方式就是在聚焦爬虫内部建立一个针对主题的词库，爬虫根据词库对网上的信息 进行检索。 目前，有关主题型搜索引擎的研究正在成为一个热点。在1 9 9 4 年，出现了最早使 用查询来指导爬虫爬行的系统f i s hs e a r c hs y s t e m j 。后来相继在1 9 9 8 年和1 9 9 9 年分别 出现了s h a r ks e a r c hs y s t e m 1 0 】和聚焦爬虫( f o c u s e dc r a w l e r ) 1 1 1 ，lz 。如今，聚焦爬虫又 有了新的发展，国外典型的系统有c o r a l i 川、i b mf o c u s e dc r a w l e r 【l 、c o n t e x tg r a p h s f o c u s e dc r a w l e r 1 4 】等。 c o r a 是美国卡内基梅隆大学的a k m c c a l l u m 和m n i g a m 等人于1 9 9 9 年针对计 算机科学设计的一个主体型搜索引擎。它利用机器学习( m a c h i n el e a r n i n g ) 技术，在 w e b 上搜索与计算机科学相关的论文。利用隐式马尔科夫模型来找出题名、作者、摘要 和参考文献，利用基于统计模型的文本分类算法将其按照y a h o o 分类目录进行分类。 c o r a 对垂直搜索引擎的自动资源搜集具有相当重要的意义。但是，c o r a 没有在预测 u r l 与主题的相关度上做深入研究，也没有对w e b 网页进行采集分析。 i b mf o c u s e dc r a w l e r 是s c h a k r a b a r t i 提出的一种新的w e b 资源爬行系统，即聚焦 爬虫( f o c u s e dc r a w l e r ) 。它对主题的定义既不是采用关键词也不是加权向量，而是一 组具有相同主题的网页。尽管称为聚焦爬虫，但它实际上是一套关于特定资源的自动搜 集方案，用来搜集w r e b 主题资源。该系统采用两个模块：一个是分类器，用来计算抓 取文档与主题的相关度，同时也用来指导爬虫优先抓取的相关资源；另一个是选择器， 用来确定哪些是中一i i , 页面。再后来的改进版本中，作者将分类器分成两个，一个用来指导 爬行，一个用来计算抓取文档与主题的相关度。从而使系统有了更好的性能。 c o n t e x tg r a p h sf o c u s e dc r a w l e r 是由d i l i g e n t i 等人研究设计的一种聚焦爬虫。它们 提出了一种通过建立上下文图( c o n t e x tg r a p h s ) 来学习网页间的引用关系的方法。首 先为系统提供一组种子主题页面，然后利用g o o g l e 提供的反向链接服务来寻找到所有 指向种子页面的网页。这些网页被称为第一层网页，而所有指向第一层网页的网页被称 为第二层网页，依次类推。页面的层数根据用户参数的改变而改变。当每一个种子页面 都建立好一个上下文图后，将不同的上下文图的相应各层进行合并，形成一个合并上下 文图。同时为每一层设置一个贝叶斯分类器。在爬行过程中，分类器被用来确定所有爬 行的页面应该属于哪一层。一旦页面的所属层次被确定，那么该页面所包含的链接就将 会被加入到与该层相对应的队列中。然后再从考前的非空队列中提取所有爬行的u r l 。 i d g s ( i n t e m e td a t ag a t h e rs y s t e m ) 是南京大学张福炎、潘金贵教授等设计的一个 数据采集系统。该系统旨在对w e b 上中英文技术资料进行自动搜集。i d g s 根据用户提 交的挖掘目标样本，在w e b 上自动寻找用户所需的信息，它采用向量空间模型和基于 词频统计的权重评价技术，由特征提取，源站点查询，文档采集，模式匹配等4 部分组 成。该系统的关键技术在于模式匹配模块，其任务是计算实际采集到的网页与用户主题 之间的相关度。它的文档采集模块相当于一个爬虫，采用兴趣漫游模型，其基本思想是： 如果某网页满足用户主题，则继续往下找，否则就终止该方向的查找。该模型类似于 f i s hs e a r c h 算法。但它只是简单的利用父节点的主题相关度来判断是否抓取孩子结点， 江南大学硕士学位论文 并且只在用户给出的有限站点基础上爬行，搜索的深度和广度很有限，更多的强调准确 度，在一定程度上忽视了覆盖度。 1 3 本文的主要研究内容 本文结合聚焦爬虫技术的发展趋势，对爬虫系统的网页排序算法和搜索策略进行了 以下三个方面的研究： 第一：详细分析了通用搜索引擎的原理、结构、工作流程及特点。 第二：分析了通用搜索引擎现在面临的问题，提出了研究和开发聚焦爬虫系统的必 要性。并详细介绍了聚焦爬虫技术的原理，结构与相关技术，并指出了它们的优缺点。 第三：详细研究了聚焦爬虫系统广泛采用的超链接分析算法和内容分析算法，并从 理论上分析了它们的优缺点。然后详细研究和分析了聚焦爬虫广泛采用的爬行策略及其 优缺点。 第四：介绍了聚焦爬虫系统的设计与实现。并引入了基于超链接分析的h i t s 算法 与基于向量空间模型的内容主题相关度分析算法相结合的综合爬行策略。最后实验结果 证明该综合爬行策略能获得较高的收获率。 1 4 本文的组织结构安排 根据以上分析，本文重点将讨论面向主题的聚焦爬虫技术及其应用。论文各章节内 容安排如下： 第一章主要介绍课题的研究背景和相关研究内容以及发展现状。 第二章介绍搜索引擎的基本工作原理和结构，以及聚焦爬虫的体系结构。 第三章主要介绍和研究当前网络爬虫主要的网页分析算法，并介绍聚焦爬虫技术主 要采用的爬行策略。 第四章针对当前聚焦爬虫系统的爬行算法的不足，提出了基于超链接分析和内容分 析相结合的综合爬行策略，并提出了基于该爬行策略的聚焦爬虫系统模型，详细介绍了 该模型的功能与实现。 第五章对论文的主要工作做了总结，同时也提出了今后需要进一步研究和完善的工 作。 4 第二章搜索引擎技术概述 第二章搜索引擎技术概述 2 1 搜索引擎基本要求 搜索引擎接受用户通过浏览器提交的查询关键词，记作q 。在个可以接受的时间 内返回一个和该用户查询匹配的网页信息列表，记作l 。这个列表的每一条目至少包括 三个元素( 标题，网址链接，摘要) 。 “可以接受的时间 ，也就是响应时间。对于在w e b 上面的软件来说，这个时间不 能太长，通常也就在“秒”这个量级。这是衡量搜索引擎可用性的一个基本指标，也是 和传统信息检索系统的一个差别。更进一步的，这样的响应时间要求不仅要能满足单个 用户查询，而且要能在系统设计负载的情况下满足所有的用户。也就是说，系统应该在 额定吞吐率的情况下保证秒级响应时间。 “匹配 ，指的是网页中以某种形式包含有q 的内容，其中最简单、常见的形式就 是q 在其中直接出现。不过如果一个搜索引擎就是以百分之百满足这种简单的包含关系 为目标，即使实现了也并不就达到了最好的效果。 “列表”，这蕴含着一种“顺序”。绝大多数情况下，l 是相当长的，例如超过1 万个条目( 这是和图书馆全文检索系统的又一个不同，那里返回的列表通常较短，例如 几十个条目) 。这不仅是由于w e b 上的信息量大，也由于搜索引擎的查询方式简单。简 单，意味着抽象：抽象，意味着有更多的具体事物可能是它的体现。对于一个长长的列表， 很少有用户有耐心都审视一遍( 不仅是因为长，还因为大多数使用搜索引擎的用户通常 都是“找到为止 ，而不是“不全部找到不罢休”，加上这个列表中和一个用户关心的其 实只占很少的比例) 。有分析统计表明，用户平均察看返回结果不超过2 页。 现代大规模高质量搜索引擎一般采用三段式的。搜索引擎工作流程如图2 1 所示， 即：网页搜集、预处理和查询服务。 图2 - 1 搜索引擎工作流程 f i g 2 - 1t h ew o r k f l o wc h a r to f t h es e a r c he n g i n e 2 2 搜索引擎的分类 按照信息搜集方法和服务提供方式的不同，一般搜索引擎可以分为以下三类【1 5 】：目 录式搜索引擎、机器人搜索引擎和元搜索引擎。 江南大学硕士学位论文 目录式搜索引擎 目录式搜索引擎以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工 形成信息摘要，并将信息置于事先确定的分类框架中。信息大多面向网站，提供目录浏 览服务和直接检索服务。该类搜索引擎因为加入了人的智能，所以信息准确，导航质量 高，缺点是需要人工介入，维护量大，信息量少，信息更新不及时。这类搜索引擎的代 表是y a h o o 。 机器人搜索引擎 机器人搜索引擎由一个称为蜘蛛( 或爬虫) 的机器人程序以某种策略自动地在互联 网中发现和搜集信息，由索引器为搜集到的信息建立索引，由检索器根据用户的查询输 入检索索引库，并将查询结构返回给用户。服务方式是面向网页的全文检索服务。该类 搜索引擎的优点是信息量大，更新及时，不需要人工干预。缺点是返回信息过多，有时 候不够准确，用户必须从结果中进行筛选。这类搜索引擎的代表是：g o o g l e ，b a i d u 。 元搜索引擎 元搜索引擎1 6 】没有自己的数据，而是将用户的查询请求同时向多个通用搜索引擎递 交，将返回的结果进行消重，重新排序等处理后，作为自己结果返回给用户。服务方式 为面向网页的全文检索服务。这类搜索引擎的优点是返回结果的信息量更大，更全，缺 点是不能够充分使用所搜索引擎的功能，用户需要做更多的筛选。这类搜索引擎的代表 是w e b c r a w l e r ，i n f o m a r k e t 。 2 2 搜索引擎的体系结构 搜索引擎是一个技术含量很高的网络应用系统。它包括网络技术、数据库技术、检 索技术、语言处理技术及智能技术等等。 各种搜索引擎虽然在设计细节上有所不同，但是基本构造通常可以分为四部分：网 络爬虫、索引模块、信息检索和用户接口。图2 2 给出了搜索引擎的体系结构。 6 第二章搜索引擎技术概述 2 2 1 网络爬虫 用户接【 信息检索 索引模块 网络爬虫 图2 - 2 搜索引擎体系结构 f i g 2 - 2t h ea r c h i t e c t u r eo f t h es e a r c he n g i n e 网络爬虫17 j ( c r a w l e r ) 也称“网络机器人( r o b o t ) ，“网络蜘蛛( s p i d e r ) ”，是一个 功能很强的w e b 自动抓取程序，它为搜索引擎遍历万维网，抓取网页，是搜索引擎的 核心组件，搜索引擎的性能，规模，扩展能力很大程度上依赖于网络爬虫的处理能力。 图2 - 3 为网络爬虫的系统结构图，其中下载模块用于访问并抓取w e b 上的页面， u r l 队列按优先级存放待抓取的u r l 。u r l 数据库用于存放从抓取网页中抽取的u r l 。 7 高 江南人学硕十学位论文 图2 3 网络爬虫的结构图 f i g 2 3t h ea r c h i t e c t u r eo f t h ew e bc r a w l e r 通用网络爬虫会根据预先设定的一个或若干初始种子u r l 开始，下载模块不断从 u r l 队列中获取一个u r l ，访问并下载该页面。页面解析器去掉页面上的h t m l 标记 得到页面内容，将摘要、u r l 等信息保持在w e b 数据库中，同时抽取当前页面上的新 的u r l ，保存到u r l 队列，直到满足系统的一定停止条件。网络爬虫访问页面的过程 是对互联网上信息遍历的过程。通用网络爬虫的工作流程如图2 - 4 所示。 y 图2 4 通用网络爬虫工作流程 f i g 2 - 4t h ew o r k f l o wc h a r to f t h eg e n e r a lw e bc r a w l e r 为了保证网络爬虫遍历信息的广度和深度，一般事先设定一些重要的u r l ，并制定 相关的爬行策略，然后对这些链接进行遍历。搜索引擎的爬虫系统一般还要定期重新访 问所有w e b 页面，更新w e b 所有数据库，以反映w 曲的更新情况，所以网络爬虫的实 第二章搜索引擎技术概述 现常需要常用分布式、并行计算技术，以提高信息发现和更新的速度。 网络爬虫将遍历得到的页面存放在临时数据库中。为了提高检索的效率，需要建立 索引。索引模块将w e b 网页进行词汇流化，即将这个文档内的全部单词分别提取出来， 然后依次对每个单词进行索引。这样得到的索引库称之为全文数据库。目前常用的有三 种全文索引算法： 倒排文件( i n v e r t e df i l e s ) 后缀数组( s u f f i xa r r a y s ) 签名文件( s i g n a t u r ef i l e s ) 倒排文件【l8 】是目前搜索引擎实际使用的全文索引算法。对于倒排文件来说，这个技 术是以关键词为基础的搜索技术，它是现在对于大多数应用最佳的选择；后缀数组对于 短语查找和其他很少的普通查询比较快，但是构造和维护它们是非常困难的；签名文件 流行于2 0 世纪8 0 年代，但是现在倒排文件已经取代了它们。 一个倒排文件( 或者称为倒排索引) 是一个基于单词来索引一个文本集合的机制， 其目的是提高查找任务的速度。倒排文件由两个组成部分：词汇表( v o c a b u l a r y ) 和位 置信息( o c c u r r e n c e s ) 。词汇表是一个由文本中的不同词汇组成的集合。对于这样的单词， 它在文本中出现的位置也被存储下来。位置集合被称作o c c u l l r e n c e s ；这些位置可以涉及 单词或者字符。单词的位置简化了短语和相近的查询。与此同时，字符的位置能够使得 直接获得匹配文本的位置更加容易。词汇表要求的存储空间非常小。 如果有时索引不能及时更新，网络爬虫带回的新信息就不能被使用搜索引擎的用户 查到。 2 2 3 信息检索 信息检索模块的主要功能就是根据用户提交的查询请求，在数据库中检索相关信 息。在文本信息检索中，因为处理的主要对象是词语，所以通常采用匹配方式，并以精 确匹配为主。用户端的查询信息首先要进行分析处理，要提取出查询项索引，逻辑表达 式或其他查询特征描述。并采取相似性估算算法检索出相关文件，然后对检索的结果网 页进行排序，然后将查询结果返回给用户。搜索引擎处理一次用户查询的代价是高昂的， 另一方面，很多用户的查询请求也是相同的，或者部分相同，为了加快检索端的响应速 度，通常根据最近用户查询信息建立检索缓存。 2 2 4 用户接口 用户接口是用户直接接触到的部分，所以其作用也至关重要。用户接口的设计既要 考虑其功效性，便于用户使用，也要充分体现简洁，美观，以吸引更多的用户。现状很 9 江南人学硕十学位论文 多中文搜索引擎都同时提供分类目录导航和网页检索功能。这样用户既可以通过逐层浏 览界面上的分类目录，也可以直接通过输入查询信息来查找所需要的信息。 用户接口提供一系列的查询选项以满足不同的查询要求。一般的搜索引擎都支持布 尔表达式操作( 与、或、非) 、搜索域名范围限制( 如只检索e d u c n 域名的网站) 、查询 网页的语种，甚至可以选择文档的类别( 如h t m l 、p d f 、d o c 等) 。合理的设置查询 选项可以大大的减少搜索结果中的无关内容，提高查询效率。 2 3 聚焦爬虫概述 2 3 1 主题式垂直搜索引擎概述 主题式垂直搜索引擎是针对通用搜索引擎的信息量大、查询不准确、深度不够等提 出来的新的搜索引擎服务模式。垂直搜索引擎是以构建某一特定主题或学科领域的 i n t e r n e t 网络信息资源库为目标，智能地在i n t e r n e t 上搜集符合这一特定主题或学科领域 需求的w e b 信息资源，能够为包括学科信息门户、专业信息机构、特定行业领域、公 司信息中心、行业专家等等在内的信息用户，提供整套的网络信息资源开发方案。其特 点就是“专、精、深”，且具有行业色彩，相比较通用搜索引擎的海量信息无序化，垂 直搜索引擎则显得更加专注、具体和深入。表2 1 显示了通用搜索引擎与垂直搜索引擎 的区别。 表2 1 通j j 搜索引擎与乖直搜索引擎的区别 t a b 2 - 1t h ed i f f e r e n c eb e t w e e ng e n e r a ls e a r c he n g i n ea n dv e r t i c a ls e a r c he n g i n e 通川搜索引擎年直搜索引擎 服务目的面向任何用户，提供任何信息的面向专业川户，提供专业信息的 查询查询 搜索方式广度优先策略爬行，试图遍历整采用一定的爬行策略，尽量只抓 个w e b取主题相关网页 硬件与网络要求 对硬件和网络的要求较高对硬f t ：币l j 网络的要求较低 定向抓取相关网络资源的聚焦爬虫正是主题式垂直搜索引擎的基础和核心。与传统 网络爬虫不同，聚焦爬虫并不追求覆盖率，而将目标定位抓取一部分主题网络资源。聚 焦爬虫可以避免访问网络中不相关的网页，从而节省硬件和网络资源。近几年来面向主 题的搜索领域中，聚焦爬虫收到了极大的关注。 2 3 2 聚焦爬虫的特点 聚焦爬虫( f o c u s e dc r a w l e r ) ，又称为主题爬虫1 8 ，1 2 憎，2 0 2 1 1 ( t o p i c a lc r a w l e r ) 。虽然 在实现原理上与通用网络爬虫基本相同，但不同的是聚焦爬虫的爬行过程是目标主题驱 动的、有选择性的爬行。它根据既定的目标主题，有选择性的访问w e b 上的相关页面， 搜集所需要的信息。聚焦爬虫并不追求网络资源的覆盖率，而将目标定为抓取与某一特 定主题内容相关的网页，为面向主题的通话查询准备数据资源，追求网络资源的查准率 j 。相比通用网络爬虫，聚焦爬虫需要在以下几个方面需要更进一步的工作： 1 0 第二章搜索引擎技术概述 ( 1 ) 信息的定制。由于面向主题的搜索引擎是为用户提供某一特定主题或学科领 域的信息。搜集的信息应该满足用户的要求。信息定制就是让用户定制自己想要查找的 内容，通常有给出分类关系，关键词，初始网站和网页范例等形式。 ( 2 ) 对网页进行主题过滤。网络上的w e b 信息是海量的，往往希望搜集的知识其 中很少一部分信息，而大量的都是与主题不相关或相关度较低的信息。所以，聚焦爬虫 通常对网页进行主题过滤，滤除不相关网页或者相关度较低的网页。 ( 3 ) 以一定的启发式搜索策略算法控制信息资源的抓取。w w w 是一张巨大的信 息网，如何引导聚焦爬虫有目的，有控制的抓取与特定领域相关的w e b 页面信息是一 个关键问题。问了达到这个目的，聚焦爬虫通常采用某种启发式搜索策略算法，根据用 户设置的主题导向词或者主题表示模型，以启发式函数计算每个u r l 的权值，并进行 w e b 排序，并选择权值高的u r l 优先访问，并放弃未到达预定阀值的u r l 。 ( 4 ) 寻找和发现高质量网页和关键资源。关键资源：是指一个包含许多指向指定 主题的超链接的网页。高质量网页：是指内容是知道主题的网页。由于网页信息分布通 常呈现不均匀性。通常，指定主题的关键资源总是链向高质量网页。寻找和发现高质量 网页和关键资源不仅可以大大提高聚焦爬虫搜集w e b 页面的效率和质量，还可以为主 题表示模型的优化等应用提供支持。 2 3 3 聚焦爬虫的工作流程 聚焦爬虫需要根据一定的网页分析算法过滤与主题无关的链接，保留有用的链接并 将其放入等待抓取的u r l 队列。然后，它将根据一定的搜索策略从队列中选择下一个 要抓取的网页u i 也，并重复上述过程，直到达到系统的停止条件。聚焦爬虫的工作流程 如图2 5 所示。所有被抓取网页将会被系统存储，并进行一定的分析、过滤、然后建立 索引，以便用户的查询和检索；这一过程所得到的分析结果可能对以后的抓取过程提供 反馈和指导。 江南人学硕十学位论文 y 图2 5 聚焦爬虫的工作流程 f i g 2 - 5t h ew o r k f l o wc h a r to ft h ef o c u s e dc r a w l e r 2 3 4 聚焦爬虫系统体系结构 下面将分析三种具有代表性的聚焦爬虫系统的体系结构。 2 3 4 1 基于分类器的聚焦爬虫 文献【11 】是具有代表性的聚焦爬虫的早期研究之一，目前大多数的聚焦爬虫都采用 了类似的工作流程，其系统结构如图2 - 6 所示1 4 j 。根据一个主题目录和用户指定的初始 种子来描述抓取主题，并在用户浏览过程中，将用户标注的感兴趣网页加入到相应的主 题目录，修改主题样本。系统的两个主要部分是网页分类器( c l a s s i f i e r ) 和网页选择器 ( d i s t i l l e r ) 。网页分类器负责学习抓取目标的特点，计算网页的相关度，并过滤网页。 网页选择器负责计算网页的重要程度，发现中心网页，并由此动态决定网页的访问顺序。 1 2 第二章搜索引擎技术概述 图2 - 6 基于分类器的聚焦爬虫体系结构 f i g 2 - 6t h ea r c h i t e c t u r eo ft h ef o c u s e dc r a w l e rb a s e do nc l a s s i f i c a t i o n 2 3 4 2 基于数据抽取器的聚集爬虫 聚焦爬虫从网络上发现主题相关的资源网页，传递给数据抽取器进行数据抽取工 作。数据抽取可能是对h i d d e nw e b 之后的数据库进行探测查询，也可能是通过w r a p p e r 或网页外观格式信息进行数据抽取。得到的元数据将由数据分析器做分析和标注，才能 转化为符合系统数据库模式的结构化数据进行存储和索引。系统结构图如图2 7 所示【4 1 。 图2 7 基于数据抽取器的聚焦爬虫体系结构 f i g 2 - 7t h ea r c h i t e c t u r eo ft h ef o c u s e dc r a w l e rb a s e do nd a t ae x t r a c t 2 3 4 3 基于用户学习的聚焦爬虫 用户协作聚焦爬虫的体系结构关键在于对用户的浏览模式的学习模块。文献【2 2 】提 出了基于用户学习的聚焦爬虫的体系结构如图2 - 8 所示【4 1 。系统通过记录用户在浏览到 感兴趣的网页时，点击“有用”按钮的行为，记录相关网页，为用户建立浏览模式。之 后，系统对经过标注的网页进行l s i 聚类，根据聚类结果构建概念图，表示不同类别之 间的联系，学习用户的浏览行为。用户浏览模式学习还可以通过对日志的挖掘来获得弘川， 其具体方法与文献【2 2 】不同，但是系统同样通过建模和学习两个部分来完成对爬虫程序 江南人学硕+ 学位论文 的指导。 图2 - 8 基于用户学习的聚焦爬虫体系结构 f i g 2 - 8t h ea r c h i t e c t u r eo ft h ef o c u s e dc r a w l e rb a s e do nu s e rl e a r n i n g 2 4 本章小结 本章介绍了当前通用搜索引擎的系统结构，以及功能模块的实现技术，包括网络爬 虫，索引，信息检索和用户接口。通过分析了当前通用搜索引擎的不足，对比了通用搜 索引擎和主题式垂直搜索引擎的区别后，详细介绍了主题式垂直搜索引擎的基础和核心 组件聚焦爬虫。首先详细介绍了聚焦爬虫需要解决的问题，然后介绍了聚焦爬虫的 工作流程以及基于各种技术实现的聚焦爬虫的体系结构。 1 4 第三章聚焦爬虫技术的研究 3 1 主题描述 第三章聚焦爬虫技术的研究 主题描述是指对主题的量化表现，即通过一定的方法和