（计算机应用技术专业论文）搜索引擎中的信息抽取技术研究.pdf

檀索引擎中的信息拙取技术研究 摘要 y 3 9 8 5 2 1 ，随着信息技术的高速发展，凶特网卜信息爆炸性地增长，因此如何能够快 速和精确地在这种海量信息中检索到用户所需信息已成为重要的研究课题。搜索 引擎是目前在w e b 中查找信息的土要技术，原理卜，搜索引擎技术主要涉及w e b 搜索技术、文挡分类技术和信息抽取技术，本文着重研究搜索引擎中的信息抽取 技术。文中首先就搜索引擎技术做了概要介绍，分析了搜索0 i 擎的交现原理，在 此基础上着重对传统向量空间模型的信息抽取算法进行了分析，指出j ，其存在的 缺点，针对特定领域搜索引擎，提出了种新的基于n 层向量空间模型的信息抽 取算法，比较于传统向量空间模型，该算法在查全率、查准率、查技效率和计算 复杂发等方面，具有较好的性能。基于n 层向量空间模型的信息抽取算法，本文 实现j ，一个中文计算机文献搜索引擎。 关键词：特定领域搜索引擎，信息抽取，向量空间模型，查全率，查准率 搜索弓l 擎中的信息撤取技术研究 a b s t r a c t a st h ei n t e r n e tc e n t i n a o u st og r o wi np o p u l a r i t ya n ds iz e 。t h ea m o u n t 0 fi n f o r m a t i o n0 i 2t h ew o r l dw i d ew e b si n c r e a s i n ge x p l o s jv e ly s oi t b e c o m e st h em o s t i m p o r t a n tr e s e a r c ht o p i e t or o t j e v et h ei n f o r m a t i o r l r a p i d l ya n da c c u r a t e l y n o w ，s e a r c he n g i n e sh a v eb e c o m et h em a i l 2t e c h n 0 1 0 9 y f o rr e t r i e y i n gi n f o r m a t i o nf r o mw e b t y p i c a l l y ，s e a r c he n g i n e sc o n s i s to f w e ba g e n t i n f o r m a t i o ne x t r a c t i o na n dr e x tc i a s s if i c a t i o nt e c h n j q u e s t h i s p a p e rm a i n l yd i s c u s s e st h et e c h n 0 1 0 9 yo fi n f o r m a t i o ne x t r a c t i o n f i r s t l y ， t h ep r i n c i p l eo fs e a r c he n g i n e sisi n t r o d u c e da n dt h ed e s i g n i n gt e c h n o l o g y i s a n a l y z e d ，t h e n ，t h e v c c t o r s p a c em o d e l ，a t r a d i t i o n a i n f o r m a t i o n e x t r a c t i o nm o d e l ，i sa n a l y z e dd e t a i l ，a n ds o m eo fi t sd e f e c t sa r ep o i n t e d o l i t b a s e do nt h ea r i a l y s is a nn - t e v e iv e c t o rs p a c ea ! g o t i t h mi sp r o p o s e d f o r t h ed o m a i n s p e c i f i es e a r c he n g i n e s c o m p a r e dw i t ht h et r a d i t i o n a l v i c t o rs p a c ea l g o r i t h m t h en e wa l g o r i t h mh a sb e t t e rp e r f o r m a n c ei nf e c a l1 ， p r e c i s i o na n dc o m p e x it yo ft h ea 】g o r i t h m b a s e do nt h en e wn l o v e tv e c t o t k e y w o r d s ：d o m a i n s p o c i f i cs e a r c he n g i n e ，i n f o r m a t i o ne x t r a c t i o n ，v e c t o r s p a c em o d e ! ，r e c a j1 ，p r e c i s i o n 搜索 1 擎中的信息抽取技术研究 第一章引言 1 1 搜索引擎概述 随着i n t e r n e t 的飞速发展，网络已经成为人们生活、工作的重要部分。为了 使人们能够在浩如烟海的海量信息中寻找到有用的信息昵，国外比较成功的搜索 引擎有i n f o s e e k 、y a h o o 、a t t a v i s t a 等等；而在国内，搜狐与新浪也是比较成功 的门户网站。现大多数的搜索引擎的主要任务是实现信息的有序利用和快速定位， 为此其应以信息检索功能为主体，同时为增强其性能，搜索引擎还应有其他几项 必备功能，例如：主页、站点索引、个人知识库、自然信息库、信息桥等等。搜 索引擎除提供用户方便的使用界面和多种检索方法外，更重要是能否实现一个高 效合理的信息索引机制，以最少量的存储、最快的速度，表达最复杂的信息逻辑 关系，并具有良好的可扩充性和与其他相关系统的接口。搜索引擎的相关功能也 4 i 应各自独立，应彼此联系形成一个有机的统一体。信息本身是多样化的，但通 过搜索引擎提供给用户的索引接口应是一致的。这样将有利于搜索索引机制的统 一，有益于数据的公享，有利于整个信息网信息的高效利用，有利于建设一个具 有相当规模和较强市场竞争力的信息网络。 1 2 搜索引擎中的三个主要问题 对于用户来说，若想要检索到自己所需要的内容，已经变得越来越困难。一 般的搜索引擎如a l t a v i s t a 和g o o g t e 只注重于查全率，而忽略了查准率，对于细 节查询，其效果就可想而知了。假如，用户已经知道所需要检索信息的信息类型 或主题时，这时，一般的搜索引擎就不是最佳的检索方式了。特定领域搜索引擎 就成为了最佳解决方案。搜索引擎技术主要涉及三个方面，即自动w e b 搜索技术， 文挡分类技术和信息抽取技术。目前国内外都在致力研究与之相关的技术以解决 w e b 上的海量信息搜索，分类及信息抽取。1 。传统的搜索引擎主要采用广度优先 算法建立w e b 蜘蛛( s p i d e r ) 实现w e b 的搜索，导致搜索的信息杂乱无章，且效 率很低。针对门户引擎的特点，目前一些研究人员提出利用具有机器学习功能的 搜索引擎中的信息抽取技术研究 算法，建立搜索模型，以提高搜索精度和效率，代表性的方法包括基于概率进化 算法的巩固学习( r e i n f o r c e m e n tl e a r n i n g ) 。1 ，w e b 代理”! 。对于文档分类目 前的研究主要分为三类，一类是基于标准的r o c c h i 0 “】分类算法的t f i d f 方法”。， 其基本思想是利用加权“词向量”( w o r dv e c t o t ) 的概念表示一个词在文档类中 的重要性：另一类方法则是基于概率和信息论理论的分类器，如b a y e s 算法”1 ， 最大熵算法”1 等；第三类是基于符号学习的方法，如决策树”“。利用机器学习 方法进行信息抽取近年来得到普遍关注“1 ，传统的信息抽取技术是基于普通文本， 如m u c “1 ，而搜索引擎的信息对象主要是超文本，目前研究的方法包含隐含马尔 科夫模型。”。，关系识别1 “，基于知识的w e b 信息抽取“等。特定领域搜索引擎， 往往集中某一方面的内容，为特殊领域信息的查询提供有效的方法。 - - - - c a m p s e a r c h ( w w w c a m p s e r c h c o m ) ，允许用户查询有关于夏令营方面的信 息。用户可以通过夏令营地理位置、价格、日期等方式来查询和搜索有关于 夏令营方面的信息。 - - - - l i n u x s t a r t ( w w w 1 f n u x s t a r t c o m ) ，为l i n u x 用户提供一个有关于l i n u x 的技 术与资源的交流场所，并在主页上提供一个有关于l i n u x 网页的主题层次和 搜索引擎。 - m o v f er e v i e w q u e r ye n g i n e ( w w w m r q e c o m ) ，为电影爱好者提供一个有关 于电影信息交流场所，并在主页上提供一个有关于电影网页的主题层次和搜 索引擎。 一一c r a f t ss e a r c h ( _ w w w b e l l a - d e c o r c o m ) ，为工艺品爱好者提供一个有关于工艺 品的技术与资源的交流场所，并在主页上提供个有关于工艺品网页的主题 层次和搜索引擎。 一一t r a v e l f i n d e r ( _ w w w t r a v e l - f i n d e r c o r n ) ，为旅游爱好者提供一个有关于旅游 信息的交流场所，并在主页上提供一个有关于旅游信息网页的主题层次和搜 索引擎。 若想用一个传统的、一般的搜索引擎来完成上述任务，其查找的效率与准确率 是很低的。对于上述问题，我们怎样解决呢? 在本论文中，将针对这个问题进行 研赍， 搜索引擎中的信皂0 由取技术研究 1 3 信息抽取技术的研究概况 s p i d e r 或r o b o t 在网络上爬行，获取人数据文档，那如何处理呢? 又如何 使这些文档来为搜索引擎服务呢? 这项任务就得由信息抽取来完成。信息抽取就 是从文档中抽取一些概要信息来形成描述整个资源的文档，这些概要信息包括 u r l 、标题、关键词、描述、文件长度、文件中各种超链接数等。 传统的信息抽取技术是基于普通文本，如m u c “”1 ，而搜索引擎的信息对象主 要是超文本，抽取关系类型的数据 2 1 l 、关系识别“，需要对搜索的信息类型进 行很强的假设。如抽取页面结构关系的信息l j ”，从数据库的观点看，w w w 上的 大量资源包含结构化的信息，对于w e b 页面的结构信息抽取的方法也有很多种， 如采用启发式方法 1 9 1 ，按照各个部分字体的大小和缩进的距离来推导出页面上的 层次结构，该方法对于没有标出字体大小和缩进距离的部分是无法抽取；采用用 户输入页面描述文件 2 0 l 对层次结构进行抽取，该描述文件需要用户描述抽取过程 的具体变量和编写抽取方法；采用从w e b 文档中构造半结构化信息抽取器hz j 就 是将一组链接的h t m l 页面转化为嵌套的数据对象，抽取器将所需数据的网页地 址和该数据抽取格式的描述作为输入。近年，利用机器学习方法进行信息抽取已 得到普遍关注，所谓机器学习方法是通过以初始的训练集为基础，通过机器的 自学习来不断的扩大训练集和提高信息抽取的准确率的方法，如p a l k a “和 a u t o s l o g ”】就是通过语法分析进行自学习的信息抽取系统，而c r y s t a l 。：1 和 p a p i e r 。”是通过应用学习规则来完成自动抽取任务的，搜索引擎c o r a 中就采用 隐含马尔科夫模型“”来自学习。其它的抽取技术是基于知识的w e b 信息抽取。“1 ， 如i 。i a ：3 9 ：和w e b f o o t ：就是应用这种方法来学习的系统。 向量空间模型是由s a t t o n 等人在六十年代末到七十年代初期提出并发展起来 的”。这一模型将给定的文本( 文章、查询、或文章的一段等) 转换成一个维数 很高的向量。它的最大特点是可以方便地计算出两个向量的近似度，及向量所对 应的文本相似性。所有文献用向量表示，也就是将搜索到的文档材料进行特征项 抽取，形成特征向量，而用户查询时，则针对特定的查询向量，比较它与所有文 献的相似度，并依相似度大小将文献排序提交给用户。 搜索引擎中的信息抽取技术研究 1 4 本文所做工作 本文着重于特定领域搜索引擎信息抽取技术的分析与研究，现将主要工作归 结如下： 1 对于搜索引擎所涉及的w e b 搜索技术、文档分类技术、信息抽取技术 等三个重要技术问题做了讨论与研究。 2 深入地探讨了搜索引擎中的信息抽取技术，特别是对传统的向量空间模 型信息抽取算法做了系统的分析与研究，并指出该算法不适应于动态文 档变化的缺陷。 3 通过改进向量空间模型，提出了基于n 层向量空间模型的信息抽取算 法，既保持了传统向量空间模型实现特征信息抽取以及在查询过程中的 相似度计算方便性，又使得这种方法能够应用于动态文档集合中。 4 试验证明：比较传统向量空间模型的信息抽取算法，该算法在查准率、 查全率和查找效率等方面，具有较好性能。 5 基于n 层向量模型和信息抽取算法，本文实现了一个中文计算机文献搜 索引擎。 全文主要包含五个章节：第一章引言部分，包括搜索引擎的概况，搜索引擎研 究中的三个主要问题，信息抽取技术研究概况，本文所做的工作；第二章主要介 绍了搜索引擎的基本原理，包括搜索引擎的主要任务及组成，互联网信源分析及 有关协议，搜索信息资源的获取及原理，信息标引及分类；第三章中着重介绍了 特殊领域搜索引擎中信息抽取的重要性，以及研究现状，在基于传统的向量空间 模型信息抽取算法分析的基础上，提出一种基于n 层向量空间模型的特定领域搜 索引擎的信息抽取算法，并用实验证明相对于传统向量模型的信息抽取算法，在 查准率、查全率、查找速度和计算复杂度等方面，该算法的性能更优；第四章基 于n 层向量空间模型信息抽取算法，实现了一个中文计算机文献搜索引擎；第五 章是结语，主要是针对全文做出总结，并提出需要改进和继续研究的方面。 搜索引擎中的信息抽取技术研究 第二章搜索引擎的基本原理 本章中主要介绍了搜索引擎的基本原理，对于搜索引擎所涉及的w e b 搜索技 术、文档分类技术、信息抽取技术等三个重要技术问题做了讨论与研究。包括搜 索引擎的主要任务及组成，互联网信源分析及有关协议，搜索信息资源的获取及 原理，信息标引及分类。 2 1 搜索引擎的主要任务及组成 2 1 1 搜索引擎的主要任务 搜索引擎的主要任务是实现信息的有序利用和快速定位，为此其应以信息检 索功能为主体，同时为增强其性能，搜索引擎还应有其他几项必备功能，例如： 主页、站点索引、个人知识库、自然信息库、信息桥等等。搜索引擎除提供用户 疗便的使用界面和多种检索方法外，更重要是能否实现一个高效合理的信息索引 机制，以最少量的存储、最快的速度，表达最复杂的信息逻辑关系，并具有良好 的可扩充性和与其他相关系统的接口。搜索引擎的相关功能也不应各自独立，应 彼此联系形成一个有机的统一体。 图2 - - i搜索引擎在骨干网中的位置 搜索引擎中的信皂、抽取技术研究 2 1 2 搜索引擎在骨干网中的的位置 搜索引擎和本地w w w 挂接到同网段或不同网段的局域网上，共同通过路由 器连接到骨干网上，如上图2 1 所示： 2 1 3 搜索引擎的功能组成 一个完善的信息搜索引擎必须具备的功能有： 信息获取：遵循互联网协议，自动识别网络信源，获取网页内容。 信源注册：个人主页注册、信源站点注册等。 信息标引：主要是对获取到的网络信源进行加工处理，形成可供高速查 询的索引信息集。 信息管理、分类：对生成的索引信息集进行增删改等操作，并将信息条 目进行类别归档。 系统数据维护：维护系统的各种数据词典、工作日志以及数据的备份等。 信息有效性检查：根据索引信息集和外部网络环境，检查数据的有效性。 数据动态跟踪、统计调整功能：系统根据时间、用户访问次数等动态因 素进行跟踪统计，形成热点、新料等数据。 其他功能：例如广告功能等。 明 系统功能结构如图2 - 2 所示：图中所用到的一些图示，都给出了其对应的说 方框代表功能单元 数据接口 ： 操作 ： 圆柱体代表数据库 口 口 口 曰 一 堡至! 】望! 塑笪：垦垫塾垫查堡塞 图2 - 2搜索引擎系统功能结构图 7 搜索引擎中的信息抽取技术研究 2 2 互联网信源分析及有关协议 i n t e r n e t 通过复杂的网络设备互相连接起来，形成遍布全球的物理网络。网 络上的应用及信息资源更是丰富多彩、干变万化。无论是实现原理、表现形式还 是遵循的网络协议都在随着网络技术的发展而发展。 2 2 1 互联网信源数据类型 互联网信息资源数据类型可分为7 大类( 详见下表2 1 ) 表2 1 互联网信息资源数据类型 1名称解释 l 文本( t e x t )用于表达由字符组成的纯文本信息和按标准格式 化的文本描述语言。 i 多部分数据体将可能为不同数据类型的数据组装成一条信息。 l ( m u l t j p a r t ) i 应用( a p p li c a t i o n )用于传输应用程序或二进制、十六进制数据，完 成电子文件的传输服务。 消息( m e s s a g e )用于封装另外一条电子邮件信息。 l 图片( i m a g e )仅用于传送图片数据。 l 声音( a u d i o )用于传输音频或声音数据。 i 影象( v i d e o )用于传输图象、动画，也可包括声音数据。 而每一种数据类型都包括多种子类。例如图片还有g i f 、j p e g 等。但对于信 息搜索引擎，对“应用”这种数据类型是不做处理的。而消息、图片、声音、影 象，现在有关的处理技术正在逐渐形成，也有一些试探性的应用范例，例如基于 图象的检索系统。但都不够完善，或者说尚未达到实用化阶段。目前国内外的信 息搜索处理的数据类型主要是文本。为进一步分析，现将文本数据类型包含的子 类罗列如下表2 2 ： 搜索引擎中的信皂舳取技术研究 表2 2 文本数据类型 纯文本，未经格式化，默认字符集为u s a s c i i 。 纯文本 p l a i n 无需软件解释。 r i c h t e x t纯文本扩充形式，在r f c l 3 4 i 中定义。 扩展文本h t m l超文本标记语言。 s g m l标准化标记语言。h t m l 是s g m l 的应用程序。 2 2 2 互联网信源数据组织方式 互联网络的信源组织方式颇象w i n d o w s 标准的h e l p 文档，但比h e l p 文档 丰富得多。每篇网页都或多或少地加入很多超级链接。如果将网络信源比做信息 的海洋，那么每一个超链便是海洋中抛下的“锚”，提起任何一只锚都可以去邀游 一片新的海域，在新的海域中又有无数的锚。因而，互联网上信息的海洋是浩瀚 无边的。在网页中超链主要有以下几种： i 标记加上h r e f 连接参数。 2 标记。 3 标记。 4 标记加上s r c 连接参数。 5 标记。 6 标记加上m e t h o d = g e t 连接参数。 信息页面上的链接一般会通过不同的u r l 连接到不同的网页而有些则是通 过“# ”符连接到同网页的不同章节或段落。 2 2 3 互联网协议 i n t e r n e t 是一个开放的网络，网络协议多种多样，从物理网络层到网络应用 层数不胜数。但仅就网络地址u r l 中用到的协议而言，主要有以下几种： “c i d ：”，“c l s i d ：”，“f i l e ：”，“f i n g e r ：”，“f t p ：”，“g o p h e r ：”，“h d t ：”，h t t p ：”， h t t p s ：”，“i t u ：”，i o n ”，“i r c ：”，“j a v a ：”，“j a v a s c r i p t ：”，“l i f n ：”，“m a i l t o ：”， “m i d ：”，“n e w s ：”，“n n t p ：”，p a t h ：”，“p r o s p e r o ：”，“r t o g i n ：”，“s e r v i c e ：”， 搜索引擎中的信息抽取技术研究 “s h t t p ：”，“s n e w s ：”，“s t a n f ：”“t e l n e t ：”。t n 3 2 7 0 ：”“w a i s ：”“w h o i s + + ” 等。 其中常用协议如下表2 - 3 ： 表2 - 3 常用协议 协议解释 f t p文件传输协议 h t t p超文本传输协议 g o p h e r分散文档查询访问协议 m a i t t o电子邮件地址 n e w s新闻组 n n t p利用n n t p 访问新闻组 t e n e t w a l s广域信息服务 f i l e 指定本地文件名 p r o s p e r o 目录服务 对信息搜索有价值的，或者说可以取得文本信息的协议有f t p 、h t t p 、n e w s 、 n n t p 、r i t e ，而f t p 协议经常传输较大的二进制或大文本文档。 2 3 搜索信息资源的获取及原理 2 3 1 信源加载的基本原理 以上对网络信源种类和信源组织方式进行了分析。得知诸多种类的信源中可 用于搜索的主要为文本信息，对他们可以进行直接读取，或通过内置简单的扩展 文本识别器的方式进行读取。网页链接将不同地域、不同类别的信源组织起来， 构成相互间的联系。正因为存在这种联系，才使得信息的自动获取成为可能，并 发展成为一门专门的技术，有人称之为r o b o t 或s p i d e r 技术。它以一个或多个 u r l 为起点，根据网页的组织方式顺藤摸瓜，识别信源种类、链接标记、网络协 议，进行信息资源获取。 搜索引单中的信息抽取技术研究 2 3 2 信息加载在系统中的位置和作用 由于w w w 网的规模飞速扩大，要求搜索引擎中网络资源信息的数量也应相 应增加。如果仍然采用传统的手工加载信息的方式，将大大影响信息库扩充的速 度，并给管理员带来极大的负担。因此，我们开始研制了一些应用程序在网络上 自动搜索信息并加载到数据库中去。由于w w w 网络的最大特点在于各个网页由 大量超链接相互联系，组成一个巨大的图，只要沿着这些超链接走下去，几乎可 以遍历所有网页。利用这个特点，我们的信息自动加载应用系统按一定的规则沿 着超链接在网络上漫游，并收集资源信息。这样的应用就被称为s p i d e r 或r o b o t 。 l y c o s ，e x c i t e ，a | t av i s t a 等著名的搜索引擎都已应用了这种加载机制。 ! 爿丽i i ；l 。 搜索其他功能 图2 3 信息加载在系统中的位置 信息搜索的基础是网络信息资源 重要内容，是系统获得用于原始资料 所处的位置如上图2 - - 3 所示： 2 3 3 信息加载应用规范 所以搜索信息资源的获取是系统初始化的 而后进行加工处理关键环节，它在系统中 搜索引擎信息加载软件( 有人称其为机器人、旅行者、网络蜘蛛等) 是随信 息网络的出现和发展而逐渐走向成熟的，到目前为止在网上公布已有一百多种。 它们有各自不同的产生背景，在不同的领域、不同的应用中发挥着重要作用。有 关信息加载软件的技术标准、实现方案、对网络的影响等等问题，都是网络管理 人员和技术人员经常讨论的热门话题，并各执几见，分歧多多。但综观多家信息 加载软件实现方案，并对不同的见解进行分析，去异取同，总结出信息加载软件 应用姚范如下： 搜索引擎中的信息抽取技术研究 信源的取得方式：都是通过网络协议和对信息服务器频繁的信息访问，获得 全部或部分文本、图片、声音等。都或多或少造成网络带宽的占用和对信息服务 器负担的加重。 运行控制：信启抽取的工作方式、运行规则应该是灵活多变的，一般的做法 是提供参数控制功能，参数选项主要有： 启始地址列表：指向信源站点或具体u r l 。 搜索周期或工作定时机制：信息定期到网上搜索的时间间隔或是工作闹 钟功能。 搜索深度：抓取信息的逻辑层数。 超时上限：是指网络连接、网络读写时间的上限值。 网络访问权限限制：是指网络信源加密处理例如b a s i cc o o k i e 或m d 5 等 p r o x y 设置：通过设置p r o x y 地址、端口、用户、口令等，利用网络代理 访问信息源。 日志功能：记录加载设置、工作日志等。 数据类型过滤：可以通过设置，选择获取什么类型的文件比如h t m 【、t x t 或图片。 站点选择过滤：可以通过设置，选择获取或过滤哪些站点的数据信息。 非公开网页列表：希望服务器上的某些文件被r o b o t 访问，则你需要在 w w w 服务器的根目录下放置一个名为n o r o b o t t x t 的文件，其中列出了 不希望r o b o t 访问的文件清单。 2 3 4 信息加载原理和重要技术 信息的加载是建立搜索引擎的第一步，即通过网络s p i d e r 或者网络r o b o t 在 网络上爬行来获取信息。大多数搜索引擎，如a t a v i s t a 、g o o g l e 和l y c o s 都是用广泛的爬行来获得较高的覆盖率。这是由于一般的搜索引擎的目标是 提供搜索这个w e b 的能力，故这搜索引擎就致力于尽可能多的寻找不同的w e b 网页，所以一般搜索引擎都采取广度优先的策略。而对于特殊领域的搜索引擎， 搜索引擎中的信息抽取技术研究 则要求它的s p i d e r 能够避开那些与主题无关的链接，将注意力集中在那些与主题 相关文档的链接，现在常采取的方法是效率优先的巩固学习方法( r e i n f o r c e m e n t l e a r n i n g ) ，【1 6 】【1 7 】。 1 加载方式 1 广度优先策略 信息加载的每一次搜索都从外部指定的一条u r l 开始，这条u r l 被称作“种 子”。我们将网络复杂的图结构简化为一个具有冗余节点的树结构。例如，图2 4 为4 个节点组成的图，若以1 为“种子”，则树结构为图2 5 所示，若以2 为“种子”，则树结构为图2 6 ，依此类推。 3 图2 4 四个节点图 1 234 砀心 134124123 图2 5 以1 为种子的示意图结构 2 ，7 4 砀n 234124 123 图2 6 以2 为种子的示意图结构 在进行了上述简化后，我们就可以采用遍历树的方法来遍历网络了。由于我们希 望r o b o t 每回抓取的站点都集中在“种子”周围，因此我们选用了宽度优先算法， 这样离“种子”越近的u r l 越先被获取。我们采用了链表结构来记录需要获取的 u r l ，具体步骤是： 1 、将“种子”的u r l 加入链表。 2 ，、读取链表中第一个u r l ，抓取相应h t m l 文件，进行分析，提取概要信 搜索0 l 擎中的信息抽耿技术研宄 息，并在h t m l 文件中找出指向其它h t m l 文件的超链接，若不与链表 中任一元素重复，则将此u r l 加入链表尾部。 3 ，、判断程序是否结束，若没结束，则返回( 2 ) 。 我们通过指定抓取的最大节点数来设置结束条r l ：或不限接点数而让r o b o t 自 动遍历终止。 2 、效率优先的巩固学习策略( r e i n f o t c el e a r n i n g ) 有效的网络爬行是令人关注的。对于特殊领域的搜索引擎来说，因为已经圈 定了搜索的主题范围，此时广度搜索已是次要的了，而主要的是搜索效率。巩固 学习是同通过对反馈的信息进行奖惩来学习的。其最大特点是：学习者并未被告 知何谓正确行为，而仅仅被告诉其所选择的行为是好或者坏，好或坏的程度以分 等级的奖惩来表示【1 6 】。 若设状态的集合为s ，对于任何一种状态s ，满足条件s s ；行为的集合为a ， 对于任何种行为a ，满足条件a a ；函数t ：s + a s 是状态一行为转换函数， 该函数可以将一种状态经过一种行为而映射到另一种结果状态；函数r ：s 张一听 是奖励函数，该函数将对于一种状态经历过一种行为后给予分级的奖励。则在每 一个时间段内，学习者( 或称为代理) 选择种行为，将会获得一个奖励和转换 到一种新的状态。 巩固学习策略的目的就是学习一种策略，即学习一个从状态映射到行为的策 略n ：s a ，使得学习者在学习的全部时间内获得奖励值的和最大；通过极限方 式来近似的得到奖励值之和是最常用的方法。通常的方法如下：设0 4 7 与c t i t l e 之间的文字得到。 2 ) 指向本机h t m l 文件的链接数( 1 0 c a l l i n k ) 与指向远程的h t m l 文件的链 接数( r e m o t el i n k ) 分析文件时，提取四种类型的超链接： c a 旦b 旺二： c a 一 堡窒! ! 兰! 塑堡垒塑壁塾查塑壅 弋竺乏也 q 卜_、一 l建立连接 rl _ i 山山 队； 虹山 l 发送“t t 9 请求 错 1 ， 是 处 v 弹 接收h t t p 头 山下 判断时间、长度、lfu r l 分 + 。hi 析器j 厂：! ：1 = 7 厂一 接收一丌r 文档体 小 l 羚是fif 蓠 j ，广一新州一 日志 i 一 库 对文档体分析处理 夕 山 一、 图2 - 9 信息获取过程分析图 搜索引擎中的信息抽取技术研究 f r a m es r c = ”n a m e = ” 从u r l 中提取出主机信息，判断是本机还是远程主机，然后增加相应计数。 3 ) 描述( d e s c h b e ) 若m e t a 信息中有c o n t e n t 一项，则将其中内容作为描述，否则，从标签 开始，从除去所有h t m l 标签之外的文字信息中截取前2 0 0 个字符作为描述信息。 4 ) 关键词( k e y s ) 若m e t a 信息中有k e y s 一项，则将此项信息作为关键词，否则，找到标题和 特殊字体的文字作为关键词。特殊字体的文字按字体的大小确定优先级，这些特 殊字体的h t m l 标签包括： h 1 ， 文献数目大、体积增长快，而且文本的长度变化范围较大，从几k b 到几百 k b 不等，因此要求索引空间的大小必须限制在合理范围内 2 新概念和专指性概念的出现频率和检索频率高 3 要求较高的查询速度，能在较短的相应时间内计算出检索结果 4 利用停用词表将文本切分为多个切分段，再利用中文分词词表对各个切分 段进行词切分，对切分出的字词，根据如下规则进行标引： 5 若为英文词或者中文分词词表中的词，进行关键词标引，记录权重信息整 个文章处理完毕后，保留关键词标引中权重最大的前3 0 个词作为最终的关键词存 入关键词索引 2 权重计算 衡量关键词的权重一般考虑以下因素： 词频权重：即词在整个文章中的重复出现次数，一般来说，词频越大，词与 主题的相关程度越大，词的权值越大。 位置权重：词出现位置在整个文章中的重要程度。出现在h t m l 文档的标题、 描述、超链接等部分的词般具有较大权重；正文部分中出现在前言、结束语等 重要段落的词的权重也高于其余部分的权重 系统采用的权重计算公式为：f _ k ，坼+ k 2 p j 其中，i 为第 个词的词频权重，p ，为其位置权重，k ，和k 2 为常数，分别为词 频和位置的加权系数，且满足k f + k 2 = 1 。，f 的计算方法为： 假设文章中共抽出m 个词，其出现次数分别为 ，局，f m ，则有： ： 曼 m a x ( f i , f2 ，f 对于p f ，分两种情况考虑： 搜索引擎中的信息抽取技术研究 词出现在特殊标记段中。特殊标记段即带特殊h t m l 标记的段，包括文档标 题 、子标题 、n a i v eb a y e s 框架 我们将框架建立于多项式n a i v eb a y e s 文本分类上【2 3 】。考虑用n a v i eb a y e s 方法，来估计文本文档的一个概率生成模型的参数是非常有用的。在这个模型中， 首先，文档中的类已经选定；然后，在以一个类特殊多项式的参数为基础，产生 文档的单词。因此，分类器的参数由以下部分组成：类的前概率和单词的类条件 概率。每一个类j ，相对于所有其它的分类，都有一个文档概率，表示为p ( c j ) 。 对于词汇表中的每一个单词w t ，p ( w t i c ，) 来表示：分类器所预期的单词w t 在所有 文档的c 类中出现的概率。 在标准的测试环境中，往往是通过使用一组已经标记的文档集d 来获取参数 的。为了估计单词概率p ( w t l c i ) ，本文中用单词w t 数量作为分子，并将文档集中 所有的c j 分类所出现的单词总数作为分母来计算。当然本文中也用到了拉普拉斯 式来补充这个多项式。先预先将分子加一，目的是防止零概率出现。假如：设 n ( w t i c j ) 表示单词w t 在文档d i 中出现的次数，p ( c j id i ) f o ，1 ) ，若文档的类标已经 给定：则w t 在分类c 1 中的概率的估计值表示如下表达式2 1 ： p ( m 怙而l 甚+ , d 五, ：o n x ( w t , d 而, ) * p 丽( c j i d o n 所有类的前概率参数值的设定方式相同，若c ；代表所有分类的数目， d 】代表文 搜索引擎中的信息抽取技术研究 档的数目，则如表达式2 - 2 ： ( c j 紫 ( 2 2 1 假设给定一个文档和一个分类器，在判断该文档属于分类c j 的概率时，使用 贝叶斯规则( b a y e s ) 和n a i v eb a y e s 假设给定类的一个文档中各个单词都 独立出现。设文档d i 中第k 个单词是w d ，k ，则分类表示如表达式2 - 3 ： 啪 户( c ，id f ) zp ( c ) + p ( d ji c ，) zp ( c j ) + 丌p ( 缸。i c ，) ( 2 3 ) k = l 一般来说，当给定的训练文档许多时，n a i v eb a y e s 将很好地胜任对文本文档 的分类【2 ”。对于文本分类如何使用n a v i eb a y e s 在文献【2 4 】和文献 7 】有详细的描 述。 2 5 小结 在本章中，论文对搜索引擎作了概要的介绍，全章共分五节。首先第一节介绍 了搜索引擎的主要任务及组成，对于搜索引擎的全貌以及要达到的功能作了简要 介绍；其次第二节介绍了互联网信源分析及有关协议，着重于对于互联网信息资 源的分析，为搜索引擎的信息获取做准备；再次第三节介绍了搜索信息资源的获 取及原理，重点介绍了信息的获取以及信息的抽取；再次第四节介绍了信息标引 及分类，重点介绍了如何对已经获取到的信息资源进行标引和分类；最后第五节 对全章做出了小结。 搜索引擎中的信息抽取技术研究 第三章搜索引擎的信息抽取算法研究 本章深入地探讨了搜索引擎中的信息抽取技术，特别是对传统的向量空间模 型信息抽取算法做了系统的分析与研究，并指出该算法不适应于动态文档变化的 缺陷。通过改进向量空间模型，提出了基于n 层向量空问模型的信息抽取算法， 既保持了传统向量空问模型实现特征信息抽取以及在查询过程中的相似度计算方 便性，又使得这种方法能够应用于动态文档集合中。试验证明：比较于传统向量 空间模型的信息抽取算法，该算法在查准率、查全率和查找效率等方面，具有较 好性能。 3 1 引言 随着w w w 在全球范围内的不断普及和应用，、 n n f 上的信息资源种类及其 数量不断扩大，因此，研究高效的信息抽取方法成了一个非常重要的课题。近年 来，不少科研工作者致力于这方面的研究，文献 2 8 】结合h t m l 标志的特点，根据 w e b 页面显示格式，将文档中各个部分抽取出来，得到相关数据信息，但由于 w e b 页面显示格式变化多端，同时许多网页设计的不规范( 但人们同样接受) ， 使得文档相关信息的获取可能会产生错误的结果；文献 3 2 j 利用x m l 标记语言从 w e b 页面中抽取出相关的知识，但是由于不同的用户定义相同知识内容所使用的 x m l 标记可能各不一样，使得这种w e b 信息抽取的方法受到很大的局限：文献u j 是一种基于概念的相关信息获取方法，这种方法要求提供反馈信息，才能使得查 询结果满足用户的要求，其实质是以用户的时间开销作为代价获取较高的查准率。 基于向量空间模型的信息检索方法【”1 、【”l ，这种方法通过向量空间模型将文档转 化为向量形式，使得文档之间匹配的计算转化为向量的简单计算，但是由于文档 的向量维数大小与文档集合中的所有检索字的数目相关，检索字数目越大，向量 维数也越大，因此这种方法比较适应于静态检索字集合的文档查询，而对于动态 检索字集合的文档查询则受到限制。 本章中在传统向量空间模型基础上，提出一种基于n 层向量空间模型，理论 分析和实验结果表明，利用该摸型实现的信息抽取方法，具有较快的查找速度以 及较高的查准率。 搜索引擎中的信息抽取技术研究 3 2 基于传统向量空间模型的信息抽取算法研究 3 2 1 传统的向量空间模型算法的基本概念 向量空间模型是由s a l t o n 等人在六十年代末到七十年代初期提出并发展起来 的“。这一模型将给定的文本( 文章、查询、或文章的一段等) 转换成一个维数 很高的向量。它的最大特点是可以方便地计算出两个向量的近似度，既向量所对 应的文本相似性。所有文献用向量表示，也就是将搜索到的文档材料进行特征项 抽取，形成特征向量，而用户查询时，则针对特定的查询向量，比较它与所有文 献的相似度，并依相似度大小将文献排序提交给用户。 向量空间模型使用以下的一些知识： 文献d ( d o c u m e n t ) ：泛指各种机器可读的记录，通常指一篇文章。 特征项t ( t e r m ) ：也称为索引项，是指出现在文档d 中且能够代表该文 档性质的基本语言单位，主要由词或短语来构成，这些基本语言单位统称 为项，于是文献和查询均可用项构成向量来表示d = ( t 1 ，t 2 ，t n ) 。 特征项权值w s k ( t e r mw e i g h t ) ：对于有n 个不同的项的系统，文献d = ( t l ， t 2 ，t 。) ，项t k ( 1 k n ) 常常被赋予一个数值w i k 表示它在文献中 的重要程度，称为项t k 的权重。因此，我们一般用d = ( w i l ，w 。2 ，w i 。) 的形式表示文献。也就是指特征项t k 代表文档d f 的能力大小。的计算 采用特征项频率魄和反比文献频率f 啦计算【z 8 】： = 娠+ ，嘶= 嘛+ ( 1 0 9 2 i n ) + 1 ) ( 3 - 1 ) t f + i d f ：t f ( t e r m f r e q u e n c y ) 指某个特征项t 在文档d 中出现的次数，显 然，t f 越大，则特征项t 越能够代表文档d ，t 的权值应当与之成正比。d f ( d o c u m e n tf r e q u e n c y ) 指整个文档集合中，包含特征项t 的文档个数，直观上 看，d f 越大，既包含特征项t 的文档越多，则特征项t 越代表文档d 的能力越小， t 的权值应当与之成反比；所以人们就提出了i d f ( i n v e r s ed o c u m e n t 搜索引擎中的信息抽取技术研宄 f r e q u e n c y ) ，既然d f 与t 的权值成反比，那么i d f 应当与t 的权值成正比，通常 i d f = 0 8 ( n d f ) ，其中，n 代表文档集合中的文档个数。t f + i d f 能够有效地表达 特征项t 在文档d 中的重要性。 在公式3 1 中，