（计算机科学与技术专业论文）基于web的网络搜索技术研究.pdf

摘要 随着互联网规模的急剧膨胀，面对用户无法正确找寻所需网络资源的困境， 搜索引擎为用户提供了便利的网络信息检索条件，成为现代信息获取的重要手段 之一。面向不同用户的智能网络搜索技术结合了搜索引擎的各种特性，并能够根 据用户需求、总结其不同的浏览行为，为用户提供良好的个性化网络搜索服务， 具有良好的应用前景。 本文首先介绍了搜索引擎的历史和现状，以及所需的技术指标和发展趋势。 随后按照一般网络搜索技术的流程，即网页搜索技术、网页分析技术和网页检索 技术，组织全文。并分别对这三个阶段的一般性技术和面向用户的个性化技术进 行了详细研究和全面的描述。 网页信息收集阶段首先描述了搜索引擎中网页收集的几种方式，并讨论了全 文搜索引擎使用爬虫进行网页收集的技术特点。在该章中，本文着重描述了面向 主题的网页信息收集技术，包括一个主题爬虫的系统模型、网页爬取超链接预测、 两页下载分析、主题h u b 网页的发现和对收集到的网页在主题上的质量控制。 网页分析阶段综合了一整套网页内容识别和语义信息提取技术，是数据挖掘 在网络资源上的典型应用。这章包括了使用正则匹配识别网页源代码中的内容、 网页预处理、网页特征项提取和量化，倒排文件的建立，和对具有相似内容的网 页进行消重。 网页检索阶段首先介绍了信息检索的定义和经典的网页排序算法p a g c 黜i l l 【 和h r r s ，随后描述了智能在线r s s 阅读器的内部核心对象和模型建立流程。最 后简单描述了系统检索和排序功能。 关键词：搜索引擎，用户个性化，网络挖掘，信息检索 a b s t r a c t w i mc x p o n 即t i a l 掣拼t ho fw e bp a g e s ，u s e sa l w a y sm e c tt l l ed i l e m m ao f c h o o s i n ge x a c t 洫f o 肌a t i o nt h a tt h e yn e c d s e a r c he n 舀n e sh a v ep m v i d e dl l s e f h l m e m o d st oi n d e x 柚ds e a r c hw e bs o l e s ，w h i c hb e c o m e so n eo ft h em o s ti m p o r t a m t o o l si i lo b t a i n i l l gm o d c mi n f 0 肌a t i o n h l t e l l i g e n tw 曲s e a r c ht c c l l i l o l o g yw h i c hf a c e s d i 丘b r c mu s e r sh 勰c o m b i i l e d 埘n d so fc h a r a c t e r i s t i c so fs e a r c he n 百n e s f l m h c n n o r e ， t h i st e c l l n o l o g ) ，s u 删瑚r i z e su s e r sb r o w s c rb e h a v i o r 锄dp r o v i d e sp e r s 伽i a lw c b s e a r c hs c r 、，i c ct ol l s e s ，w l l i c hh 略b r i g h tp m s p e c t 1 1 1 ep a p c rf i r s t 痂胁d u c 鼯l l i s t 0 1 y 锄dp r e s e n to fs e a r c h 百n 锚a n dt l l e i l l i s t m et c c h i q l l cd e t a i l sa n df i l l 曲e rd e 、r e l o p m e n ti i lt l l i s a a t h ew h o l cp a p c ri s o r g a n i z e d 勰m et l m es t 印so fs e a r c hc n 百n 龉：w e bc o l l e c t i o ns t a g c ，w e b 锄l y z i n g s t a g e 锄dw e b 砌c xs t a g e h le v e r ys t a g e ，t h ep a p c r 丘r s t 砌如d u c 嚣s o m eb 勰i c t e c l l i l i q u 嚣i n v o l v e di i lt l l i sf i e l d ，a n dt h e nd e r i b e st e c b l l i q u 酷m a t 如c 邯o np e r s o n a l s e a i c ho f u s e f si nd “l s mw e bc o l l e c t i o ns t a g e ，l h ep a p c rf i r s td e s c 曲e ss o m cm e 也o d si i lw e bc o l l e 嘶o n o fs e a r c he n g i n 髂，舡l dd i s c u s s 韶s p i d e r su s e di l lf i l l lt e x t 础锄g i n 髓t h ep a p e r f o c l l s e so nf o c 哪c dc r a w l e r s ，i n c l u d i n ga r c h i t e c t 盯eo f f i a 伊o c 惦e d i n t e l 】j g e i l ta g e t ) ， p r e d i c t i o no fu 幽暑t c h e du i 也，a l l a l y 2 i n go fd o w n l o a dw c bp a g c s ，d i s c o v e r yo ft o p i c h u bp a g 鼯柚di m p r o v i n gq u a l i t yo f c o l l e c t e dw e b p a g e s w 毫bp a g ea n a l y z i n gs t a g ei l 鸽酬_ 1 n m a r i z e das e r i 酷o ft e c 枷q u e sf b fi d c n t i 研n g w e bc o n t e n t 柚ds 锄a i l d cw e bi n f o 皿a t i o na b s 仃a c t ，w h i c hi st l l et y p i c a la p p l i c a t i o i l o fd a c am i n ：m g 也ew c b 1 1 l i ss e c t i o ni n c l u d 嚣l l s i n gr c g u l 缸e 】【p r e s s i o 璐t oi d 枷母 w e bc o n t a l ti l lw e bp a g e 础目d w c 骼，w c bp r e p r o c e s s i n 岛a b g t r a c t i n g 锄dq l l a n t i 轴g w 曲c o n c 印t s ，b i l i l d i i l gi n v e n c d 矗1 e sa i l dd e a l i n gn e 小r 印l i c 舔o ft h ed o c u m t s t l l e w e b bw e bi n d e ) 【s t a g e ，t h ep 印盯丘r g ti n 仃。血c c dd c 丘n e so fi n f o 蚰a t i o ni n d e x 强d c i a s s i c a im e l o d so fr a n k i i l gw e bp a g e s ，s u c h 雒p a g e r a n k 雏dh i t s a i l d l e l l d e s c r i b ek e m e lo b j c c t sa 1 1 dp m c e s s 访b u i l d i n gm o d e l so fo u ri m e l l 培e n tr s so i l l i n e r e a d e r f i n a l i y ，d i s c u s si i l d e xa n dr a u 咄o f m es y s t e m k e y w o r d s ：s e a r c he n 百n e ，u s c rp e r s o n a l i z a t i o n ，w e bm i n i n g ，h l f o 咖a t i o nr e t r i c v e u 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属于西北工业大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查 阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作 者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名：薹超i指导教师签名： 7 年争月。日2 司年华月2 日 l 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的 学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所 知，除文中已经注明引用的内容和致谢的地方外，本论文不包含任何其 他个人或集体已经公开发表或撰写过的研究成果，不包含本人或他人已 申请学位或其它用途使用过的成果。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名： 孙7 端 西北工业大学硕士学位论文绪论 1 研究背景 绪论 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。卡内基嗨隆大学的m i c h a e l m a u l d i l l 将j 0 h nk a v i t t 的网络蜘蛛s p i d e r 程序接入其索引程序，建立了l 弦o s 。 同年4 月，杨致远和d a v i df i l o 共同创建了超级目录索引y 拙o o ，并成功使搜索 引擎的概念深入人心。 随着互联网规模的急剧膨胀，搜索引擎成为现代信息获取的重要手段之一。 目前主流搜索引擎分为全文搜索引擎、目录搜索引擎和元搜索引擎。全文搜索引 擎主动派出s p i d e r 收集网页信息，根据网页关键字进行查询索引。目录搜索引擎 在人工基础上为网页编制等级式主题指南或主题目录，方便用户浏览感兴趣的网 页信息。元搜索引擎对多个搜索引擎返回的结果进行重复排除、重新排序等处理 后，作为自己的结果返回给用户。 搜索引擎己成为一个新的研究和开发领域。其涉及到信息检索、人工智能、 计算机网络、分布式处理、数据库，数据挖掘、数字图书馆、自然语言处理等多 领域的理论和技术，具有综合性和挑战性。同时搜索引擎具有广泛而且稳定的客 户群体，有很好的经济价值，也引起了世界各国计算机科学界和信息产业界的高 度关注。 信息过滤和个性化服务是搜索引擎的一个发展趋势。其使用自动获得的领域 模型、用户模型知识进行信息搜索、索引、过滤，并自动将用户感兴趣的、对用 户有用的信息提交给用户。该机制具有不断学习、适应信息和用户兴趣不断变化 的能力，从而提供个性化服务。本文作者借参与美国公司与西北工业大学合作项 目之机，得以对建立于搜索引擎原理之上的信息过滤和用户个性化服务的体系结 构和实现方法有全面了解及分析。根据实际参与该项目设计和实现经验，本文将 对搜索引擎的实现机理进行全面分柝，并对相关技术进行详细讨论。 2 本文主要工作 作者参与美方与西北工业大学两期合作项目“个人信息挖掘助手”( p e r s o n a l h f o 皿a t i o nm i i l i i i g a s s i s 恤t ) 和“智能在线r s s 阅读器”( i n t c l l i g 龃to i l l mr s s r e a d 盯) 的开发。在项目中积累了大量w 西数据挖掘、搜索引擎以及信息检索知 识。 “个人信息挖掘助手”是结合浏览器插件和w e b 服务的网页信息挖掘工具， 西北1 = 业大学硕十学位论文 绪论 包括针对网页内容的信息挖掘，在线购物功能，在线地图功能，和图形化记录网 页历史访问功能。并提供基于浏览器插件的搜索，高光，网页嵌入式t a g 等功能。 “智能在线r s s 阅读器”是结合用户兴趣和语义分析的智能在线r s sf e e d s 阅 读器，包含当代搜索引擎的基本功能。添加热门话题，f e e d s 分类下载过滤，文 章过滤，热门话题间关系与变化趋势等元素，并针对不同注册用户提供相关兴趣 信息，具有非常广阔的应用前景。 结合项目参与经历，本文主要完成以下工作： ( 1 ) 根据全文搜索引擎原理，勾勒搜索引擎的体系结构框架。 ( 2 ) 网页搜集，完成针对用户兴趣的主题网页信息收集工作。 ( 3 ) 网页预处理，完成网页内容分析、索引建立，以及网页消重工作。 ( 4 ) 网页查询服务，完成针对不同用户的网页信息过滤和检索。 3 本文结构 全文体系结构如下： 绪论：综述本文背景和体系结构。 第一章：搜索引擎综述 第二章：主题网页信息收集 第三章：网页信息提取和索引建立 第四章：网页信息查询服务 结束语：总结本文成果，指出进一步发展方向。 2 西北丁业大学硕士学位论文 第一章搜索引擎综述 第一章搜索引擎综述 本章对搜索引擎进行概括性描述。首先介绍了搜索引擎发展的历史与当前现 状。其次针对不同搜索引擎，本文简要叙述了当前搜索引擎的技术分类，主要工 作流程和评价搜索引擎的技术指标。最后勾画了搜索引擎的发展趋势。本章为后 面进一步讨论奠定了基础。 1 1 搜索引擎历史与现状 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆 炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大 众信息检索需求的专业搜索网站便应运而生了。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h 猫m 卸l d m 将 j o l l i ll e a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的【，y c o s 。同 年4 月，斯坦福( s t a i l f b r d ) 大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e 矗v m g ) 共同创办了超级目录索引，并成功地使搜索引擎的概念深入人心。 从此搜索引擎进入了高速发展时期。 1 9 9 5 年，一种新的搜索引擎形式出现了一一元搜索引擎。用户只需提交一 次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引 擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给用户 第一个元搜索引擎，是w 瑚l i n 垂o n 大学硕士生e r i cs e l b e r g 和o r e 晒i 的 m 如c r a w l c r 。元搜索引擎概念上好听，但搜索效果始终不理想，所以没有哪个元 搜索引擎有过强势地位。 1 9 9 8 年1 0 月之前，g o o 哲e 只是s t a l l 如r d 大学的一个小项目b a c 蹴b 。1 9 9 5 年博士生l 跚了p a g e 开始学习搜索引擎设计，于1 9 9 7 年9 月1 5 日注册了 g o o 硝e c o m 的域名，1 9 9 7 年底，在s e 唱e yb r i n 和s c o 仕h 勰s 强、a 1 a 1 1s t 砌e r g 的共同参与下，b a c h r u b 开始提供d e m o 。1 9 9 9 年2 月，g o o 四e 完成了从p h a 版到b e t a 版的蜕变。g o o 出e 公司则把1 9 9 s 年9 月2 7 日认作自己的生日。g o o d e 在p a g e r a 】 1 1 ( 、动态摘要、网页快照、d a i l y r e 如s h 、多文档格式支持、地图股票 词典寻人等集成搜索、多语言支持、用户界面等功能上的革新，像舢t a v i s t a 一样， 再一次永远改变了搜索引擎的定义。在2 0 0 0 年中以前，g o o 毋e 虽然以搜索准确 性备受赞誉，但因为数据库不如其它搜索引擎大，缺乏高级搜索语法，所以使用 价值不是很高，推广并不快。直到2 0 0 0 年中数据库升级后，又借被y 曲o o 选作 西北t 业人学硕十学位论文 第一章搜索引擎综述 搜索引擎的东风，才一飞冲天。目前，互联网上有名有姓的搜索引擎已达数百家， 其检索的信息量也与从前不可同日而语。 随着网上内容的爆炸式增长和内容形式花样的不断翻新，搜索引擎越来越不 能满足挑剔的网民们的各种信息需求。目前的搜索引擎仍然存在不少的局限性。 从1 9 9 6 年起，搜索引擎技术开始注重网页质量与相关性的结合，这主要是通过： 对网上的超链结构进行分析、对用户的点击行为进行分析、与网站目录相结合。 最新的趋势则是搜索的个性化和本地化。入门网站的个性化已经比较成熟了，但 是搜索引擎的个性化并没有得到解决，不同的人使用相同的检索词得到的结果是 相同的。也就是说搜索引擎没有考虑人的地域、性别、年龄等方面的差别。 d 眦c t h i t 等公司一年前开始了个性化方面的研发工作，但至今没有推出任何 产品。本地化是一个比个性化更明显的趋势。随着互联网在全球的迅速普及，综 合性的搜索引擎已经不能满足很多非美国网民的信息需求。近来，y a h 0 0 1 、 玳k t o 、i ，y c o s 等公司不断推出各国、各地区的本地搜索网站，搜索的本地 化已经是势不可挡。 1 2 搜索引擎技术 1 2 1 搜索引擎技术分类 按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类： ( 1 ) 目录搜索引擎：以人工方式或半自动方式搜集信息，由编辑员查看信息 之后，人工形成信息摘要，并将信息置于事先确定的分类框架中。信息大多面向 网站，提供目录浏览服务和直接检索服务。该类搜索引擎因为加入了人的智能， 所以信息准确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息 更新不及时。这类搜索引擎的代表是：呦o o 、l 0 0 ks m a n 、o p d i r e c 幻r y 、g o 例d e 等。 ( 2 ) 全文搜索引擎：由一个称为蜘蛛( s p i d 盯) 的机器人程序以某种策略自 动地在互联网中搜集和发现信息，由索引器为搜集到的信息建立索引，由检索器 根据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式是面向网 页的全文检索服务。该类搜索引擎的优点是信息量大、更新及时、毋需人工干预， 缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。这类搜索 引擎的代表是：灿t a v i s t a 、n o r i h 锄n g h t 、e x c i t e 、h f o s e e k 、i i l l 【t o m i 、 f a s 俯a s t s e a r c h 、l 弦o s 、g o o g l e ；国内代表为：“天网”、悠游、0 p e l l f i n d 等。 ( 3 ) 元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同 4 西北工业大学硕十学位论文 第一章搜索引擎综述 时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为 自己的结果返回给用户。服务方式为面向网页的全文检索。这类搜索引擎的优点 是返回结果的信息量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能， 用户需要做更多的筛选。这类搜索引擎的代表是w e b q a w l e r 、i n f o m a r k e t 等 1 2 2 搜索引擎工作流程 互联网是一个宝库，搜索引擎是打开宝库的一把钥匙。然而，绝大多数网民 在搜索引擎的相关知识及使用技巧上能力不足。国外的一次调查结果显示，约有 7 1 的人对搜索的结果感到不同程度的失望作为互联网的第二大服务，这种状 况应该改变。互联网的迅速发展，导致了网上信息的爆炸性增长。全球目前的 网页超过2 0 亿，每天新增加7 3 0 万网页。要在如此浩瀚的信息海洋里寻找信息， 就像“大海捞针”一样困难。搜索引擎正是为了解决这个“迷航”问题而出现的 技术。搜索引擎的工作包括如下三个过程，如图1 一l 所示： 图1 一l 搜索引擎工作流程 ( 1 ) 在互联中发现、搜集网页信息； 需要有高性能的“网络蜘蛛”程序( s p i d e r ) 去自动地在互联网中搜索信息。 西北工业大学硕十学位论文第一章搜索引擎综述 一个典型的网络蜘蛛工作的方式，是查看一个页面，并从中找到相关信息，然 后它再从该页面的所有链接中出发，继续寻找相关的信息，以此类推，直至穷尽。 网络蜘蛛要求能够快速、全面。网络蜘蛛为实现其快速地浏览整个互联网，通常 在技术上采用抢先式多线程技术实现在网上聚集信息。通过抢先式多线程的使 用，你能索引一个基于u i 也链接的w 曲页面，启动一个新的线程跟随每个新的 u r l 链接，索引个新的u r l 起点。当然在服务器上所开的线程也不能无限膨 胀，需要在服务器的正常运转和快速收集网页之间找一个平衡点。在算法上各个 搜索引擎技术公司可能不尽相同，但目的都是快速浏览w 曲页和后续过程相配 合。目前国内的搜索引擎技术公司中，比如百度公司的网络蜘蛛采用了可定制、 高扩展性的调度算法使得搜索器能在极短的时间内收集到最大数量的互联网信 息，并把所获得的信息保存下来以备建立索引库和用户检索。 ( 2 ) 对信息进行提取和组织建立索引库； 关系到用户能否最迅速地找到最准确、最广泛的信息，同时索引库的建立也 必须迅速，对网络蜘蛛抓来的网页信息极快地建立索引，保证信息的及时性。对 网页采用基于网页内容分析和基于超链分析相结合的方法进行相关度评价，能够 客观地对网页进行排序，从而极大限度地保证搜索出的结果与用户的查询串相一 致。新浪搜索引擎对网站数据建立索引的过程中采取了按照关键词在网站标题、 网站描述、网站u r l 等不同位置的出现或网站的质量等级等建立索引库，从而 保证搜索出的结果与用户的查询串相一致。新浪搜索引擎在索引库建立的过程 中，对所有数据采用多进程并行的方式，对新的信息采取增量式的方法建立索引 库，从而保证能够迅速建立索引，使数据能够得到及时的更新。新浪搜索引擎在 建立索引库的过程中还对用户搜索的查询串进行跟踪，并对查询频率高的查询串 建立c h e 页。 ( 3 ) 由检索器根据用户输入的查询关字，在索引库中快速检出文档，进行文 档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户。 这是对前两个过程的检验，检验该搜索引擎能否给出最准确、最广泛的信息， 检验该搜索引擎能否迅速地给出用户最想得到的信息。对于网站数据的检索，新 浪搜索引擎采用c l i 舔e n ，e r 结构、多进程的方式在索引库中检索，大大减少了 用户的等待时间，并且在用户查询高峰时服务器的负担不会过高( 平均的检索时 间在o 3 秒左右) 。对于网页信息的检索，作为国内众多门户网站的网页检索技 术提供商的百度公司其搜索引擎运用了先进的多线程技术，采用高效的搜索算法 和稳定的u n 平台，因此可大大缩短对用户搜索请求的响应时间。作为慧聪i 系列应用软件产品之一的i s e a r c l l 2 0 0 0 采用的超大规模动态缓存技术，使一级响 应的覆盖率达到7 5 以上，独有的自学习能力可自动将二级响应的覆盖率扩充到 6 西北工业大学硕士学付论文第一章搜索引擎综述 2 0 以上。 1 2 3 搜索弓l 擎技术指标 搜索引擎的目标就是在非常短的时间内搜索的信息全面并且准确。传统信 息检索系统的性能参数，召回率和精度同样也可以衡量一个搜索引擎的性能。 对于信息获取系统而言，1 9 6 6 年c l c v e r d o n 给出了信息获取系统的六个主要评价 指标： ( 1 ) 信息的覆盖率，即该系统所包含信息的范围，数量； ( 2 ) 系统响应时间，即查询请求与结果返回之间的平均时间间隔； ( 3 ) 结果输出方式，即结果是以什么样的格式给出的； ( 4 ) 用户获取搜索结果所需要付出的努力； ( 5 ) 召回率是检索出的相关文档数和文档库中所有的相关文档数的比率，衡 量的是检索系统( 搜索引擎) 的查全率； ( 6 ) 精度是检索出的相关文档数与检索出的文档总数的比率，衡量的是检索 系统( 搜索引擎) 的查准率。 ；我们可以将w e b 信息的搜索看作一个信息检索问题，即在由w e b 网页组 成的文档库中检索出与用户查询相关的文档。所以我们可以用衡量传统信息检索 系统的性能参数一召回率( r 船a 1 1 ) 和精度( p r e c i s i ) 衡量一个搜索引擎的性 能。对于一个检索系统来讲，召回率和精度不可能两全其美：召回率高时，精度 低，精度高时，召回率低。所以常常用1 1 种召回率下1 1 种精度的平均值( 即 1 1 点平均精度) 来衡量一个检索系统的精度。对于搜索引擎系统来讲，因为没 有一个搜索引擎系统能够搜集到所有的w e b 网页，所以召回率很难计算。目前 的搜索引擎系统都非常关心精度。 影响一个搜索引擎系统的性能有很多因素，最主要的是信息检索模型，包括 文档和查询的表示方法、评价文档和用户查询相关性的匹配策略、查询结果的排 序方法和用户进行相关度反馈的机制。 1 3 搜索引擎发展趋势 搜索引擎经过几年的发展和摸索，越来越贴近人们的需求，搜索引擎的技术 也得到了很大的发展。搜索引擎的最新技术发展包括以下几个方面： 、提高搜索引擎对用户检索提问的理解 二、对检索结果进行处理 1 基于链接评价的搜索引擎 7 西北丁业大学硕士学位论文第一章搜索引擎综述 2 基于访问大众性的搜索引擎 3 去掉检索结果中附加的多余信息 三、确定搜索引擎信息搜集范围，提高搜索引擎的针对性 1 垂直主题搜索引擎 2 非w w w 信息的搜索 3 多媒体搜索引擎 四、将搜索引擎的技术开发重点放在对检索结果的处理上，提供更优化的检 索结果 1 纯净搜索引擎 2 元搜索引擎 1 4 小结 本章概括描述了搜索引擎的基本知识，包括搜索引擎的发展历史以及现状、 搜索引擎在技术上的分类、搜索引擎的主要工作流程，评价搜索引擎的标准，最 后给出了搜索引擎的一些发展趋势。该章作为综述性描述，为后面详细介绍搜索 引擎工作的各部分奠定基础。 西北工业大学硕士学位论文第二章主题网页信息收集 第二章主题网页信息收集 本章对搜索引擎系统的第一部分一网页信息收集进行了详细描述，首先介绍 网页信息收集方式分类，并对全文搜索引擎所使用的网页收集的原理和搜索策略 进行详细描述。其次对基于网络蜘蛛s p i d e r 之上的一种f & 璐e dc r a w l c f 设计进行 了原理和爬取策略的描述。 2 1 网页信息收集概述 2 1 1 网页信息收集方式分类 目前，针对搜索引擎的网页信息收集方法主要分为采用s p i d e r 网络蜘蛛进行 收集，人工目录式收集，基于其他搜索引擎返回结果的信息收集方法。这些主要 对应于全文搜索引擎，目录式搜索引擎和元搜索引擎的网页信息收集方式。 t 全文搜索引擎主动派出s p i d e r 网络蜘蛛，在一定的口内以某种策略自动地 在互联网中搜集和发现信息。具有信息量大、更新及时、毋需人工干预，缺点是 返回信息过多，有很多无关信息，用户必须从结果中进行筛选。本文2 1 2 小结 将详细介绍全文搜索引擎的网页信息收集方式 随着搜索引擎的发展，全文搜索引擎风头正劲，目录式搜索引擎逐步向全文 搜索引擎靠拢，实现目录与全文搜索引擎相结合。有观点认为目录式搜索引挚并 不是真正意义上的搜索引擎，仅仅是按目录分类的网站链接列表而已，用户在查 询信息的时候都不需要使用关键字，只需要根据目录进行索引就可以。目录式搜 索引擎网页信息收集方式为：网页的拥有者向搜索引擎提交网址，搜索引擎会在 一定时间内派出s p i d e r ，而网页的甄别和分类都是依靠人工识别的方法，具有较 高的精确度；同时并不是所有提交的网页都会被收录入该类型搜索引擎的数据 库，因此多向外提供一些链接，更利于被搜索引擎发现和收录。由于加入了人的 智能，以此方式收集的网页具有信息准确、导航质量高，缺点是需要人工介入、 维护量大，信息量少、信息更新不及时。 同期发展的元搜索因其搜索机制，从未在搜索引擎市场占据过主流地位。而 且元搜索引擎的技术关键在于通过结果归并和过滤提高检索精度和效率，因此主 要目标并不在于网页信息收集。 9 西北工业大学硕士学位论文第二章主题网页信息收集 2 1 2 全文搜索引擎的网页信息收集方式 2 1 2 1 原理描述 具体搜集过程，抓取网页信息的方法，可以有不同考虑。最常见的s p i d e r 网络蜘蛛“爬取”，是将w 曲上的网络集合看成一个有向图，搜索过程从给定的 u r l 集合s ( 或者说“种子”) 开始，沿着网页中的链接，按照深度优先、广度 优先或者某种策略进行遍历，不停的从s 中移除u r l ，下载相应的网页，解析 出网页中的超链接u 1 也，看是否已经被访问过，将未访问过的那些u i 也加入 该个过程递归进行，直到s 为空或者采取某种控制策略结束爬取。整个过程可以 形象的想象为一个蜘蛛( s p i d e r ) 在蜘蛛网( w 曲) 上面爬行( c r a w l ) 。 这种方式的好处除了概念很漂亮，一般实现起来也不困难外，还有很重要的 一条是容易通过一定的策略，是搜索到的网页相对比较“重要”。任何搜索引擎 是不能将w 西上的网页搜集完全的，通常都是在其他条件的限制下决定搜索过 程的结束( 如磁盘满，或者搜索时间已经太长了) 。因此就有一个尽量使搜到的 网页比较重要的问题，这对于那些不追求很大的数量覆盖率的搜索引擎特别重 要。研究表明，按照广度优先搜索方式得到的网页集合要比深度有些搜索得到的 集合重要。这种方式的一个困难是要从每一篇网页中提取出所含的u r l 。由于 h ，i 咖，的灵活性，其中出现u r l 的方式各种各样，将这个环节做的彻底并不容 易。同时，由于w 曲的“蝴蝶结”形状，这种方式搜集到的网页不大会超过所 有目标网页数量的2 3 。 另外一种可能的方式是在第一次全面网页搜集后，系统维护相应的u r l 集 合s ，往后的搜集直接基于这个集合。每搜到一个网页，如果它发生变化并含有 新的u r l ，则将它们对应的网页也抓回来，劳将这些新的u r l 也放到集合s 中； 如果s 中某个u 也对应的网页已经不存在了，则将它从s 中删除。这种方式也 可以看成是一种极端的宽度优先搜索，即第一层是一个很大集合，往下最多只延 伸一层。 还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址，系统在一定 时间内定向向那些网站派出s p i d e r 蜘蛛程序，扫描该网站的所有网页并将有关信 息存入数据库中。大型商业搜索引擎一般都提供这种功能。 大规模搜索引擎服务的基础应该是一批预先搜集好的网页，这些网页的维护 分为定期搜索和增量搜索： 定期搜索，每次搜索替换上一次的内容，也成为“批量搜索”。由于每次都 是重新来一次，对于大规模的搜索引擎来说，每次搜集的时间通常会花几周。而 l o 西北工业大学项士学位论文第二章主题网页信息收集 且由于这样做的开销比较大，通常两次搜集的时间问隔也不会短。例如g o o 出e 在一段时间曾是2 8 天来一次。这样做的好处是系统实现比较简单，缺点是“实 效性”不高。而且带来重复搜集的额外带宽消耗。 增量搜集，开始时搜集一批，往后只是搜集新出现的网页和被搜集后出现改 变的网页，并且删除自从上次搜集后已经不存在的网页，并从库里删除。优点在 于“实效性”比较好，但是缺点时系统实现起来比较复杂，不仅在于搜索过程， 而且还在于创建索引的过程。 2 。1 ，2 2 爬取策略 目前w 曲上信息量庞大，试图穷尽搜索比较困难。但是，完全有可能在搜 索的过程中尽量优先搜集用户感兴趣的信息，或者重要性比较高的信息。这样尽 管没有穷尽w 如上的信息，但是已经搜集的信息对用户的利用价值也会很高。 这一点是通过加权的启发式搜索算法来解决的。每个u 也有自己的权值，反映 其文档内容的重要性，没有访问的u r l 有预测权值，用来预测该u r l 的重要程 度，访问时根据权值大小决定优先顺序。根据搜集经验，体现网页重要度的特征 有： i ：( 1 ) 网页的入度大。表明被其他网页引用次数多 ：( 2 ) 某网页的父网页入度大 。( 3 ) 网页的镜像度高，说明网页的内容比较热门，从而显得重要 “( 4 ) 网页的目录深度小，易于用户浏览到 ( 5 ) 根据上述描述，权值的选择可以有很多种，例如： ( 6 ) 父u r l 的权值，即本u r l 所在文档的权值 u 也的a n c h o r ( 锚文字) 权值，即出现在h r m l 文件种对u r l 的描述 信息的权值 。( 8 ) u r l 目录长度权值，每个u i 也都有一个目录，一般目录短的u r l 重要 性要相对高些 ( 9 ) 被别的文档引用次数权值 ( 1 0 ) 加入者信息 ( n ) u r l 的域名的深度。 2 2 主题网页信息收集原理描述 w 曲信息分布的局部专题化是互联网信息所呈现的特征之一，伴随着面向主 题信息获取的需求越来越多，用户希望主题信息获取能够做到领域信息搜集更加 西北工业大学硕士学位论文 第二章主题网页信息收集 完备、更新速度更快、并能够主动发现领域内的主要资源，进而研究主题信息的 变化及其分布特征。由于主题信息一般只占整个w 曲很小的一部分，并且具有 分散性，因此传统的基于广度优先货深度优先的搜索策略在w 曲信息搜集的效 率上难以达到期望要求。面向主题的信息搜集系统的主要认为是利用优先的网络 带宽、存储容量和较少的时间，抓取尽可能多的网页。 目前，w 曲主题信息搜集的主要方法来源子s a l 出a b a 而于1 9 9 9 年构建的 f b c l l s e dc r a w l i l l g 系统，该系统采用基于样例网页驱动的主题信息的搜集方法， 所搜集的主题信息由用户通过选定样例网页来确定，并基于如下假设： 如果页面l l 是一个于主题相关的页面( 正例) ，u 到页面v 有一个超链接， 则页面v 是正例的概率远远大于在w 曲上随即抽取的一个页面。 为考察w 曲上主题信息分布的特征，d a v i s o n 从一个称为d i s c o w 曲的研究 型搜索引擎的网页库中抽样获取了l o 万个页面，通过大量的反复试验，得到了 不同情形下，两个页面之间的平均相关度。该试验利用向量空间模型中向量夹角 的余弦值来度量两个页面之间的相似度，其中词条的权重用t f d f 来计算。 设随机变量u 和v 表示w 曲上的两个页面，当u 和v 为w 曲上随机抽取的 两个页面时，用r 锄d o m 表示他们之间相似度的均值；当u 和v 被同一个页面所 链接，即：u 和v 具有相同的父节点页面时，用s i b h n g 表示他们之间相似度的 均值；当u 为w 曲上随机抽取的一个页面，u 是v 父节点且u 和v 具有同一个主 机( 由主机名确定) 时，用s 锄e d o m a i l l 表示他们之间相似度的均值；当u 为 w 曲上随机抽取的一个页面，u 是v 父节点，但u 和v 位于不同主机( 由主机名 确定) 时，用d i 衄o m a i n 表示他们之间相似度的均值。统计试验显示： s 锄e d 锄a i n 对具有较高的相似度，s i b l i n g 对次之，d i 任d o m a i n 略差，随机抽 取的两个页面( 砒m d o m ) 的相关度极低。由此亦可看到w 曲信息组织的局部化 特征。从一个网页开始的随机冲浪，其主题迁移的可能性极大。 实现上，主题爬虫f o c u s e d c r a w l 盯与全文搜索引擎采用的网络蜘蛛s p i d e r ， 最大的差别在于网页信息收集关注内容不同。网络蜘蛛s p i d c r 采用优先策略尽可 能获取较多的、重要性可能较高的网页。主题爬虫对于网页的获取不在于获得更 多的网页，而在于获得与用户兴趣相关，质量较高的网页。主题爬虫f o c u s e d c r a w l c r 可以认为是网络蜘蛛s p i d 盯的进行搜索时的一种特例，其特点主要区别 在爬取起点和搜索策略。 西北工业大学硕十学位论文第二章主题网页信息收集 2 3 一种主题网页信息收集系统 2 3 1 ，收集原理 2 3 1 1 网页分类 网页类型是根据网页内容的表现形式进行划分的，在本小节中将网页分为三 类：主题网页( t o p i c ) 、h u b 网页( h u b ) 、图片网页( p i a t i l r e ) 。其中，主题网页 是指网页中通过文字描述了一件或多件事物，是有一定主题的，如一张具体的新 闻网页就是典型的有主题网页。h u b 网页是指专门用来提供网页导向的网页，因 而是超链接聚集的网页，如门户网站的首页就是典型的h u b 网页。图片网页是 指网页的内容是通过图片的形式体现的，其中文字很少，仅仅是对图片的一个说 明，如某个机构包含图片的人员介绍网页就是典型的图片网页。 将网页分为上述三个类型是因为三类网页在用途和处理方法上存在较大的 差别。其中h n b 网页与其它两类网页的区别在于网页在w 曲上发挥的作用不同， h u b 网页通常不会具体的讲述一件事物，而是提供关于相关信息的链接集。而图 片嗣页与其它两类网页的区别在于处理的方法不同，由于图片网页的内容是通过 图片表达的而不是通过文字，因而，传统信息处理领域的方法对图片网页是不够 有效的。三类网页间的区别导致很多应用领域都会对它们作适当的区别。 彳网页类型识别 特征项被定义为一个词或者短语，在传统的文本处理领域，一篇文档可以看 作是一组特征项的集合。这组特征项对文档主题具有一定的描述能力，是文档的 一种抽象表示。在本文后面的章节将对特征项进行详细描述。特征项在网页类型 识别过程中起到重要作用。 一种基本网页类型识别方法描述如下：依据网页中特征项数与图片数和超链 数的比值可以为每个网页设定一个类型，分为t o p i c 、h u b 、p i c t u ”三种。如果网 页中特征项与图片数的比值小于某个阈值，该内容块就是d i c t 【l r e 类型，如果网 页中作为a n c h t e x t ( 锚文字) 出现的特征项与该网页中总词项数的比值小于某 个阕值，该内容块就是b n b 类型，否则为幻p i c 类型。 对于主题网页信息收集而言，确定主题b o p i c 网页和主题h u b 网页也是重要 的环。如果t o p i c 网页中，属于该主题的特征项比例大于某个阀值，可认为该 t o p i c 网页属于主题范围。如果h u b 网页中链接的网页中属于主题t o p i c 网页的比 例大于某个阀值，则认为该h u b 网页属于主题范围。 西北丁业大学硕士学位论文第二章主题网页信息收集 2 3 1 2 基于h u b 网页的主题网页收集 图2 1 描述了这样的事实：般t o p j c 网页的内容固定不变，但是指向t o p j c 网页的h u b 网页容易随着信息变化而改变该页面的链接指向，比如新闻h u b 网页、 门户网站的首页。而t o p i c 网页上也可能提供一些超链接，比如友情链接等，指 向一些同主题t o p i c 的h u b 网页。基于上述事实，该主题网页采集工作，首先从 一定的h u b 网页开始，抓取相应主题t o p i c 网页。在抓取的过程中，系统将不停 收集新h u b 网页，合并入以前的h u b 网页，一起作为下一次抓取的起始点，以加 快获取t o p i c 网页的速度。 o 表示鼬一页口表一一页一一黼 图2 1t o p i c 网页和h u b 网页 该系统采用广度优先抓取策略进行抓取，并综合考虑网页链接指向、u d 信 息以及页面信息对一个未爬取l 的影响，同时根据对所获超链接进行主题预测 决定进一步抓取任务。为防止网页爬取存在的主题漂移( t o p i c “r ) 问题，该系 统对已采集网页进行主题相关性验证，对不满足要求的网页进行剪枝。如果预测 满足主题t d p i c 的超链接个数与实际获取的超链接个数相差太远，认为爬取偏离 了主题，可以结束爬取。 2 3 2 系统描述 基于上述原理，我们设计了如下系统，称为f i a ( f o c u s e d1 1 1 t e 】l i g ta g t ) ， 用于收集面向主题的网页信息，如图2 2 描述。整个f n 系统从起始h u b 库开 始爬取。由于起始h u b 库设计为由用户或专家提供的主题h u b 网页，因此，不 西北工业大学硕十学位论文第二章主题网页信息收集 需要验证该库中h u b 网页与主题的相关程度。以后，系统自己会根据收集到的 h u b 网页自动进行判定，如果判定结果满足条件，就将这些新收集到的h u b 网 页加入到起始h u b 网页库中，作为新的爬取起始点。这种收集方法，加快了新 主题网页的收集速度。因为新的主题网页被用户发现的最好方法就是被h u b 网 页链接。因此从收集到的主题h u b 网页开始爬取是接触到可能相关的主题网页 的最好方法。下面着重描述几个a g e m 之间的关系。 c = ：衰示数据滤争表示操作流 图2 2f 1 a 系统模型 ( 1 ) 主题爬取a g e n t 做为f 认系统的一部分，主题爬取a g c 址从存储在起始h u b 库的t o p i ch u b 网页开始爬取，这部分称为预收集。由于此时已经认定由泖i ch u b 指向的网页 都是主题相关，因此在t o