（计算机科学与技术专业论文）台海领域的人立方关系搜索引擎的研究与实现.pdf

2 j j 。一_ _ i 嬲愀 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 均岔日期1 堡z 堡季珥岔 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适用本授权书。 日期： 日期： 4 一 一 北京邮电大学硕十学位论文 台海领域的人立方关系搜索引擎的研究与实现 摘要 搜索引擎技术可以提供信息检索服务，使得用户在互联网中可以快速，准 确地获取感兴趣的数据。随着时间的发展，传统的全文搜索引擎和垂直搜索引 擎已经不能满足用户的所有需求，一种新的搜索模式必将产生。特定领域的人 立方关系搜索引擎是基于对象级别的垂直搜索引擎，它致力于将w e b 信息抽 取、社会网络分析等技术和传统的检索技术相结合，为用户提供强大的检索和 社会网络分析可视化能力。 本文以台海领域的新闻网页作为研究数据，针对搜索引擎、信息抽取的研 究热点及其相关技术进行了深入的分析和研究，取得了如下研究成果： 关系搜索引擎的网络爬虫。本文研究了网络爬虫的爬行算法、主题采集 策略和遍历优先策略，提出了基于配置文件的定制爬行方法，实现了台 海领域主题的新闻网页爬虫。 关系搜索引擎的网页解析和主题过滤。在网页解析方面，本文提出了一 种结合h t m l p a r s e r 技术，基于特征的网页解析方法；在主题过滤方面， 本文采取了传统的文本分类方法。， 关系搜索引擎信息抽取。本文实现了命名实体识别和实体关系提取。命 名实体识别采取了基于最大熵模型的面向特定领域的实体识别方法，实 体关系抽取则采用的是基于向量空间的实体关系提取方法。 关系搜索引擎社会网络的分析和展示。人立方关系搜索引擎力图在互联 网的台海领域中记录人的社会活动信息，并揭示人与人之间关系的动态 结构图景。本文提供了几种社会网络的分析方法，并支持可视化功能。 最后，在对上述问题的研究和应用的基础上，本文构建了一个台海领域的 人立方关系搜索引擎系统，并对系统进行了功能可用性验证。 关键词：关系搜索引擎网络爬虫网页解析信息抽取社会网络分析 面向台海关系的人立方系统的研究j 实现 j j l i 北京邮电人学颂l 学位论文 t h er e s e a r c ha n di m p l e m e n t a t i o no fc u 旧i c r e l a t i o n s h i ps e a r c he n g d 厄i nt a i 恰nf i e l d a b s t r a c t s e a r c he n g i n et e c h n o l o g yc a l lp r o v i d ei n f o r m a t i o nr e t r i e v a ls e r v i c e s ，a n d e n a b l eu s e r sg e tt h e i n t e r e s t e dd a t af a s to i lt h ei n t e r n e t a st h et i m eb y , t h e t r a d i t i o n a lf u l l - t e x ts e a r c he n g i n e sa n dv e r t i c a ls e a r c he n g i n e sc a nn ol o n g e rm e e ta l l t h en e e d so fu s e r s ，a n dan e ws e a r c hp a t t e r ni sb o u n dt op r o d u c e c u b i cr e l a t i o n s h i p s e a r c he n g i n ei nt a i w a nf i e l di sav e r t i c a ls e a r c he n g i n eb a s e do no b j e c t - l e v e l i t c o m b i n e sw e bi n f o r m a t i o ne x t r a c t i o n , s o c i a ln e t w o r ka n a l y s i sa n dt h et r a d i t i o n a l s e a r c ht e c h n o l o g yt op r o v i d eu s e r sw i t hm a n yp o w e r f u lc a p a b i l i t i e s ，s u c ha ss e a r c h , s o c i a ln e t w o r ka n a l y s i sa n dv i s u a l i z a t i o n i nt h i sp a p e r , b a s e do nt h ed a t ao fc h i n e s en e w si nt a i w a nf i e l d ，w eh a v e s t u d i e ds 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 na n do t h e rr e l a t e dt e c h n o l o g i e s ，a n d a c h i e v e dt h ef o l l o w i n gr e s u l t s ： c o m p l e m e n t e dar e l a t i o n s h i ps e a r c he n g i n ew e bc r a w l e r t h i sp a p e rh a s s t u d i e dc r a w l i n ga l g o r i t h m s ，p a g et h e m ec o l l e c t i o na n dp a g et r a v e r s a l s t r a t e g yi nw e bc r a w l e r i tp r o p o s e dap a g ec r a w l i n gm e t h o db a s e do nt h e c u s t o mc o n f i g u r a t i o nf i l e s c o m p l e m e n t e dap a g ep a r s e ra n dp a g et h e m ef i l t e ri nr e l a t i o n s h i ps e a r c h e n g i n e p a r s i n gt h ew e bp a g e ，t h i sp a p e rp r o p o s e dam e t h o r db a s e do n f e a t u r e sc o m b i n i n gh t m l p a r s e rt e c h n o l o g y i nt h ep a g et h e m ef i l t e r i n g , t h i sp a p e rd o p t e dat r a d i t i o n a lt e x tc l a s s i f i c a t i o nm e t h o d c o m p l e m e n t e dw e bi n f o r m a t i o ne x t r a c t i o ni nr e l a t i o n s h i ps e a r c he n g i n e w e bi n f o r m a t i o ne x t r a c t i o ni n c l u d e sn a m e de n t i t yr e c o g n i t i o na n de n t i t y r e l a t i o n s h i pe x t r a c t i o n i nt h i sp a p e r , n a m e de n t i t yr e c o g n i t i o ni sb a s e do n m a x i m u me n t r o p ym o d e lc o m b i n i n gs p e c i a lf i e l dr u l e s ，a n de n t i t y r e l a t i o n s h i pe x t r a c t i o ni sac l a s s i f i c a t i o nm e t h o db a s e do nt h ev e c t o rs p a c e m o d e l c o m p l e m e n t e dt h ea n a l y s i sa n dv i s u a l i z a t i o nf u n c t i o n t h er e l a t i o n s h i p s e a r c he n g i n ei st r y i n gt or e c o r dt h ep e o p l e ss o c i a la c t i v i t i e sa c r o s st h e t a i w a nf i e l di nt h ei n t e r n e t i tr e v e a l e dt h ed y n a m i cs t r u c t u r eo ft h es o c i a l n e t w o r k t h i sp a p e rp r o v i d e ss e v e r a ls o c i a ln e t w o r ka n a l y s i sm e t h o d s ，a n d 北京邮电大学硕一l ：学位论文 s u p p o r t sn e t w o r kv i s u a l i z a t i o n e x c e p tt h ew o r ki n t r o d u c e da b o v e ，t h i sp a p e rh a si m p l e m e n t e dt h es y s t e mo f c u b i cr e l a t i o n s h i ps e a r c he n g i n ei nt a i w a nf i e l d a tl a s t ，t h i sp a p e rv a l i d a t e dt h e f u n c t i o na n da p p l i c a t i o no fs y s t e mw i t hs o m ec a s e s k e yw o r d s ：r e l a t i o n s h i ps e a r c he n g i n ew e bc r a w l e rw e bp a g e p a r s i n g i n f o r m a t i o ne x t r a c t i o ns o c i a ln e t w o r ka n a l y s i s j i 北京邮电人学硕十学位论文 目录 第一章绪论l 1 1 选题背景及意义1 1 2 国内外研究现状2 1 3 本文主要工作3 1 4 本文结构4 第二章相关技术综述5 2 1搜索引擎技术综述。5 2 1 1搜索引擎原理5 2 1 2 全文搜索引擎7 2 1 3垂直搜索引擎7 2 1 4 特定领域的人立方关系搜索引擎8 2 2w 曲信息抽取技术综述9 2 - 2 1 w e b 信息抽取概述一9 2 2 2w e b 信息抽取的发展历史与研究现状1 0 2 2 3w e b 信息抽取的关键技术1 1 第三章关系搜索引擎的研究内容1 4 3 1网络爬虫1 4 3 1 1工作原理1 4 3 1 2 搜索策略1 4 3 1 3 主题采集策略- 15 3 1 4 具体解决方案1 6 3 2网页解析18 3 2 1 相关方法18 3 2 2h t m l p a r s e r 技术1 9 3 2 3 时间提取2 l 3 2 4 正文提取2 2 北京邮电人学硕1 ：学位论文 3 3 网页主题过滤2 6 3 3 1 文本分类概述2 6 3 3 2 特征提取2 7 3 3 3特征向量表示2 8 3 3 4 分类方法2 8 3 4 中文命名实体识别31 3 4 1 相关方法3 2 3 4 2 最大熵模型3 2 3 4 3 特征选择3 3 3 4 4 具体解决方案3 5 3 5 实体关系抽取3 8 3 5 1问题提出。3 8 3 5 2 相关方法4 0 3 5 3 基于特征向量的关系抽取4 l 3 6 索引搜索模型4 5 3 6 1 总体模型4 6 3 6 2l u c e n e 技术4 6 3 6 3 网页搜索策略4 9 3 6 4 关系搜索策略5 0 第四章台海领域的人立方关系搜索引擎的设计与实现5 2 4 1系统功能5 2 4 2 总体架构5 3 4 2 1 系统架构概述5 3 4 2 2 具体工作过程5 5 4 2 3 数据描述与定义5 6 4 3 系统实现5 8 4 3 1 开发运行环境5 8 4 3 2 实现技术5 9 4 3 3 系统运行状况5 9 i 北京邮电大学硕j ：学位论文 4 4 应用和分析6 3 4 4 1数据准备6 3 4 4 2 具体分析6 4 4 4 3 总结与评价6 9 第五章总结与展望7 0 5 1论文总结7 0 5 2 论文展望7 0 参考文献7 2 致谢7 5 攻读学位期间发表的学术论文目录7 6 北京邮电人学硕1 二学位论文 北京邮l 乜大学硕i ：学位论文 第一章绪论 1 1 选题背景及意义 随着网络与通信技术的迅速发展，w e b 信息爆炸性地增长，互联网已经成为 一个巨大的海量信息空间。如何快速、准确、方便的从如此庞大的信息库中获取 自己需要的信息，是互联网用户面临的一个重要问题。搜索引擎技术的出现恰好 解决了这一难题，它可以为用户提供信息检索服务。用户希望通过信息检索迅速 快捷地找到自己所需要的信息，而这时传统的全文搜索引擎的弊端就逐渐显露出 来，比如搜索引擎的覆盖范围有限，有时只能检索出总网页数的5 0 ；返回结果 多而繁杂，其中包含了许多无关或者相关性很小的信息，用户要找到自己的信息 仍很困难等。因此，全文搜索引擎已不能完全满足人们的需求，面向领域的垂直 搜索引擎的研究随之产生。垂直搜索引擎针对某一特定领域、某一特定人群或某 一特定需求提供有价值的信息和相关服务。其特点就是“专、精、深”，相比较 全文搜索引擎的海量信息无序化，垂直搜索引擎则显得更加专注、具体和深入。 垂直搜索引擎具有广阔的市场应用前景和研究价值，形形色色的垂直搜索引 擎也应运而生。例如，有面向房子的搜房网，面向求职的职业搜索，面向学术的 学术搜索等，这些搜索引擎都有三个共同特点：1 ) 抓取的数据来源于垂直搜索 引擎关注的行业站点，并倾向于结构化数据和元数据；2 ) 搜索行为是基于结构 化数据和元数据的结构化搜索；3 ) 搜索结果往往是搜索对象的相关结构化信息 和网页信息集合。垂直搜索引擎能够提供一些常规的信息，但当用户检索后，往 往对其它一些信息感兴趣，比如检索对象和其它相关对象的关系；领域内的社会 网络或者关系网络的发展和演变等等。为解决这一问题，一种新的搜索模式产生， 即特定领域的人立方关系搜索引擎。首先什么是人立方关系搜索? 它是由微软亚 洲研究院的网络搜索与挖掘小组研发的基于对象级别的互联网搜索引擎。它是一 款新型社会化搜索引擎，能够从超过十亿的中文网页中自动的抽取出人名、地名、 机构名以及中文短语等，根据搜索关键词和与其相关的人名之间的关联度强弱自 动的计算每一个人名与关键词的直接距离、数据大小以及具体的摆放位置等等， 并通过一条标明了人际关系的细线连接他们并使其发生社会化关系【i 】。这种信息 聚合方式为关注某些人物和挖掘人物社会关系发挥了重要作用。其次为何是特定 领域? 因为微软人立方虽然提出了一种新的搜索引擎概念，但是它仍然存在缺 陷：一是海量的w e b 数据使得系统难以一一获取资源，二是w e b 数据的多样性 和分散性导致分析能力松散、实体重名等问题出现。特定领域的人立方关系搜索 北京邮电人学硕i ：学位论文 引擎使数据量大大缩小，相对集中，更有利于专注这一领域内感兴趣的对象以及 对象之间的关系。 特定领域的人立方关系搜索引擎是基于对象级别的垂直搜索引擎，致力于将 w e b 信息抽取、社会网络分析等技术和传统的检索技术相结合，为用户提供强大 的检索和网络信息可视化功能。信息抽取作为一门正走向成熟的技术，在信息处 理自动化中具有基础性的地位，将它融合到关系搜索引擎中，能够有效和快速地 从无组织和非结构化的互联网数据中提取出结构化信息。在w 曲信息抽取领域 中，命名实体即为对象，是指现实世界中具体的或抽象的实体，如人物、机构、 地点等，是文本中基本的信息元素；关系被看作两个实体在一段时间或空间范围 内的某种联系，是研究实体之间语义关系的一项重要基础性研究。对象和关系构 成一系列社会网络，分析这些网络的组成和演变将成为人立方关系搜索引擎的根 本。什么是社会网络? 社会网络是指实体( 例如人、机构) 和实体之间的关系所 组成网络结构，这些关系通常可以包括朋友、合作、亲戚等等。社会网络分析不 仅包括统计和网络分析，还包括可视化分析，其重点在于分析这些实体之间的关 系模式【2 j 。随着互联网的不断发展，社会网络分析已成为w 曲挖掘领域研究开发 的焦点。 鉴于特定领域的人立方关系搜索引擎产生的重大意义，本文作者将深入垂直 检索，信息抽取，社会网络分析等技术，针对台海领域实现人立方关系搜索引擎。 这里所指的台海领域是指围绕台海两岸关系，台湾政治、经济发展等展开的新闻 网页信息集合。台海领域的人立方关系搜索引擎则是特定领域的人立方关系搜索 引擎的一个应用实例。为何要选择台海领域呢? 主要因为：1 ) 领域内的数据更 加统一，容易定义出对象类型和关系模式；2 ) 台海领域是公众关注的热点；3 ) 挖掘社会网络有利于了解台海领域的人物关系，研究台海领域的局势和发展。本 文以下的章节都将围绕着台海领域的人立方关系搜索引擎展开。 1 2 国内外研究现状 搜索引擎按其工作方式主要可分为四种，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、垂直搜索引擎( v e r t i c a ls e a r c h e n g i n e ) 、目录式搜索引擎 ( d i r e c t o r ys e a r c he n g i n e ) 和元搜索引擎( m e t as e a r c he n g i n e ) 【3 1 。下面将主要 介绍全文搜索引擎、垂直搜索引擎和关系搜索引擎的研究现状。 全文搜索引擎是目前最为普遍的应用，国外具代表性的全文搜索引擎有 g o o g l e 、y a h o o 、a l l t h e w e b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著 名的有百度( b a i d u ) 、中搜等。它们都是通过从互联网上提取各个网站的信息( 以 网页文字为主) 去建立数据库，检索与用户查询条件匹配的相关记录，然后按一 定的排列顺序将结果返回给用户。其优点是：信息量大、更新及时、毋需人工干 2 北京邮电人学硕士学位论文 预；而缺点是：返回信息过多，往往夹杂着冗余的信息，检准率低，用户还必须 从结果中进行筛选。 垂直搜索引擎是一种主题型搜索引擎。其优点是：对某一领域来说信息搜集 全面、更新及时、针对性强、检准率高；缺点是：结构复杂、技术要求高。国内 外具有代表性的垂直搜索引擎主要有以下几个：1 ) e l s e v i e r 的s c i r u s 系统，它只 面向包含有科学内容的网站，是一种专为搜索高度相关的科学信息而设计的搜索 引擎：2 ) l i b r a 学术搜索，它是一个免费的计算机论文搜索引擎，用来更加智能 地获取在计算机科学领域内的各种关于论文、科学家、会议、期刊和学术兴趣圈 的信息；3 ) w i n d o w s l i v e 产品搜索，以企业所经营的产品为查询主线，搜索结 果为专业加工过的数据，信息内容规范：4 ) 还有查询地图的m a p b l a s t 、查询信 息产业的赛迪i t 罗盘、查询证券信息的和讯搜索、查询旅游信息的中华万游网、 查询音乐信息的m p 3 搜索通等等。 上面列举的系统都是一些垂直搜索应用实例，虽然有很多优点，但是它们没 有融入对象的社会关系网络分析和展示。如今，已有很多垂直搜索引擎将重点放 在了以人物为中心的关系搜索上，比如较早的雅虎人物搜索，它对w e b 中的人 物信息进行了分类，并提供人物检索功能和以人物为中心的社会关系网络展示功 能：腾讯搜搜的搜索华尔兹也是一种基于互联网海量信息下的以人物为中心的信 息聚合垂直搜索；微软的人立方，它不仅提供了关系搜索功能，而且关系挖掘深 度令人满足，结合了s i l v e r l i g h t 的绚丽界面也令人心旷神怡。除此之外，还有一 些文献检索也引入了科研合作网的分析和展示，比如万方医学网，它不仅提供了 作者检索，而且还能展示此作者几跳内的科研合作网络。 不过这些关系搜索引擎还存在很多需要完善的地方，比如解决实体重名问 题；提高关系挖掘的深度和精度；打破社会网络分析的局限性，让用户挖掘出更 有用的信息等等。 1 3 本文主要工作 本文实现的台海领域的人立方关系搜索引擎不仅是一个垂直搜索引擎，而且 还涉及到信息抽取、社会网络分析和可视化技术的方方面面。本文作者在经过大 量收集和阅读相关文献后，主要做了以下几个方面的工作： 关系搜索引擎网页抓取和网页解析的研究。本文介绍了此搜索引擎采取 的爬行算法、主题采集策略和遍历优先策略，并提出了一种结合 h t m l p a r s e r 技术，基于特征的网页信息解析方法( 包括题目和正文解析) 。 关系搜索引擎信息抽取的研究。这里的信息化抽取是指命名实体识别和 实体关系提取。本文首先介绍了基于最大熵模型的面向特殊领域的实体 识别方法，在实体识别的基础上又提出了基于机特征向量的实体关系提 3 北京邮电大学硕i ：学位论文 取方法。 关系搜索引擎索引和检索机制的研究。在实现了网页信息抽取后，这些 结构化信息需要组建成适合关系搜索的索引检索模型。本文主要研究如 何利用l u c e n e 和数据库技术去实现关系搜索引擎的索引检索模型。 关系搜索引擎社会网络分析和展示的研究。入立方关系搜索引擎力图在 互联网的台海领域中记录人的社会活动信息，并揭示人与人之间关系的 动态结构图景。本文提供了几种社会网络分析方法，并支持网络的可视 化功能。 台海领域的人立方关系搜索引擎的设计与实现。在对上述问题的研究和 应用的基础上尝试构建一个台海领域的人立方关系搜索引擎系统。 1 4 本文结构 本文按以下章节组织： 第一章，绪论，首先说明了课题的研究背景和意义，接着对搜索引擎技术的 现状进行了分析，最后介绍了作者的主要工作和论文结构。 第二章，相关技术综述，本章将重点介绍搜索引擎、w e b 信息抽取的概念、 原理和方法等内容。 第三章，关系搜索引擎的研究内容，详细介绍关系搜索引擎各个关键部分的 原理、发展现状和本文采取的方法。这些技术分别包括网页抓取和解析、网页信 息抽取以及关系检索的索引搜索模型等。 第四章，台海领域的人立方关系搜索引擎的设计与实现，本章首先描述了系 统的总体框架和各个模块的主要功能，然后详细介绍了框架中核心模块的设计与 实现，最后给出了一个应用，以验证此系统。 第五章，总结与展望，主要针对全文做出总结，并提出需要改进和继续研究 的方面。 4 2 1 有相 和垂 擎的 2 1 1 尽管当前对于各种搜索引擎的分类不同，但从原理上看，搜索引擎主要是指 那些使用网页爬行软件，按照一定的策略将w e b 文档采集到本地数据库，然后 对这些网页进行自动分析并建立索引数据库，进而对用户提出的检索请求在数据 库中进行搜索，找出匹配的文档或者链接返回给用户的网络软件。 搜索引擎一般由信息采集器、数据索引器、查询搜索器和结果排序器四个部 分组成。 信息采集器 信息采集器( 网络爬虫或者网络蜘蛛) 的功能是在五联网中漫游，发现和采 集信息。它常常是一个计算机程序，日夜不停地运行。它要尽可能多、尽可能快 地采集各种类型的新信息，同时因为互联网上的信息更新很快，所以还要定期更 新己经采集过的旧信息，以避免死链接和无效链接。目前有两种采集信息的策略： 1 ) 从一个起始u r l 集合开始，顺着这些u r l 中的超链接，以宽度优先、深度 优先或启发式方式循环地在互联网中发现信息。这些起始u r l 可以是任意u r l ， 但常常是一些非常流行、包含很多链接的站点；2 ) 将w e b 空间按照域名、口地 址或国家域名划分，每个采集器负责一个子空间的穷尽搜索。采集器采集的信息 类型多种多样，包括h t m l 、x m l 、f t p 文件、字处理文档、多媒体信息等【钠。 采集器的实现常常用分布式并行计算技术，以提高信息发现和更新的速度。商业 搜索引擎的信息发现可以达到每天几百万网页。 数据索引器 索引器的功能是理解采集器所采集的信息，从中抽取出索引项，用于表示文 档以及生成文档库的索引表。索引项分为客观索引项和内容索引项：客观索引项 与文档的语意内容无关，如作者名、u r l 、更新时间、编码、长度、链接流行度 等等；内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。 内容索引项可以分为单索引项和多索引项( 短语索引项) 两种。单索引项对于英 5 北京邮电人学硕+ ：学位论文 文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符( 空格) ；对 于中文等连续书写的语言，就必须进行词语的切分。在搜索引擎中，一般要给单 索引项赋予一个权值，以表示该索引项对文档的区分度，同时用来计算查询结果 的相关度。使用的方法一般有统计法、信息论法和概率法。短语索引项的提取方 法有统计法、概率法和语言学法。索引器的生成是索引表，它一般使用某种形式 的倒排表，即由索引项查找相应的文档。索引表也需要记录索引项在文档中出现 的位置和频率，以便排序器计算索引项之间的相邻或接近关系。索引器可以使用 集中式索引算法或分布式索引算法。当数据量很大时，必须实现实时索引，否则 不能够跟上信息量急剧增加的速度。索引算法对索引器的性能有很大的影响。 查询搜索器 检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询 的相关度评价，并实现某种反馈机制。用户在查询中，可以按照搜索引擎的查询 语法制定待检索词条和各种简单、高级检索条件。简单查询只解析查询串，而复 杂查询可以对查询条件进行限制，如逻辑运算( 与、或、非) 、相近关系、出现 位置( 如标题、正文) 、时间信息、长度信息等等。 结果排序器 结果排序器主要对搜索器返回的匹配网页集合进行相关度排序。排序是指根 据索引库中网页得到的词频率( t f ) ，反转文档频率( i d f ) 以及p a g e r a n k p j l 6 j 值，融合用户反馈信息；网页更新时间等因素，对网页进行评分。 搜索引擎的具体工作流程如图2 1 所示，它包括网页信息的发现和收集；对 信息进行提取建立索引库；对用户检索请求在索引库中搜索排序，然后把检索结 果返回给用户等主要过程。 图2 - 1 搜索引擎的工作流程 1 从互联网上抓取网页 需要有高性能的网络爬虫去自动地在互联网中搜索信息。一个典型的网络爬 6 北京邮电大学硕士学位论文 虫的工作方式，是查看一个页面，并从中找到相关信息，然后它再从该页面的所 有链接出发，继续寻找相关的信息，以此类推，直至穷尽。在算法上各个搜索引 擎技术公司可能不尽相同，但目的都是快速浏览w e b 网页和后续过程相配合。 2 建立索引数据库 由索引器对收集回来的网页进行分析，提取相关网页信息，然后用这些信息 建立网页索引数据库。 3 在索引数据库中搜索排序 当用户输入关键词搜索后，由查询搜索器从网页索引数据库中找到符合该关 键词的所有相关网页。 4 返回检索结果 最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起 来返回给用户。 2 1 2 全文搜索引擎 全文搜索引擎符合上面介绍的搜索引擎原理，它最为关键的部分就是全文检 索。全文检索是指计算机索引程序通过扫描文章中的每一个词，对每一个词建立 一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根 据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程 类似于通过字典中的检索字表查字的过程。 全文检索的方法主要分为按字检索和按词检索两种。按字检索是指对于文章 中的每一个字都建立索引，检索时将词分解为字的组合。对于各种不同的语言而 言，字有不同的含义，比如英文中字与词实际上是合一的，而中文中字与词有很 大分别。按词检索指对文章中的词，即语义单位建立索引，检索时按词检索，并 且可以处理同义项等。英文等西方文字由于按照空白切分词，因此实现上与按字 处理类似，添加同义处理也很容易。中文则需要切分字词，以达到按词索引的目 的，关于这方面的问题，是当前全文检索技术尤其是中文全文检索技术中的难点。 在普通搜索引擎的结构上，全文搜索引擎增加了文本分析器。文本分析器包 括英文分析器、中文分析器和其它语言的分析器。目前，英文分析器处理的效果 比较好，而中文分析器也在逐步发展。中文分析器涉及到很多自然语言处理的知 识，比如中文分词、词性识别和语义识别等。一个较好的分析器能大大提高检索 的性能。 2 1 3 垂直搜索引擎 垂直搜索引擎是一种主题型搜索引擎，它对信息的需求往往是针对受限领域 和面向特定主题的。目前，垂直搜索引擎技术有基于内容分析的搜索引擎技术和 7 北京邮电人学硕f ：学位论文 基于链接分析的搜索引擎技术。基于内容分析的搜索引擎在内部建立了一个针对 主题的词表，网络爬虫会根据词表对网上的信息进行索引。各个不同的系统词表 建设的复杂度也大不相同。现在这种词表的建设越来越多的引入了知识表示的方 法。基于链接分析的搜索引擎则是模拟社会网络模型，一些学者认为网页之间的 链接指引关系同社会网络中的关系有相似之处，特别的与传统的引文索引非常相 似。通过对链接进行分析，可以找出各个网页之间的引用关系，由于引用网页与 被引用网页间内容上一般都比较相关，所以就可以很容易地按照引用关系将大量 网页分类，从而找到感兴趣的网页。 不难看出，垂直搜索引擎技术的实质就是主题爬虫技术【7 】。主题爬虫是主题 搜索引擎的基础与核心，主题相关度的分析是主题爬虫的关键。主题爬虫在普通 爬虫基础上进行功能扩充，在对网页的整个处理过程中需要增加模块：主题确立 模块、初始种子模块和主题相关度分析模块。主题确立模块用于确立爬虫面向的 主题；主题相关度分析模块用来进行网页主题相关度的计算，决定页面的取舍； 主题相关度排序模块是对页面的最终处理，对主题相关页面的价值进行评价；初 始种子模块用于生成面向特定主题的较好的种子站点，使爬行模块能够顺利展开 爬行工作。 图2 - 2 主题爬虫系统构成 如上图2 2 所示的主题爬虫系统，( 1 ) 至( 5 ) 是数据流的处理过程。( 1 ) 爬虫模块取回网页；( 2 ) 调用主题相关度分析模块，对网页进行相关度分析；( 3 ) 爬行模块根据分析的不同结果进行相应的处理；( 4 ) 爬行模块从数据库取出等待 处理的u r l 继续工作，循环到第一步，直至没有新的u r l ；( 5 ) 利用主题相关 度排序模块对网页的重要程度进行排序。可以看出，初始种子模块和主题确立模 块只是两个辅助模块，不参与数据流的处理。 2 1 4 特定领域的人立方关 本文提到的特定领域的 北京邮电大学硕上学位论文 信息采集器、数据索引器、查询搜索器和结果排序器等组成；它与全文检索引擎 相似，也需要文本分析器；它与垂直搜索引擎相似，也需要垂直搜索主题爬虫。 不同的地方是：1 ) 特定领域的人立方搜索引擎还需要对非结构化数据进行信息 抽取，包括命名实体识别和实体关系提取；2 ) 针对用户，加入了社会网络的分 析和可视化展示；3 ) 提供对象级别的搜索。其具体流程如下： 网络爬虫从大量的中文新闻网站中抓取和特定领域密切相关的网页集 合，送入到原始页面存储库中。同时，网络爬虫控制中心负责控制爬虫 抓取网页上u r l 对应的网页，反复循环直到把所有的网页抓取完成。 网络爬虫抓取的网页是原始的h t m l ，需要进行处理。使用网页解析技 术从h t m l 中提取标题、正文和u r l ，把它们分别放入有效网页信息库 中，然后，网页过滤利用文本分类或者数据挖掘方法把与特定领域无关 的网页信息集合放入无效网页信息库中，有关的继续放在有效网页信息 库中。 对有效网页信息库中的标题和正文进行信息抽取。首先利用命名实体识 别算法自动抽取出人名、地名、机构名等实体，然后提取出实体之间的 关系，并挖掘出具体的关系描述词。 集成上面的这些对象和关系数据，建立组织成符合对象级别的关系搜索 模型。这个关系搜索模型包含三个部分：1 ) 建立索引库，它由倒排表组 成，负责对象的网页检索；2 ) 建立对象库，它主要存储对象的属性信息； 3 ) 建立关系库，它主要负责对象的关系搜索。 在索引库和关系库的基础上，进行搜索。一方面，从索引库和对象库中 找到与对象相关的网页信息和对象属性信息；另一方面，从关系库中找 出此对象的社会网络。 当用户检索时，对网页信息进行排序，并展示对象的社会网络。当结果 展示以后，系统还提供社会网络的挖掘功能。 2 2w e b 信息抽取技术综述 2 2 1w e b 信息抽取概述 随着计算机的普及与互联网的高速发展，信息也呈爆炸式地增长。信息的过 量增长带来一定负面影响，面对巨量的信息，难以发现真正需要的信息。如何将 大量无序的信息及时、准确地进行提取、整理、组织和便于查询检索的形式，已 成为研究开发的焦点。信息抽取正是在这种背景下产生、发展起来的。 信息抽取( i e ， i n f o r m a t i o ne x t r a c t i o n ) 是指直接从自然语言文本中抽取事 实信息，并以结构化的形式描述信息，供信息查询、文本深层挖掘、自动回答问 9 北京邮电人学硕l ：学位论文 题等使用，为人们提供有力的信息获取工具。信息抽取作为自然语言处理中一个 发展很快的研究领域，有以下特点：1 ) 信息抽取是当前文本挖掘中最为突出的 一项技术，这一技术结合了自然语言处理、语料资源以及语义技术，目前正趋于 成熟；2 ) 信息抽取不是从文本集中选取一个与用户需求相关的子集，而是直接 抽取与用户需求相关的事实或信息；3 ) 信息抽取是一个从无结构的自由文本或 其他信息资源中抽取出结构化，无二义性信息的过程。 目前，w e b 已经发展成为一个全球的、巨大的、分布的、和共享的信息空间， 而这些信息同样需要提取和整理，所以，信息抽取技术对那些把互联网当成知识 来源的人来说是至关重要的。因此为了从w e b 网页中抽取所需要的信息内容， 研究人员开始把目光转向w e b 信息的机器抽取工作。w e b 信息抽取处理的对象 是w e b 网页，即从w e b 页面所包含的无结构或半结构的信息中识别用户感兴趣的 数据，并将其转化为结构和语义更为清晰的格式( x m l 、关系数据库、面向对 象的数据等) 。 2 2 2w e b 信息抽取的发展历史与研究现状 w e b 信息抽取( w i e ，w 曲i n f o r m a t i o ne x t r a c t i o n ) 的前身是文本理解，最 早开始于2 0 世纪6 0 年代中期，主要是从自然语言文本中获取结构化信息的研究， 这被看作是信息抽取技术的初始研究。这里有两个自然语言处理的项目，一是美 国纽约大学的l i n g u i s t i cs t r i n g 项目i s 】，其主要研究内容是建立一套规模较大的英 语计算语法，用于从医疗领域的x 光报告和出院记录中抽取信息格式 ( i n f o r m a t i o nf o r m a t s ) ；二是耶鲁大学r o g e rs c h a n k 研究小组根据故事脚本理论 建立的信息抽取系统f r u m p 9 1 。该系统主要用于从新闻报道中抽取信息。 从2 0 世纪8 0 年代末开始，信息抽取研究蓬勃开展起来，这主要有两个因素 对其发展有重要的影响：一是在线和离线文本数量的几何级增加，另一个是“消 息理解研讨会”( m u c ， m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ) 从1 9 8 7 年开始 到1 9 9 8 年共举行了七届会议，一直推动着该领域的发展。m u c 由美国国防高级 研究计划委员会( d a r p a ，t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 资 助，其显著特点并不是会议本身，而在于对信息抽取系统的评测。m u c 1 没有 明确的任务定义，也没有制定评测标准；m u c 2 开始有了明确的任务定义，规 定了模板以及槽( s l o t s ) 的填充规则，抽取任务被明确为一个模板填充的过程； m u c 3 到m u c 5 引入了召回率、准确率和平均填充错误率作为评价标准； m u c 6 又引入了三个新的评测任务：命名实体州e ， n a m e de m i 哆) 识别、共指 ( c o ，c o n f e r e n c e ) 关系确定、模板元素( t e ，t e m p l a t ee l e m e n t ) 填充掣m 】【l l 】。最 后的m u c - 7 又增加了一项新任