（计算机应用技术专业论文）搜索引擎中数据对象研究——树藤共生模型的研究与应用.pdf

y 3 9 8 4 5 3 摘要 本文主要研究搜索引擎的原理结构及其所处理数据资源对象的结构、特点与模 刑。论文对现有的数据模型与应用进行了分析、讨论，指出了它们在数据描述、应 川臂方丽的局限性。在此基础之上，提出了一种新的互联网数据模l ! 一一树藤j g 生 模型，该模型能够较好地的描述异质、异构的互联网数据资源并且定义了对象的 井、差、关系投影、粘帖、剪切、选择等操作，这些运算操作使得搜索引擎对互联 网资源进行分析、整理、查询时具有更高的准确性和更大的灵活性。结合互联网资 源的构建规则、链接分布规律和u r l 命名规则，论文提出了树藤共生数据模j 锂的 重建算法，实验结果验证了树藤共生模型的有效性与合理性，在此基础上初步讨论 了树膝共生模型在浏览导航、网页分类和r e i n f o r c e m e n tl e a r n i n g 算法中的鹿川。 关键词：搜索引擎，数据模型，树藤共生对象模型 孟， a b s t r a c t 1 1 1t h i sp a p e lt h ew o r k i n g m e c h a n i s m sa n ds t r u c t u r eo f s e a r c he n g j n e s a r cd i s c u s s e d , a sw e l la st h ec o n s t r u c t i o n ，f e a t u r e sa n dm o d e l s o fi n t e r n e td a t at h a ta s 8 0 c j 8 t 。dw i t ht h e s e a j c he n g i n c s s e v e r a ld a t am o d e l s a r ei n t r o d u c e d ，a n d t h e i rl i r a j t a t j o n s i nd a l a d e s c r i p t i o na n da p p l i c a t i o na r e r e v e a l e d o nt h eb a s i s o f t h ef e a t u r e sa n df a b 。j 。0 f i n f e 。t d a t a an e wi n t e m e td a t am o d e l c a l l e dt r e e v i n es y m b i o s i sm o d e l ( t v m ) i 3 p o p 0 8 e d t h i si n o d e lp r o v i d e sp r e c i s e a n df l e x i b l ed e s c r i p t i o n o fi n t e r n e th a t e r o g e n e o “5 d a t a s e v e r a lo p e r a t i o n sa r ed e f l n e di n c l u d i n ga n d ，s u b t r a c t , r e l a t i o n ，p a s t e ，c u t a n ds e l e c t , w h i c hm a k es e a r c he n g i n e sa n a l y z e ，p r o c e s sa n dq u e r yi n t e r n e t r e s o “。e m o r e p r e c i s e l ya n df l e x i b l y b a s e do nt h eo r g a n i z a t i o nr u l e so f i n t e r n e td a t a , t h ed i s t r i b u t i o nl a w so fh y p e 舳k 8 a n dt h en a m er u l e s o fu r l ，aa l g o r i t h m o ft v mr e b u i l d i n g i se s t a b l i s h 。d ，a n d s a t i s f a c t o r ye x p e r t m e r i t r e s u l t sa r eo b t a i n e db ya p p l y i n g t h i s a l g o r i t h m f u r t h e r m o r e , e 肋r t sa r em a d eb y 印p l y i n go f t v mo nb r o w s en a v i g a t i o n ，w e bp a g ec l a s s i f i 。“o n ”d r e i n f o r c e m e n tl e a m i n ga l g o r i t i i m 。 k e y w o r d s s e a r c he n g i n e ，d a t am o d e l ，t r e e 。v i n es y m b i o s i s m o d 。l 第一章绪论 第章绪论 1 1 互联网的发展及搜索引擎的诞生 h 联嘲涎生丁二十世纪六、七十年代，经过短短二十年的迅猛发展，规模日豁 增人，1 9 9 8 年互联网上有3 2 亿个页面，到1 9 9 9 年这个数字增加到了8 亿。联接 的嗍站越来越多，内容也越来越丰富，从最初的科研、教育、行政管理到体育、医 曲n 生、文化直至方兴未艾的电子商务【4 1 ，互联网已经愈来愈贴近我们的生活，井 深刻地影响着社会的格局，它引发了信息产业革命，把世界经济从传统工业、商业 经济带入到知识经济时代。所以人们称互联网是人类历史上最伟人的发明。 随着互联网的不断普及、发展，提供的信息越米越多，越来越广泛但商刘这 浩如烟海的信息海洋，往往让人感到无所适从。因为一个人所要获取的信息足有限 的，互联网上绝大多数的信息对他来说是没有浏览价值的，是信息垃圾。这就是为 j - 引导人们快速查阅到真正需要的网站内容，有人开始专门收集网站的内容并分门 别类加以整理，然后出版成书籍，这是搜索引擎的雏形，这些书籍就是在9 0 年代 初曾人量发行过的网站黄页( 网址簿) 。从这些。f 上获取网站信息井不方便，而h i 嗣为网站内容更新快而没有时效性。1 9 9 3 年，美籍华人杨致远( j e r r yy a n g ) 和人 1 j 赞罗( d a v i df i l o ) 敏锐地发现了这个问题，并开始在自己的网站上创建数据库， 收集人量的网站信息，供浏览者免费查询，并给他们的网站起了个名字叫y a h o o ! ， 住没有任何经济回报的情况下，他们以极大地热情投入这项i 1 ：f l - 并坚持f 米。1 9 9 6 年3 月7 日y a h o o ! 上市，市值8 5 亿美元，1 9 9 7 年市值2 8 亿美元，1 9 9 9 年市值3 9 0 亿美元。 1 ，2 搜索引擎技术发展 y a h o o ! 是最早的搜索引擎之一，它创造了搜索引擎发展史的奇迹。现在，随着 户联网的持续高速发展搜索引擎的数量愈来愈多，影响比较大的有e x c i t e f h l t p ：w w w e x e i t e c o r n ) 、y a h o o ! ( h t t p ：w w w y a h o o c o m ) 、a l t a v i s t a ( h t t p ：w w w a l t a v i s t a d i g i t a l c o r n ) 、h o t b o t( h t t p ：w w w h o t b o tc o r n ) 、 i n f o s e e k ( h t t p ：h w w w i n f o s e e k c o r n ) 、l y c o s ( h i t p ：w w w 1 y c o sc o r n ) 邪l n o r l b e r n l i g h t ( h c f p ：肌v w m nj s e a r c h c o r n ) 等 j ，对搜索引擎的研究也愈来愈深入，搜索引擎的技术 也日趋成熟起来。 在搜索引擎发展的初期，数据的整理、分类：l 作完全依靠人j l ：完成。人i 录入 有准确、可靠的优点，但速度慢，无法适应互联网上愈米愈快的发展趋势。这时产 生了有计算机自动录入、整理数据的技术，就是依靠某些软件，自动地依据超级链 第一章错论 按( h y p e r l i n k ) 从一个网页链接到另个网页，从一个网站链接到另个网站 汝墩网页内容井传送回搜索引擎，这些专门从网站上获取数据的程序被形象地称为 “网络蜘蛛”( w e bs p i d e r ) 或“机器人”( r o b o t ) 【“。尽管如此，搜索引擎所收录 的数据还足有限的，截止到1 9 9 9 年上半年，搜索引擎n o r t h e r nl i 曲t 收录了1 2 8 亿个网页，覆盖了互联网上1 6 的内容，y a h 0 01 的覆盖率为7 4 ，而l y c o s 只收 录了25 的互联网内容。它们传回的数据也由计算机通过自动分类( c l a s s i f i c a t i o n ) 支术米整理、分类供以后搜索引擎用户查询1 8 ”。由于计算机的识别、分类技术还 小足很完善，绝大部分的搜索引擎还是部分甚至全部地保留了人一i = 搜索、整理数据 的i ：作以获得较高的数据质量f ”】。 人部分搜索引擎是面向全体互联网用户的，像y a h o o ! 、a l t a v i s t a 、e x c i t e 、i n f c s e e k 等，它 j 本身从一开始就是设计为面向所有潜在的用户，它们的数据库容量非常火， 收集了数以千万、甚至以亿计算的网页内容，它们涉及的山容厂泛、但深度不够， 无法满足些专业性强的搜索引擎用户的要求，因此，一些专业搜索引擎应运而生， 它们专f 膳t 对某个领域方向，收集与之相关的数据，并依据具体领域的规划优化整 理分类、查询等方面的计算方法，以满足专业性较强的用户要求，这类搜索引擎通 常称为门户搜索引擎，像c o r as e a r c h ( h t t p ：w w w c o r a , w h i z b a n g , c cr n ) 、m lp a p e r s 【h i t p ：g u b b i oc s b e r k e l e y e d u m l p a p e r s y 和c i t e s e e r ( h t t p ：# c i t e s e e r n j n e c c o m c s ) f 等灶 专fj 针对计算机人工智能、机器学习研究方向的搜索引擎。c a m b r i d g e s o f t 公司开 发的c h e m f i n t l l e t ( h t t p c h e m f i n d e r c a m s o f t c o m ) 向化学：c 作者提供了化学物质信 息检索，b o t a n yo n l i n e ( h t t p ：n e r b b i o l , h r e g i n a , c a l i , , h t m l ) 是一个以植物学 内窬为核心的专题搜索引擎。近年来还出现一种搜索引擎技术，叫集成搜索引擎技 术，也称为元搜索引擎( m e t as e a r c he n g i n e ) ，它是将用户查淘需求同时向多个搜 索引擎提交，然后再把所得到的查询结果直接或经过定的处理后返回给用户，比 如m e t a c r a w l e r ( h t t p ：w w w m e t a c r a w l e r c o m ) ，它的搜索过程非常清楚，有深度， 爿且有组织，可以进行简单查询或适度复杂的搜索，还有s a v v y s e a r c h ( h t l p ：s a v v yc s c o ks t a t e e d u ：2 0 0 0 ) ，它支持二十种语言( 很遗憾，不包括中文) ， 功能也很齐全【”】。 j j 户所接触到的搜索引擎一般都是基于页面文本内容分析的，这些分析拽术一 般是基：r 文档向量模型4 l 其中部分原因是初期网络传输速度低、传输质量不可靠， 普通网站的内容都是文字形式。现在随着网络基础建设水平的提高，互联网上出现 了人量以图像、声音甚至视频信息为主的数据形式，截至到1 9 9 9 年2 月，互联网 共有人约i8 亿个“可索引”图像。用户对网上图像搜索的要求也在不断增k ，为 适应这个新的发展趋势，图像搜索技术得到越来越多的重视。许多大型搜索引擎象 a l t a v i s t a 、y f h o o ! 、l y c o s 、e x c i t e 等都增加或完善了其图像搜索功能，也山现了许 多专门搜索图像的搜索引擎，如成立于1 9 9 8 年的s c o u r ( w w w s c o h l c o i t i ) ，自称是 2 角一尊绪茁 第个基于w e b 的多媒体搜索引擎，哥伦比亚大学开发的实验性系统w e b s e e k ( d i s n e y c t r c o l u m b i a e d u w e b s e e k ) 是采用代理自动搜索可视信息并对其进行分类。 中国的互联网起步比美国、欧洲等发达国家和地区要晚，1 9 8 7 年9 月2 0 曰， 钱犬向教授发出我国第一封电子邮件从此揭开了中国人使刚i n t e r o e t 的序幕。搜 索引擎的发展也相对要慢一些，完全自主开发的搜索引擎技术少，购买国外成熟技 术的多，比如网易( h t t p ： w w w 1 6 3 c o r n ) 就是购买美国l n k t o m i 公司的搜索引擎技 术，现在网易已经转向与美国g o o g f e 公司合作。而国外搜索引擎在数据收集、整 理分类和查询等方面的技术主要是针对英语环境开发，不太适合中文这一特殊语言 的要求，因而有一定的局限性。 近年来国内也正在自主开展搜索引擎技术研究，并开发山实际的产 扎例如，化 人的天嘲l 、消华的网络指南针等，但是由于人才、技术、资金的原因，商业化的 白联网中文搜索引擎一直没有出现。1 9 9 9 年北京百度公司( h t t p ：w w w b a i d uc o r n ) 开发池基于页面内容分析的中文搜索引擎技术，而且已投入实际运行，最初向硅谷 动力( h t t p ：w w w e n e t c o r n ) 和中国人( h r t p ：w w w c h i n a r e n c o r n ) 提供服务，取得 了较好的应用效果，现在搜狐( h t t p ：f f w w w s o h u c o r n ) 、新浪( h l p ：w w w s i n a t o m c o ) 和i2 1 世纪( h t t p ：w w w 2 1 e n c o r n ) 也分别在2 0 0 0 年8 月、1 0 月和1 1 月采川了百 度的搜索引擎，中国人的搜索引擎界面“孙悟空搜索”( h t t p ：s e a r c h c h i n a r e nc o i n ) 逊f 发了一个基于自然语言查询的搜索界面，能够较为正确地分析刚户以自然语言 提出的中文提问。近期国内网站还推出了基于w a p p c 双平台的w a p 搜索引擎， 可以使用w a p 手机或计算机来使用该项服务，可以说中国目前的搜索引擎技术正 在赶上世界的发展水平。 1 3 搜索引擎目前所面临的问题 一个完按的搜索引擎包括网络蜘蛛( w e bs p i d e r ) 、分类和信息抽f f 双( c l a s s i f i c a l i o n a n di n f o r m a t i o na b s t r a c t ) 、用户查询服务( u s e rq u e r ys e r v i c e ) 等三个部分， i 构 示意图如图1 1 所示： 3 第一章绪论 网络蜘蛛足搜索引擎刖以获取互联网资源信息的程序，它“j 通过u r l 地址歌 戢“j j 刚资源，井从中分析、提取新的u r l 地址获取新的且联网资源：分类和 信息抽墩部分则将网络蜘蛛收集的资源进行分析、挺理归类； 1 j 户奁潮部分! l ! l l 负责 阳川，：- 提供信息检索功能；但是集成搜索引擎中没有网络蜘蛛和分类与信息抽收部 分，它们的信息源是其他搜索引擎的返同信息。 搜索引擎的研究同绕上述三个方向开展。搜索引擎中所廊川到的理论和技术包 拓互联嘲数据模， 研究、网页分类、浏览导航、语义识别、缓冲策略等。 我们1 1 1 道，在人丁智能领域，文字、语言的语义分析已经取得了较人的进展1 1 4 i ， 州已枉许多领域付诸实现，比如不同语言之间的翻译系统口2 】，甚至可以成功地进行 i 自音识_ ：i j 旧1 。在搜索引擎的网页分类、搜索域定向和自然查| 旬语句的解析等方而可 以借鉴它们的成功之处，但不能完全照搬，因为搜索引擎的数据库内容多，更新速 j 皇挑，需要处理的数据量太大，如果完全采用传统的人f ：智能方法加以分析、牲理， 往系统资源、时间上需要付出相当高昂的代价，实际上是无法实现的。 “联网l 的数据分布、组织结构有自己的特点，例如超级链接、m e a 、t i 6 l e 、 删t l 的树状拓扑结构等口4 ”j ，这些特点在传统方法所处理的传统对象中足没有的， 行以在分析、处理互联网上的数据时应该充分利月j 这些信息，花最短的时间的州问 获得准确的分析结果。 埘互联网数据模型的描述从很犬程度上影响到搜索引擎对数据处理的效率、jj ! 确率等。目前有关的研究没有充分考虑到互联网数据资源的有关特性，本文捉了 个新的数据摸型可以更好、更准确地描述互联网数据资源，f 可应川 ：刚负分类， 信息提取、浏览导航等多个领域。 搜索引擎技术发展到令天仍面对许多的问题，象专业搜索引擎的搜索域确认， 自动分类技术的准确性需要进一步提高，网络蜘蛛的搜索策略、数据更新策略需要 优化等等。 蚬在搜索引擎发展的一个新趋势是智能化，智能化主要体现在网锚蜘蛛的搜索 仃为、数据分类和自然语言查询等方面。有些搜索引擎已经开展一些相关研究和实 现，但效果并不让人满意，因此需要在上述研究领域取得突破性进展才能真l j ：地实 现搜索引擎的智能化。 1 4 本文的研究内容 本文对搜索引擎技术的当前发展状况进行研究探讨，对数据模型、内容的提取 与分类、智能网络蜘蛛、浏览导航等方面的研究做了深入的分析，揭示口前j i x 劂数据模型中对网站逻辑结构的忽视，并提出了树藤共生数据模型。与已有的数据 模型相比，该模型能更准确、有效地描述互联网的数据资源，并给山了在获得部分 4 第一章绪论 嘲站信息的情况下抽取有向树结构的算法与实现。该树藤共生模型可应h j j i 搜索引 擎中的搜索域判定、内容抽取与分类、浏览导航等方面，本文l ：作归纳如_ 卜： j 、系统地讨论了互联网数据资源的结构特点及当前的研究状况分析- ，现宵 研究模刑中对互联网数据模型描述的局限性，在现有研究的基础上提出了树藤k 生 模，与o i m 对象模型等数据模型相比，该模型可以比较丰i ! i 确地描述且联刚上舜 肤、异构的数据资源。 2 、在深入研究互联网数据资源特点的基础上，提出了树藤批生模z 聪对象的重 建算法。该算法可以对得到的互联网资源信息进行分析、处理能以很少的运算代 价重建互联网资源的树藤模型，这为树藤共生模型的实际应f j 打下了坚实的基础。 3 、分析研究搜索引擎中当前所引用的网页分类与内窬抽取技术，同前此类技 术一般是基于文档向量模型。在现有的研究基础之上，本文结合树藤! e 模j q 捉 了改进的网页分类方法，该方法可更准确地描述网页的内容及分布。 4 、分析了现有网络蜘蛛的原理与方法，特别关注智能蜘蛛搜索域刿定方向的 研究。本文结合r e i n f o r c e m e n tl e a r n i n g 算法与树藤共生模型，提出了改进 r e i n f o r c e m e n tl e a r n i n g 算法的思想。 5 、对当前流行的浏览导航技术，讨论了基于用户视图的浏览导航技术的不足 之处。本文结合搜索引擎技术与树藤模型内容，提出一种新的浏览导航方法，它可 为浏览者提供准确、有效的网站内容导航。 5 第二章搜索融擎l ：作鞭理的分析s 窦现 第二章搜索引擎工作原理分析 2 ，1 搜索引擎的工作原理 ! e l 前网络上有大量的搜索引擎为互联网用户提供服务，它们的功能各有千秋， 所提供的服务也五花八门，一部分搜索引擎拥有庞大的数据库资源和强劲的硬什设 施做厉盾，有的小巧玲珑而个性鲜明，有的搜索引擎从互联网上收集各类信息资料， 有的j j ! i j 获取、加丁其它搜索引擎的反馈结果，既有向所有互联网用户提供信息服务 的通川性搜索引擎，也有瞄准某一个领域的专业搜索引擎，不过它们的基本：j ：作原 理足相同的。 一个搜索引擎有三个不同的部分组成饩2 j ：烂收集数据疗勺网络蜘蛛，一足数 据维护系统，它负责对所得到的资源信息进行整理、分类、检索和更新，三是搜索 引擎的用户查询系统，这三部分各有分工，在搜索引擎中完成不同的工作，它们所 处理的对象、工作的原理有较大的差异，图2 1 是一个搜索引擎的工作原理框图： 图2 1 搜索引擎原理图 图中的三个虚线框所框出的分别是网络蜘蛛、数据维护系统和用户查向系统， 它们之间的关系和分工可以从图中很清晰地看出：网络蜘蛛的功能就是在网络中根 据u r l 地址漫游、收集资源信息并传送回搜索引擎的数据库，数据维护系统的r 作就是对这些取回的数据进行加工处理，完成对数据的分类、索引：l 作。数据的存 6 第二章搜索罗4 t 1 作鼹理韵分析与实现 储、更新工作也是由此部分负责，用户查询系统是对用户提出的查询要求进行分析 向数据库提交，再将检索结果返回给用户。一般用户直接接触的只是用户查询系 统的界面部分，比如输入所要查询的词句，然后按下搜索键，再就等待返回的查询 结果，看上去很简单，实际上为了向用户提供丰富而有效的服务搜索引擎有许多 的j ：作需要完成，下面将详细讨论这三个部分的工作原理。 2 1 1 网络蜘蛛的工作原理 网络蜘蛛又称为网络机器人，它们实质上是一种特殊的客户程序 1 0 , 3 3 , 9 j 。互联 网上的般用户所使用的客户程序就是浏览器，浏览者通过浏览器访问特定u r l i m h l ：的互联网资源，浏览者需要控制浏览器的u r l 定向、链接的跳转而浏览器 负责获取被访问资源并以适当的形式( 文本、图像、音频、视频或文件等) 返同给 浏览者。在浏览过程中，浏览器的访问行为是被动的、用户驱动的，访问模式是交 互的。 网络蜘蛛也是通过u r l 地址定向地访问网络资源，获取相应的数据，它们不 需要人为的控制，它们的访问行为是主动的、访问模式是自主的，它可以分析得到 的资源数据，提取出自己所需要的新的u r l 地址信息( 超级链接) ，这样它根据新 的u r l 地址有访问新的资源。 通过超级链按可以访问到互联网上的所有资源，这样在理论上网络蜘蛛就可以 自动地访问到所有的互联网资源，搜索引擎的数据库可以得到整个互联网的数据。 但实际上互联网的资源数量实在是太多了，而且更新速度快，将整个互联网的数据 都收录入搜索引擎数据库是根本就不可能的。那么如何在有限的资源条件下获得最 好的数据质量昵? 这样就需要一些控制策略来调整、引导网络蜘蛛的搜索行为，譬 如搜索域的划分、搜索深度的控制、数据更新等，图2 2 是一个网络蜘蛛的。r 作原 理例： 圈2 2 网络蜘蛛工作原理图 幽中虚线所框出的是网络蜘蛛部分，从图中可以看出它是由个数据获墩传送 7 第二二章搜索砚擎：【作碾理的分橱与实现 模块和一个镶略控制模块构成，数据获取传送模块负责直接从网络上获取所需要的 联网资源，并传送至搜索引擎的数据库之中，策略控制模块执行前述的各种控i t i 0 策略，具体引导模块获取数据的行为。因为实际应用中网络蜘蛛的搜索过程是多线 差垡并发进行的，所以在这张原理图中标出了多个搜索过程。 2 1 2 数据维护系统 网络蜘蛛将所得到的互联网资源传回搜索引擎的数据库，接1 ；来的工作就由数 据维护系统负责了。 数据维护系统的工作主要分为三个部分：一是对数据库中的信息资源进行分 析、整理归类的数据索引系统，第二部分是数据库的维护工作，包括数据的存储、 访问，第三部分是数据库资源的更新。图2 , 3 是数据维护部分的工作原理图： 图2 3 数据维护工作原理图 从圈中可以看出三个部分之问的关系，其中数据的更新部分实际上由数据更新 控制模块与网络蜘蛛共同完成，它们在数据更新过程中需要交换各种控制信息。 数据维护系统的工作中有很大一部分是基于数据库的操作，前面讲到过互联网 数据与传统数据库所处理的对象有很大的不同，比如数据索引部分，传统数据库的 索引功能是针对某些字段进行的简单排序工作，而搜索引擎的数据索引部分要复杂 得多，它是基于文档内容的提取技术，即文档向量模型 1 4 , 1 1 2 0 , 3 f i j ，在搜索引擎的索 引t 作中，重点是分析出页面内容的意义，然后根据分析的结果将页面整理分类。 由于计算机的分类准确性还有待进一步提高，有一些搜索引擎部分或全部地保留了 人工索引，以求获得较好的分类效果，提高检索准确率，比如象y a h o o ! 。 同传统的数据库系统相比，在数据更新方葡搜索引擎与其也存在较大的差异： 传统数据库的更新一般是局部的，要更新的数据可事先规划，是可预测的行为，而 8 第二章搜索； 擎i 佧踉理拍分瓠与实现 搜索引擎的数据库更新问题就要考虑更多的问题，因为互联网上的数据更新量人、 更新速度快，对数据的实时性要求高，而且更新数量、时阃无法准确预测，再加上 互联网的持续高速发展更加加剧了这种不确定性。采用什么样的更新控制荣略保证 数据的实时有效性和全面性就成了一个关键问题，在这方面有许多启发性和智能的 算法，主要是针对统计规律进行建模。 在大型数据库中，由于数据量庞大。因而在数据传送过程中的缓冲策略是个重 要的课题，而对搜索引擎而言，由于它的数据量是一般数据库无法望其项背的，而 且网络传输的速率、实时性又受到很多条件的制约，数据传送中缓冲策略的好坏从 很大程度上影响到搜索引擎的服务质量。 2 1 3 用户查询系统 川户查询系统是搜索引擎直接同用户接触到的部分。它负责接受用户的查询， 经过分折处理后把查询要求向数据库提交，它把返回的结果显示给用户，由川户进 一步分析，选择需要浏览的内容。对每一条查询结果相对应的提供一个u r l 地址， 用户就可以通过这个u r l 地址定向访问所要的具体内容。图2 4 是用户查询系统 的l 作原理圈： 围2 4 用户查询系统原理图 由图中可以看出；用户查询系统中牵涉到多种技术的综合包括动态网页生成 技术、语义分析技术，数据检索技术等方藏。通过分析用户的查询、访闯行为可以 学习、确定和预测用户的浏览模式，向用户提供有效的浏览导航，帮助用户快速寻 找到所需要的信息。 一般的搜索引全部是由上述三部分组成，但也有一些例外，比如一些集成搜索 引擎，它们自己没有网络蜘蛛和数据维护部分，它们的数据源是其他搜索引擎耵查 询结果，用户可以通过一些参数的设置来控制它们返回结果的数量、排序等形式。 9 第二章搜索b | 擎工作乐理的分析s 实现 象i j 面介绍过的m e t a s e a r c h 、s a w y s e a r c h 等就是这种类型的搜索引擎。 2 2 搜索引擎关键技术分析 前面讲述了搜索引擎的基本工作原理和方法。提到了搜索引擎所运用到的一些 技术和原理，比如互联网资源的数据对象模型| 2 4 , 2 s l 、网页识别技术“。3 6 i 、浏览 导航技术帆2 、缓冲策略、r e i n f o r c e m e n tl e a r n i n g 算法i i o , 3 3 等，这些理论、方法已 经得剑较为深入的研究，它们对搜索引擎的发展起到了极大的推进作用。下面将分 析数据模型、网页识别、浏览导航和r e i n f o r c e m e n tl e a r n i n g 算法等方面的基本理 论，并针对本文研究讨论这些理论和方法的优缺点。 2 2 1 数据对象模型研究 互联网是一个发展速度很快的新生事物，在互联网上的数据资源有自己独特的 属性，和传统的数据形式有较大的不同p w l 。这些新的数据资源向搜索引擎研究提 出了新的课题，只有建立台适的数据对象描述模型才能有效地处理互联网上的数据 资源f 4 ，j 。在传统关系犁数据对象模型基础之上发展起来一些新的数据模型已经得到 较多的研究如c o r d s “、m i n d t ”l 等多库系统采用的数据模型具有一定的可扩 展性，其中c o r d s 采用关系模型，m i n d 则是基于面向对象模型。 王能斌等提出了基于带根连通有向图的对象集成模型及其代数操作，能比较灵 活、有效的描述互联网上异质、异构、半结构化的数据资源并提供了对象并、差、 选择、投影、粘贴和切削等操作方法，从而可以灵活、有效地描述互联网上的数据 资源1 2 4 , 2 1 。 数据模型的正确与否从根本上影响到搜索引擎的工作原理与效果，具有十分重 要的意义。本文研究的蘑点也在建立一个新的数据模型上因而对这方面理论的研 究将硅下一章给予洋尽地阐述。 2 2 2 网页识别技术 如何快速而准确地从洁如烟海的互联网资源中寻找到所需要的信息已经成为困 扰网络用户的一大难题所以具有高智能的互联网信息搜索的技术和工具成为研究 的热门课题。 w e b 网页的识别是智能化搜索引擎的重要组成部分，w e b 网页识别能力的高低 真接影响到搜索引擎的检索效率和准确性i ”。l ，在需要自动领域识别的专业搜索引 擎中更是扮演着举足轻重的角色1 1 q 。 w e b 网页识别技术以h t m l 源文件作为研究对象，通过对某特定类则的网 页样本进行训练。获得该类别网页的特征模式，再以该特征模式为基础，进行机器 学习，使程序能够对w e b 网页识别归类。 1 0 籀二章搜索引擎 一作豫理的分柝与实现 目前w e b 网页识别技术都是基于空间向量模型1 1 4 川，即把目标网页表示成d 维 向纠拌奉特征，然后对每一个样本( 包括训练样本与测试样本) 与特征向量进行艇 配，削断样本中是否含有响应特征分量，具体的实现算法一般采明b a y e s 分类算法， 删负分类的全部过程框架如图2 , 5 所示； 幽2 5 网页分类的l 。f 1 ：原耻削 b a y e s 分类算法是一种概率方法，此算法建立在文档向量摸型的基础之上，在 此 共! “中，个文档中所有的单词在文档出现的概率是相对独立的，每一个单i i j ) j 一个分矢量表示，一个文档可表示成为所有单词分矢量的和。对于不同类文档而言， 每个单词在文档中出现的频率是不一样的，而对于菜一类文档而言，某单词出现的 撅率、频度是基本确定的，这样对某一类文档就对应着某个确定的向量模式w 。 婴判琏斤一个术归类文档的类别，可以通过计算该文档的单词与向量模式w 的胆雕 怙况而判定该文档属于某类别文档的概率。 在中文语境中应用b a y e s 分类算法时还会遇到一些具体的问题，特别是汉语分 词越。在英文语境中词与词之间有天然的分界符空格，而汉语语境中没有形 成明显的分词标志。这样自动分词成了汉语信息处理中的重要环节，它是搜索引擎、 i = 者处理、机器翻译、文摘生成和情报检索的基础工程之一。 hi j i 采_ l i i 的自动分词算法有最大匹配法( m m 法) 、从左至右最大匹配法( m m b 法) 、舣向扫描法等，在构架自动分词系统时有采用分词与评价融台的方法，也义 将分词与评价分离的系统设计思想，后者具有更好的开放性和规范性1 4 9 l 。 b a y e s 分类算法在网页识别中己得到广泛的应用与研究并产生了许多改进的 b a y e s 分类算法。例如对于自然语言的研究表明单词之间并不是完全独立的，这一 点与基本b a y e s 分类算法的假设有所不同，需要对基本的b a y e s 分类算法进行修j l ：， 比如引入对数回归法或最大熵法等可以得到改进的b a y e s 分类算法p 6 l 。 2 23 浏览导航技术 互联网是一个全球性的多媒体、超文本文档信息系统在互联网中，信息的发 布者常常通过超级链接把相关的文档连接在一起，组成一个个面向特定主体的信息 系统。而对这些信息的获取过程可分为线索发现与信息探求阶段。在一个：联网文 档中一般包含有指向多个其它文档的超级链接用户都希望以最小的代价获得最多 第二章搜索昏擎t 作蹶理的分辑s 实现 f | 川信息的浏览踏径，如果浏览路径选择不当不仪导致代价的增加，而且还“t 能使 川户与有_ = | 的信息失之交臂。因此浏览路径的选择是一件十分重要而义容易i l l 错的 - m 2 8 4 “。 个w e b 站点殴计时常常难以准确地预计可能的用户群及其特征，因此预先 垃”的浏览路径也就是站点逻辑结构常常不能与实际情况很好地吻合。所 以为川户提供动态的浏览路径导航和站点结构的优化是十分必要的。 。个典型的浏览导航系统通常由代理a g e n t ，学习a g e n t 、导航a g e n t 和文档管 删讨儿个 i f ；分组成，其中代理a g e n t 负责截取用户的信息请求，经过适当的处理厉 转发给相应的w e b 服务器，而w e b 服务器的回答也要经过代理a g e n t 处理后1 j 转 发给相应的j i = j 户，同时还把用户的活动情况记录下来供其它部件使用；学习a g e n t 从j j ，o 的活动中学习、总结用户的活动规律，产生关于用户的知识；导航a g e n t 根 据当d f 户的活动状况，利用用户知识库中的知识为用户提供适当的引导；文档管 理器! j i 负责管理从服务器取得的文档、用户曰志以及维护知识库。它们之间的关系 如幽2 6 所示： 图2 , 6 浏览导航系统原理图 阍龙凝、阳小华等提出一种基于w e b 用户视圈的浏览导航技术，它是从数据 库中借助了相应的概念来描述用户在互联网上搜寻信息的行为， 视| j f i 是数据库中的一个重要概念，在关系数据库中它是从一个绒几个基本表 ( 或视图) 导出的表，数据库管理员可以为特定的用户或用户群定义个或多个视 l j f 。以限制或引导它们对数据库的访问同时用户也可以定义视幽以把自己的视野 集中在有意义的范围内。从w e b 用户的角度来考察视图，在客户端通过对w e b 刚 户获取信息的过程进行分析，提出了w e b 区域、测览区域、浏览过程等概念以较 好地刻画w e b 用户浏览活动的本质。 第二章搜索引擎f 作雅理的分诉s 实现 个w e b 用户在互联网上的活动就是浏览过程，在一次浏览过程中w e b 朋户 次协阅过的文档的集合d = ( d l ，d 2 ，d n ) 称为一次浏览过程。蹦户住测览 过程中所经过的浏览路径与相关的文档组成了浏览区域，一个浏览区域包含有特定 的信息簇，向用户提供某特定领域的信息。 w e b 州户般会有一些相对稳定的兴趣，所以在不同浏览过程中会表现山相同 或柏似的需求，这样相应的浏览区域也会表现出相同或相似的特性。 相似形是浏览区域集合上的一个关系，它是自反的、对称的。是个相容关系 相似性芙系可以通过考察浏览区域之间的重叠部分得到。通过考察用户的浏监轨迹 分市w 以得到用户对某浏览区域的兴趣强度。 在视图的基础上引入相似性判别规则和兴趣强度度量规则，相似性判别规j l ! | j 可 以削断州户浏览区域的相似性与兴趣分类，兴趣强度度量规则可判断_ i ；f j 户对某浏览 区域的兴趣强度，从而得知用户的兴趣类型并预测其浏览行为，这样就能向州户提 供有效的浏览导航。 在基于用户视图的w e b 浏览导航系统中，准确、实用的相似性判别规划是关 键问题，周龙壤等也提出在这一方面需要进一步的努力。 2 2 4r e i n f o r c e m e n tl e a r n i n g 算法 通朋性搜索引擎( g e n e r a ls e a r c he n g i n e ) 的潜在用户是各种各样、无法准确 预计的，不是针对某一特殊群体的用户它需要为多样化的查询要求给予满意的查 询结果，以获得最好的综合服务质量，所以此类搜索引擎在收集互联网资源是一般 采心j 1 度优先( w i d t h f i r s l ) 的原则，尽量收集尽可能广的信息。 但对某些专业要求比较高的用户而言，通用性搜索引擎无法满足它们的查询需 求，这样专业搜索引擎就应运而生，他们专门收集某一特定领域的互联网资源。目 前己产生了许多的专业搜索引擎，此类搜索引擎的实现方法与通用性搜索引擎有一 定的差异，特别是在搜索策略方面存在较大的差异。专业搜索引擎在搜索过程中采 川的是深度优先的原则，自动识别收集的网页内容是否属于某一特定领域。 这样如何正确地判断网页的类别并最有效地收集互联网资源成为专业搜索引擎 研究的关键目前理论上比较成熟并且得到较好应用效果的有r e i n f o r c e m e n t l e a r n i n g 算法1 l 。 在机器学习领域中，r e i n f o r c e m e n tl e a r n i n g 算法是指基于奖罚机制的优化策略 学习方法，在此学习过程中给定某个体系条件时学习者并不知道执行哪一个动作 足止确的，但对于它选择执行的动作，最终能够得到个评价值q 来表征该次选 择执行后所得结果的好坏程度 在r e i n f o r c e m e n tl e a r n i n g 算法中，系统总是选择执行当前可执行动作中q 值 中最高的一个，而对后续执行动作的总评价值不予考虑。这种选择策略可以用f 1 1 6 l 1 3 第二章搜索；l 擎i 作强理的分析s 实现 说叫： 在r e i n f o r c e m e n tl e a r o i n g 算法中q 取值的合理性是算法有效性得以保障的关 键。q 值一般是从b a y e s 算法得到。 由七述论述可知r e i n f o r c e m e n tl e a r n i n g基于概率统计的学习方法，其中b a y e s 分类算法的准确性是该方法的关键。 1 面所述的b a y e s 分类算法、浏览导航以及r e i n f o r c e m e n tl e a r n i n g 算法已经 响人垡而深入的研究和应用，但本文认为它们都是建立在传统的数据模型基础之 上，术能充分利用互联网资源中的主要语义信息超级链接中所蕴含的、揭示文 档削戈系结构的信息因而无法获得令人满意的结果。 23 搜索引擎的实现方法 前面讨论了搜索引擎的工作原理，对网络蜘蛛、数据库维护和查询系统等三部 分都怍了详细的论述。但在搜索引擎的具体实现中仅仅依靠上述原理是远远不够 的，还必须考虑到在搜索引擎的实际工作中会遇到的问题和必须注意的一些具体技 术问题下面将讨论搜索引擎的实际工作流程及其实现方法。 2 _ 3 1 搜索引擎的实际工作流程 前面已经详细讨论过搜索引擎的工作原理，即通过网络蜘蛛从互联网上收集信 息资源，这些资源经过网页识别、分类处理后存储于搜索引擎的数据库系统之中 而用户的查询由查询系统预处理后在数据库中进行查询，井将所得到的结果返同给 _ i 户。 在上述过程中还有许多实际的问题需要考虑，譬如网络连接的可靠性、对敏 焙区域数据的同避、互联网资源的数据结构、用户搜索策略、网页更新策略等，一 个实际的搜索引擎应充分考虑运行中可能遇到的上述问题，否则是无法实际运行 的。因此必须对搜索引擎的实际工作流程有一个清晰的了解。下面将详细地描述搜 索引擎实现过程中需要考虑的问题。 ( 1 ) 、互联网资源的获取网络蜘蛛部分的实现 ( ) 由于互联网上的数据资源的数量十分庞大。单个的搜索线程只能涉猎 到互联网上极少一部分的资源，因此在实际工作中。搜索引擎必须同时运行多个搜 索线程( 网络蜘蛛) ，在互联网上举行搜索，在访问网站时应读取r o b o t t x t 文件， 该文件说明此髓站不希望w e bs p i d e r 访问的区域，网络蜘蛛都必须遵守这个规定。 网络蜘蛛的实现方法是多种多样的，依据具体的运行、开发系统而存在较人的 差异，在u n i x 和w i n d o w s 中的具体实现是不同的。就是在同一开发环境中也可 1 4 第二章挫隶； 擎i 作自i 理的分析b 实现 以“不同的选择，比如往阻v b 为开发r 具的实现环境中可以使j ；i ja c t i v e xc o n l r o l 米实现，也可以使用i n t e m e ta p i 米实现。 为实现访问互联网资源这一步必须建立描述网站和网页信息的类对象平描述 r o b o tt x t 文件内容的数据表。 ( 1 2 ) 网络蜘蛛根据搜索引擎数据库中网页的信息，去搜索需要更新的网页 或依据超级链接去获取新的网页。 有些网站因为其内容不符合搜索引擎收录的要求，在搜索中这些网页是不需要 去防问的，故而搜索引擎保存有一张屏蔽表，在该表中纪录了这些不需要访问的网 站、网页的信息，如果需要更新的网页或新链接网页在屏蔽表中则不去访问该网页。 射具体的搜索引擎而言，每个搜索引擎所收录的互联网资源是有针对性的，比 如普通搜索引擎只要求收录h i m l 文件而某些图像搜索引擎会收录图像资源以分 析处理。所以搜索引擎需要保存一张纪录了可收录文件类型的袭，如