（信号与信息处理专业论文）半格式化网页信息提取与应用.pdf

摘要 摘要 随着互联网的迅速发展，快速准确获取信息成为制约各行业发展的瓶颈。 互联网作为全球最大的信息资源宝库，受到了越来越来多地重视，通用搜索引 擎应运而生。然而，通用搜索由于“信息过载问题，会给用户带来大量无用 信息，垂直搜索成为新的研究热点。 与通用搜索不同，垂直搜索引擎仅仅专注于某一领域。其对于网页信息的初 步提取，一方面使搜索精度提高；另一方面使浏览者不用逐页阅读网页，提高 了效率。本论文的主要内容是关于垂直搜索构建的相关技术，并重点探讨了英 文网页关键词提取与产品网页的信息提取问题。 本论文开展的主要工作及创新如下： 1 提出一种基于词性颗粒度的英文网页关键词提取算法。该算法首先将文本 进行3 g r a m 分词处理，同时去掉停用词：然后把中心词与修饰词等不同词性颗 粒给与不同权值打分，最后通过软闽值输出技术输出关键词，实现了一个比较 通用的关键词抽取系统。 2 提出一种新的商品网页信息分块算法。该算法基于本文提出的一套商品网 页规则化度量标准。论文依据商品网页的可统计性，给出了网页规则化度量标 准的数学表达式。本文算法首先将网页表示成d o m 树，然后将每一个叶节点表 示成x 删路径结构，同时根据得到的x p a t h 计算网页规则度的统计量，通 过对路径x p a t h 的聚类与得到的网页信息块统计量，结合启发式规则，实现分 割产品信息块。 3 实现了一种网页块分割与包装器( w r 印p e r ) 结合抽取产品信息的算法。该 方法首先利用网页信息块分割算法，分割出产品信息块；然后采用基于d o m 的 实例路径覆盖算法，学习抽取模版，抽取产品信息。 关键词：网页信息提取网络蜘蛛网页关键词提取分词信息抽取查询系统 a b s 仃a c t ab s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e t f a s ta 1 1 da c c u r a t ea c c e s st oi n f o m l a t i o n b e c o m e st h eb o n l e n e c ko ft h eg r o w i n go fi n d u s t r y i n t e ：m e t 嬲t h e 、 ，o r l d s l a r g e s t 仃e a s u r eo fi n f o m a t i o nr e s o u r c ea n r a c t sm o 佗跚dm o r ea 牡e n t i o n t h u s ，g e n e r a l s e a r c he n g i n ea p p e a r s h o w e v e r ，b e c a u s eo fm ei n f o 咖a t i o no v e rj o a d e dp r o b l e m ，i t w i l lb r i n gu s e l e s si n f o 眦a t i o nt 0u s e r s ，v e r t i c a ls e a r c hh a sb e c o m ean e wh o t s p o t b e i n gd i 丘e r e n tf o 椭g e n e r a ls e a r c h ，v e r t i c a is e a r c he n g i n e so n l yf o c u so nc e r t a i n a 他a s t h r o u 曲i n i t i a le x t r a c t i o no fw e bi n f 0 r m a t i o i l o nt h eo n eh a n d ，i tc a ni m p r o v e t h ea c c u r a c yo fs e a r c h ；o nt h eo m e rh a n db r o w s e r sd on o th a v et or e a dp a g eb yp a g e ， i m p r o v i n gr e a m n ge 仃i c i e n c y t h em a i nc o n t e n to ft h i st h e s i si st e c h n o l o g i e so f c o n s t r u c t i o no nt h ev e r t i c a is e a r c h i nm i st h e s i s ，w el a ye m p h a s i s0 nd i s c u s s i o nt h e i s s u e so ft h ee n g i i s hw e bp a g ek e y w o r de x 觚c t j o n 觚dp r o d u c tw e bp a g ei n f 0 咖a t i o n e x 灯a c t i o n t h em a i nw o r ka n di n n o v a t i o n so ft h i st h e s i sa r ea sf o l l o w s ： 1 p r o p o s ea ne n g l i s h 、e bk e ”旧r d se x t r a c t i o na l g o r i t h mw h i c hi sb 硒e do np a r to f s p e e c hg 啪u l a r i t y t h em e t h o df i r s t l yu s e s3 一g r a mt 0s e g m e n ts e n t e n c ei n t 0p h r a s e s ， g e t t i n gr i do fs t o pw o r d sa tt h es 锄et i m e ；t h e ng i v e sd i f r e r e n tm a r kt 0t h ec e n t e r w o r d sa n dm o r d i f i e d 、o r d s ；a tl a s te x p o r t sk e ”o r d sm r o u g hs o f tt h r e s h o l d t e c h n o l o g y s ow eg e n e r a t e 锄u n i v e r s a lk e y w o r d se x tr ：a c t i o ns y s t e mb a s e do np 矾o f s p e e c hg r a n u l a r i 够 2 p r o p o s ean e ws e g m e n t a t i o na l g o r i t h mf 0 fc o m m o d i t yw e bp a g ei n f o 咖a t b n b l o c l ( s t h em e t h o di sb a s e do n 、e bp a g er e g u l a r i t ys t a n d a r d sp r o p o s e db yt h i st h e s i s t h et h e s i sa l s og i v e st h em a t h e m a t i c a le x p r e s s i o no fw e br e g u l a r i t ys t a n d a r d s i nm i s t h e s i s ，w ef i r s t l yu s ed o m t r e et 0r e p r e s e n taw e bp a g e ，x r 气：i h 鼬m c t u r et 0d e n o t ea i e a fn o d e ；s e c o n d l yc o m p u t et h ew e br e g u l a r 时；a tl a s tt h r o u g hd o i n gt l ex p ! f q l hp a t h c l u s t e r i n ga n dt h eg e t t e dw e br e g u l a r i t ys t a t i s t i c ，t h ea l g o r i t h mc o m b i n e sh e u r i s t i c r u l e s ，s e g m e n t sp r o d u c tj n f o m a t j o nb j o c j ( s 3 i m p l e m e n tap r o d u c ti n f o m a t i o n se x t r a c t i o na l g o r i t h mw h i c hi sc o m b i n a t i o no f s e g m e n t a t i o nm e t h o da n dw r a p p e rt o o i t h em e t h o da p p l i e di nt h et h e s i sf i r s t l yu s e s w e bi n f o r n l a t i o nb l o c k ss e g m e n t a t i o na l g o r i t h mt os e g m e n tp r o d u c ti n f o 姗a t i o n b i o c l ( s ；t h e nu t i i i z e si n s t a n c ec o v e r a g ea i g o r i m mw h i c hi sb a s e do nt h ed o mt oi e 锄s e x 咖c t i o nt e m p i a t e ，e x 仃a c t sp r o d u c ti n f o m l a t i o n s k e ，w b r d s ： w e bi n 如肋a t i o ne x t r a c t i o n ，w e bs p i d w e b k e y w o r d se x 昀c t j o n ， w o r d ss e g m e n t a t i o n ，i l l f o 咖a t i o ne x t 豫c t i o na n dq u e 巧i n gs y s t e m i i 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：越 砌多年，月7 日 第一章绪论 第一章绪论 自然语言处理技术中，网页信息抽取是一个十分活跃的热点领域。由于互 联网的迅猛发展，网络已经成为一个巨大的信息宝库。然而，当前大部分网页 采用h 1 m l 语言编写，导致语义不清，无法进行二次有效利用，因而网页信息 抽取成为研究的难点与热点， l - l 信息抽取研究背景与现状 1 1 1 信息抽取产生的背景 信息抽取是自然语言处理一个非常活跃的分支，它通常是指从给定文本中 抽取出特定事件、时间，并且形成结构化的数据填入数据库中，供用户查询使 用的过程( z e c h n e rk ，2 0 0 2 ) 。信息抽取最早始于2 0 世纪6 0 年代，美国纽约大学 开展的l i n g t i i s t i cs 们n g 项目和耶鲁大学设计的f r u m p 系统( 李宝利等，2 0 0 3 ) 是最初的尝试。当代信息抽取的快速发展得益于m u c ( m e s s a g eu n d e r s 协n d i n g c o n f e 啪c e ) 系列会议的召开，在m u c 的推动下，信息抽取领域逐渐形成五种方 向( 朱巧明，2 0 0 5 ) 分别为： 1 ) 命名实体抽取 命名实体可以理解为一专有名词，例如：人名、公司名称、机构名称、地 点等。准确抽取命名实体对初步理解给定文档含义至关重要。在信息抽取领域 命名实体抽取是目前最有实用价值的一项技术，它是许多应用的基础环节。例 如广告信息抽取，如何抽取该广告宣传的商品名称。根据m u c 评测结果 ( c h i n c h o rn 1 9 9 8 ) ，英文命名实体识别任务的f 指数( 召回率与准确率的加权几 何平均值) 可以达到9 0 以上。 2 ) 模板元素抽取 模板元素就是实体的属性，它通过槽的形式描述了命名实体的基本信息， 如大小、颜色、类别等。模板元素为命名实体建立各种属性，从而更清楚地描 述命名实体。 第一章绪论 3 ) 共指事物抽取 不同命名实体指向同一事物即为共指，例如：“小明是个红领巾”，此处“小 明”和“红领巾”都是指代小明这个实体。共指信息的抽取方法主要有基于句 法、基于优先知识、基于简单同现、基于统计等。 4 ) 模板关系 模板关系是指模板元素之间存在的各种关系，或称事实。目前模板关系抽 取主要有基于知识库的方法、基于特征的机器学习方法等。 5 ) 场景模板抽取 场景模板又称为事件，即抽取事件本身的描述。例如某次会议的时间、地 点、主持人等。场景模板抽取目前的研究点在于模板的获取。目前主要由专家 针对不同领域手工写模板和自动获取模板两种方式，其中后者是主流研究方向。 图f 1 为命名实体与场景模板综合抽取实例。 图1 1 中文新闻信息抽取实例 中文信息抽取研究起步较晚，并且大部分集中在命名实体抽取方面( 张跃等， 1 9 9 7 ；谭红叶等，2 0 0 l ；郑家恒等，2 0 0 2 ) 目前还处在设计实现完整的中文信 息抽取系统的探索阶段。其中，具有代表性的研究成果有：朱靖波等( 1 9 9 8 ) 人使 用自然语言处理技术，以传统的多层信息抽取模型( h o b b s ，1 9 9 3 ：c a r d j e ，1 9 9 7 ) 为基础实现的中文无结构文本信息抽取；我国台湾的国立台湾大学a t i o n a i t a i w a n u n i v e r s i 哆) 开发的n t u 系统参加了m u c 7 中文命名实体任务的评测。 信息抽取一般来说可以笼统的分成三类：自由文本抽取、半格式化文本信 2 第一章绪论 息抽取、格式化文本信息抽取( k o s a l ar e ta 1 ，2 0 0 0 ) 。自由文本符合文法，具有 完整的语义，因而可以采用自然语言处理的词法、句子结构、句子间的关系建 立语法和语义的抽取规则。半格式化文本是介于自由文本和格式化文本之间一 种文本，例如：网页、广告等。半格式化网页的信息抽取通常利用包装器技术 ( k u s h m e r i c kn e ta i ，1 9 9 7 ；b r i ns ，1 9 9 8b a u e rm e t 献2 0 0 0 ；) 。本文主要关注半格 式化网页抽取方面的研究。结构化文本是指按照预先定义好的格式书写的文本。 1 1 2 信息抽取与信息检索的区别 在自然语言信息处理中还有一个与信息抽取容易混淆的概念一信息检索。 信息检索( i n f o 咖a t i o nr - e t r i e v a l ) 是从一定规模的文档库中找到满足用户信息需求 文档的技术。通用搜索引擎对网页的索引查询，就是信息检索最成功的应用。 图1 2 是以“中国科学技术大学”为关键字，从b a i d u 搜索引擎返回的部分网页 信息。可以看出网页信息检索工具仅仅对网页进行了简单的索引，没有进行深 层次的挖掘与应用。 - 翅面啦蛆幽隧 8 翻硷 露囊覃田科匏谚杰，：+ ：二二= 罡墅口哩墅口强i 龇 氲勘噬苫瞳苴：一：! 。 生露墼芏篷燃 少年斑理牮睫比学与村辩辩掌聿靠生0 辩幸掌茂工删肇事矗i l 辅擎境采簟睫魅唯宝 闻辑掌肇睫管理擘冼 文写l e * 荦掌睫巾譬 4 幸拄冀幸。卜五螂曩砭与震 j 肆蛸b 辩薹演孤掌校羹并孙舟c o p y 呐瞄挪申雹* 擎拽勾峰 - _ 眦o o t c 簟d u ；n ，强圹1 0 1 3 苴匿簋驻 生墨毪拦& 趑 擞譬读者1 正号- p 人暮玛懂啊谣者证号毒在卡置由帆上董嗣捌卫嘲鲁疰青l i t 证如万缱t 囊捌西区豳书硪一镥书库簟r 考码 ，蕾雌算e 量墓十协霉 c 肿j 5 中毒# 掌境献擘书镭 警嘲c 耐4 嘶雄细p 啦咖t 矿一瞰幻四玉，童区蹙蔓 生准膏证中蕾荤i 荦f i 啦掌t 臣专童董早加呻年鬟奇垒 珥宄辜报薯理蟮n 的童铒p 与j m 囊肇熏耋秉囊4 灌毫蛆 黟耐 ：t 口d 州t ：幽：叫嚣k 搬t 1 - 互瑾：兰蓝 肇堂圭就塑选氩瑰歉率盏熬，嗷燕太生 i 珊 4 产葺疆擘出# 犬章，日麟韭丈草2 0 礴邮1 烈巧捷千- 佛中曩 ，：埘曩唪业主麓业供麓啦7 - 1 2 l 鼬蕈薯囊疆鲁投育曩蝴譬蔫口7 t 2 1 怔 力冀聃阔叠可榀擅捌2 7 2 - 1 1 旺嚣笆神蚪t _ 憾柚涮c t 舯c - f 州3 d 3 7 2 3 豇e 兰翌 图1 2b a i d u 搜索引擎返回的结果信息 信息检索仅仅是按照用户提供的关键词，查询所存储的材料是否符合用户 需求。可以说这是一种对于存储文档最原始初级的应用，因为它完全没有利用 文档内在的语义关系。而信息抽取恰恰相反，它需要对文本进行一定的理解， 但与真正的文本理解还是不同的。在信息抽取中，一般只关心有限的感兴趣的 事实信息，而不关心文本意义的细微差别以及作者的写作意图等深层次理解问 3 第一章绪论 题。因此，信息抽取只是浅层次的文本理解技术。它们之间的主要差异表现在 以下三个方面( 朱巧明，2 0 0 5 ) ： 1 ) 功能不同 信息检索系统主要是从大量的文档集台中找到与用户需求相关的文档列 表；而信息抽取系统则从文本中直接获得用户感兴趣的事实信息。 2 ) 处理技术不同 信息检索系统通常利用统计或关键词匹配技术，把文本看成词的集合，不 需要对文本进行深入分析理解：而信息抽取往往要借助自然语言处理技术，通 过对文本中的句子以及篇章进行分析处理后才能得到所需要的信息。 3 1 适用领域不同 由于采用的技术不同，信息检索系统通常是领域无关的；而信息抽取系统 则是领域相关的，只能抽取系统预先设定好的有限种类的事实信息。信息检索 与信息抽取又是互补的。两者之间的区别与联系可以用图l _ 3 来直观表示。 量l 寸在 格式化量符 圈1 3 信息抽取系统与信息检索系统的差别 由于通用搜索会带来“信息过载”( b o w m 卸e ta i ，1 9 9 4 ) 问题，主要表现在有效 信息少、包含大量噪声、信息缺乏时效性和专业划分。因而，学者们将通用搜 索技术与信息抽取技术融合。创造性提出垂直搜索( v c r t i c a ls e a r c h ) 的概念 ( d i l i g e n t im e ta 1 ，2 0 0 2 ；c h a um e ta 1 ，2 0 0 2 ；c a g i g a sd ，2 0 0 4 ) 。垂直搜索又称为专 业搜索或者领域搜索。它是利用传统的定向爬取工具到专业网站爬取网页， 然后利用信息抽取技术，将预先定义韵模扳元素抽取出来，再利用搜索技术将 用户的请求返回给用户的过程。垂直搜索的关键技术就是网页信息抽取问题， 下一节将讨论网页信息抽取的现状。 4 第一章绪论 1 2 动态网页信息抽取的现状 所谓动态网页就是采用p h p 、j a v a s c r i p t 等脚本语言编写的页面。这类页面 通过把后台数据库的记录动态的嵌入页面，从而呈现给浏览者的网页非常规则。 由于数据显示的统一性，就为数据的抽取提供了方便。 动态网页的信息抽取一般采用w r a p p e “包装器) 的方式抽取信息。所谓 w r r a p p e r 就是一套计算机程序，该程序能够自动判断所抽取的信息是否为所需要 的信息。它由一系列的抽取规则及应用这些规则的程序组成，用于从特定的信 息源中抽取相关内容( e i l ( v i l ，1 9 9 9 ) 。目前的包装器一般都是利用网页信息的结构 特征，实现网页信息抽取，并以此为基础实现对网页的管理( f l o r e s c ue t a i ，l9 9 8 ；k o s a l ae ta 1 ，2 0 0 0 ) 。 包装器的生成方法有三类：人工方法、半自动方法、自动方法。其中，人 工生成包装器的方法指为每一种特定的信息源编写专用的代码。这种方法需要 花费很多时间理解信息源的结构并将其转化成代码，比较繁琐并且容易出错。 半自动方法指利用工具半自动的生成包装器( s a h u g u e te ta 1 ，1 9 9 8 ；b a u e r c t a 1 ，2 0 0 0 ；黄豫清等，2 0 0 0 ；朱明等，2 0 0 l ；李效东，2 0 0 2 ) 。例如：使用向导让用户标记 出需要抽取的信息，再根据标记的信息人工编写包装器。该类方法在包装器编 码时不需要专业知识，与人工方法相比可以减少错误，但是也需要对新的站点 进行重新学习。全自动的包装器生成方法( i ( u s h m e r i c ke ta 1 ，1 9 9 7 ；b r i n ，1 9 9 8 ； c r e s c e n z iv e ta 1 ，2 0 0 1 ) ，利用机器学习技术自动从信息源中利用归纳学习方法生 成抽取规则，用户仅需要在网页中标记出需要抽取的数据，系统就可以在这些 学习实例的基础上自动生成包装器。因此，全自动包装器生成方法己成为网页 信息抽取的重点研究内容。基于包装器归纳的信息抽取方法利用网页的重复结 构自动归纳学习抽取规则，具有抽取效率高和可移植性好等优点。然而，该方 法仅利用网页的局部规律归纳学习抽取规则，难以考虑网页的全局信息，因此 当网页中存在局部特征相似的多类信息时，会出现冗余信息抽取问题，导致该 方法针对信息类型的适应能力降低。 无论是手工、半自动还是自动生成的包装器，它们都是基于某种特定的方 法。与自然语言处理相比，基于包装器的w r c b 信息抽取器较少依赖句子的文法 特征，更注重于文本结构和表现格式的分析。这种方式更有利于w 曲页面的信 息抽取，使用包装器能够充分发掘w e b 页面的格式特征，避免使用复杂的语言 5 第一章绪论 学知识，加快信息抽取的速度。然而，使用包装器亦有困难之处，突出表现在 以下三个方面( 邵辉，2 0 0 6 ) ： 1 ) 包装器的针对性强，可拓展性差。个包装器处理一种特定的信息源，从 几个不同的信息源抽取信息，需要一系列的包装器程序库，造成巨大的工作量。 2 ) 可重用性差。包装器对页面结构的依赖性强，当出现一个新类型的w 曲 页面时或者旧的w 曲页面的结构发生变化时，原来的包装器就会失效，无法从 数据源中得到数据。 3 ) 缺乏对页面语义的理解。目前的包装器主要依赖于动态网页模式，基本上 是一种数据模式的还原，缺乏主动性的语义理解。 1 3 本文的主要工作 随着电子商务的发展，互联网上出现了越来越多的电子商务网站。在现代 商业竞争中，商品信息情报的快速准确获取，有利于检测竞争环境、分析竞争 对手、制订竞争策略，从而提高核心竞争力。然而，互联网是一个巨大的异构 信息源，仅凭人力是无法获取如此海量的信息，再加上w e b 网页天生的缺陷( 适 宜于人的浏览，不适宜计算机处理) ，如何从这些半格式化网页中进行信息抽取 成为研究热点。本论文的主要工作是关于垂直搜索的构建及其设计相关技术研 究，其中重点是英文网页关键词提取与商品网页的信息提取问题。主要工作如 下： 1 ) 通过分析正向匹配分词的算法原理，给出了算法流程图，实现基于正向最 大匹配技术的系统分词工具，并给出了实验分词结果。 2 ) 提出一种基于词性颗粒度的网页关键词抽取算法。该算法通过将中心词与 修饰词给与不同打分的策略，在词性颗粒度级实现一个比较通用的关键词抽取 系统。该算法带有负反馈机制、无需训练样本、计算复杂度低、便于实时抽取 应用。 3 ) 根据商品网页的可统计性，提出一套评价商品网页规则程度的度量标准， 并给出了数学表达式。 4 ) 提出一种商品网页信息分块算法。该算法基于网页规则度量标准，通过对 路径x p a t h 的聚类，结合启发式规则，分割产品信息块，提取其详细产品网页 链接及图像链接信息。 6 第一章绪论 5 ) 实现一种新的商品网页抽取模式一网页块分割与w r a p p e r 联合抽取模式。 该模式采用半自动化抽取方法，部分规则通过人工标注，同时尽可能多的采用 模式识别技术，使整个规则识别过程自动化；其次，采用商品网页分割算法， 分割产品记录块，提取链接信息：最后采用基于路径的d o m 技术抽取产品网页 中的信息。 6 ) 实现了一个基于w i n 3 2 平台的网络下载程序d o i p h i n 。该平台具有支持最 新的h t t p 1 1 协议、i p 爬取范围限制、d n s 缓存技术、剔出重复网页等功能。 通过以上技术探索，本文构筑了一个信息抽取查询系统。该系统包括系统 分词与网页关键词提取模块、网页爬取模块、查询模块、信息抽取模块。本论 文以该系统为主线，阐述相应的技术背景及我们自己研发的技术。 1 4 本文组织结构 本文组织结构如下： 第一章，绪论。该章简要回顾了信息抽取的历史、现状，阐述了信息抽取 的定义及其与信息查询的区别。 第二章，信息抽取查询系统的构架。概要介绍本文系统的总体架构、信息 抽取查询系统采用的主要技术手段。 第三章，详细分析了分词与关键词抽取的现状、原理、实现。本章实现了 系统所需的分词程序，同时论述了本论文网页关键词抽取的算法。 第四章，网络下载引擎的设计与实现。在垂直搜索系统中，网络蜘蛛的设 计是一个难点与关键，本章将详细介绍网络蜘蛛的原理与实现。 第五章，网页信息抽取系统的介绍。该章给出了网页规则度量的具体含义 与表示方法，并详细阐述了产品块网页分割算法与商品抽取系统原理。 第六章，本文的总结，并指出了未来的工作。 7 第二章信息抽取查询系统的构架 第二章信息抽取查询系统的构架 本章是本论文的论述行文线索，后续章节都以本章内容展开。由于通用搜 索收录的资源范围广，因而存在死链接较多、相关度较低等缺点，无法满足人 们对于信息个性化的需求，人们提出了垂直搜索技术( d i i i g e n t im e ta l ，2 0 0 2 ) 。 本章将介绍信息抽取查询系统的总体架构及各组成模块。 2 1 系统总体架构 一个完整的信息抽取查询系统涉及到四个模块：分词和关键词抽取模块、 网页下载引擎模块、网页信息抽取模块、查询模块。垂直系统涉及到许多基础 研究技术：分词、信息抽取、索引、匹配、网络等等。图2 1 是本论文系统总体 设计。本章简要介绍相关技术背景，便于后续章节展开讨论。第三章是关于分 词与基于词性颗粒度的网页关键词提取，第四章的主要内容为网络蜘蛛的设计 与实现，第五章是本系统的信息抽取模块。 图2 1 系统结构框图 系统首先到领域网站下载网页( 一般把网页下载引擎称为网络蜘蛛w 曲 s p i d e r ) 。在垂直搜索系统中，与通用搜索的爬虫不同，需要采用定向爬虫，因为 垂直系统都是关注某一领域，其余网页不感兴趣。把下载的网页输入到网页信 息抽取模块( 此模块是本文介绍和研究的重点) 。信息抽取模块一般采用人工书写 8 第二章信息抽取查询系统的构架 规则( h 锄m e r e ta i ，l9 9 7 ) 或者机器学习( l e m a nk e ta i ，2 0 0 4 ) 策略进行信息抽取。 该模块将抽取的信息形成格式化的数据，存入数据库供用户查询或者分析。用 户使用查询界面输入关键词，系统c g i 程序( s t e p h e ne ta 1 ，1 9 9 8 ；杨虎，2 0 0 l ；刘 伟，2 0 0 1 ) 将客户提交的表单传递给查询系统，此时系统调用分词程序，将用户的 输入进行切分。( 有的系统采用n g r 锄( 周水庚，2 0 0 l ；毛伟，2 0 0 6 ) 以获得更好 的切分效果) 。查询模块我们采用l e m u r ( c m u 内核。l 锄u r 是一个信息检索工 具包，它将一些常用的检索模型都做成标准的a p i ( a p p l i c a t i o np r o g r a m i n 幻r f a c e ) ，供用户使用。通过l e m u r 做的倒排索引，在数据库中找到匹配信息， 然后将相关信息和网页共同返回给用户。 2 2 分词及网页关键词抽取模块 2 2 1 分词的研究现状 由于中文语言的特殊性，不像西方语言那样词与词之间有空格隔开，如何 正确提取中文词语成为中文信息处理领域的难点。通常采用的方法是中文分词， 将中文按语义分解成单个的字或词，然后以这些字词作为特征项进行特征提取。 中文分词在诸如篇章理解、机器翻译、文本检索、文本校对、过滤、分类、自 动摘要等领域都是基础性的工作。因此，汉语分词技术已成为中文信息处理技 术中的最为基础的课题。 中文分词研究始于2 0 世纪8 0 年代，目前已经有模式匹配分词方法、基于 规则的方法( 刘源，1 9 9 4 ) 、基于理解的方法、基于统计的方法( 赵铁军等，2 0 0 l ； 张华平，2 0 0 2 ) 。在国家的支持下，我国已开发出多套分词系统( 孙斌，1 9 9 9 ) ， 主要有以下几个： 】) c d 、鹏分词系统 该分词系统是我国第一个实用的自动分词系统，由北京航空航天大学计算 机系于1 9 8 3 年设计实现，它采用的自动分词方法为最大匹配法，辅助以词尾构 词纠错技术。其分词的速度为5 1 0 字秒，切分精度约为l 6 2 5 ，基本满足了词 频统计和其他一些应用的需求。这是汉语字典分词的首次尝试，具有很大的启 发作用和理论意义。 2 ) 清华大学s e g l a g 系统 o 第二章信息抽取查询系统的构架 此系统着眼于将各种各样的信息进行综合，以便最大限度的利用这些信息 提高切分精度。系统使用有向图来集成各种各样的信息，这些信息包括切分标 志、预切分模式、其他切分单位。为了实现有限的全切分，系统对词典的每一 个重要的词都加上了切分标志，即标志“c k ”或“q k 。“q k ”标志表示该词可进 行绝对切分，不必理会它是否会产生切分歧义；“c k ”标志表示该词有组合歧义， 系统将对其进行全切分，即保留其所有可能的切分方式。系统通过这两种标志 并使用几条规则以实现有限的全切分，限制过多的切分和没有必要的搜索。规 则包括： 无条件切出q k 类词。 完全切分c k 类词( 保留所有可能的子串) 。 对于没有标记( q k 或c k ) 的词，若它与别的词之间存在交叉歧义，则做全 切分；否则，将其切出。 为了获得更好切分结果，系统采用在有向图d a g 上搜索最佳路径的方法， 通过使用评价函数，求得评价函数的极大值而获得最佳路径p m a x 。所运用的搜 索算法有两种：动态规划、全切分搜索加叶子评价。同时使用了词频、词类频 度、词类共现频度等统计信息。通过实验，该系统的切分精度基本上可达到9 7 。左右，能够处理未登录词比较密集的文本，切分速度约为3 0 字秒。 3 1 哈工大统计分词系统 该系统是一种典型的运用统计纯切词系统，它试图将串频统计和词匹配技 术结合起来。 系统有三个部分构成： 第一部分，预处理模块。利用显式和隐式切分标记( 标点、数字、英文字符 以及出现频率高、构词能力差的单字词、数词+ 单字常用量词模式) ，将待分析的 文本切分成短的汉字串。这大大地减少了需要统计的无效字串的数量和高频单 字或量词边界串。 第二部分，串频统计模块。此模块计算各个已分开的短汉字串中所有长度 大于一的字串在局部上下文中出现的次数，并根据串频对每个这样的子串进行 加权。 第三部分，切分模块。首先用临时词库对每个短的汉字串进行切分，使用 的是逐词遍历算法；再利用一个小型的常用词词典对汉字短串中未进行切分的 子串进行正向最大匹配分词。对于短汉字串中那些仍未切分的子串，则将所有 l o 第二章信息抽取查询系统的构架 相邻单字作为一个权值很低的生词。其中每个模块都对待分析的文本进行一次 扫描，因而是三遍扫描的方法。此系统能够利用上下文识别大部分生词，解决 一部分切分歧义，但是统计分词方法对常用词识别精度差的固有缺点仍然存在， 系统地分词错误率为1 5 速度为2 5 6 字秒。 4 1 i c t c l a s 分词系统 该分词系统由北京计算所研发，系统使用了基于统计的分词方法，很好地 解决了切分歧义问题。该系统整体采用了基于隐马尔可夫的结构，系统采用了 两个核心词典( 一个一元词典和一个二元词典) ，实际分词过程首先使用一元词典 进行字符串匹配，得到一个句子所有的可能词；然后采用二元词典进行切分歧 义的消岐处理。通过国家9 7 3 专家组组织的测评，测试结果显示该系统分词的 正确率9 7 5 8 ，分词速度3i 5 k b ，s 。 本论文从系统的复杂性与可用度出发，经过综合考虑决定采用最大匹配方 法作为系统的分词算法。一方面系统不需要精准的分词，最大匹配算法完全可 以满足系统的需要：另一方面分词程序不是本系统的重点，笔者也没有足够的 精力实现一套复杂的分词算法。 2 2 2 关键词提取 2 2 2 1 关键词定义 关键词是从文献中提炼出来，能够概括文献内容的词或词组。因此，这些 选出来的关键词应具各如下特征( 罗式胜，1 9 9 4 ) ： 1 ) 高浓缩性：关键词的数量虽然不多( 人工提取的通常为3 至5 个) ，但这几个 关键词应能够高度的概括和代表整个文献的基本内容。所以，通过对关键词的 考察，能够窥视到该篇文献的全貌。 2 ) 可计量性：每篇文献的关键词的数量的有限性带来了关键词的可统计性， 而可统计性又为文献的研究奠定了良好的基础。 3 ) 链接性：由于不同的文献来源于不同的作者，因此各个文献在关键词方面 的某些联系必然反映出文献之间的某些关系，这些关系或是表现在文章内容上， 或是表现在研究的方向上。这些关系像一条无形的“链”，把这些文献紧密地联 系起来。通过定义这些关系，必然会对搜索引擎提供极大的帮助。 第二章信息抽取查询系统的构架 2 2 2 2 关键词提取研究现状 关键词自动提取在很多方面有着直接应用，例如：文本分类、自动标引、 信息检索等等。关键词是从一连串预先指定的词组中选择出来的。目前关键词 提取主要有两种技术：机械学习方式( b a r k e rk e ta 1 ，2 0 0 0 ；于鲲等，2 0 0 2 ；郑家 恒等，2 0 0 5 ) 和软学习方式f r u m e y ，1 9 9 9 ；f r a n k e ta 1 ，1 9 9 9 ；h u l t l l 2 0 0 3 ) 。 目前国内关键词抽取研究还处于起步阶段。于鲲( 2 0 0 2 ) 等在网页关键词抽取 中利用词频和字体信息等特征，来计算关键词的权值。郑家恒( 2 0 0 5 ) 等的关键词 提取与此类似，他们利用文档特征，将该词在文章中出现的不同位置给与不同 的权值，在题目中出现给与最大的权值，出现的位置越靠后权值越低然后构 造了权值函数，输出关键词序列。 国外在关键词提取中起步较早，目前已经形成了系统。例如g e n e x ( t u m e y ) ， k e a ( f r a n k ) 。t u n l e y ( 1 9 9 9 ) 的系统采用遗传算法作为核心模型，通过实例学习预 先定义的特征，得到启发式的抽取规则，学习出抽取模型。f r a n k ( 1 9 9 9 ) 则利用 贝叶斯模型为算法核心。该系统通过事先标注好的语料，学习得到贝叶斯概率 模型，然后对候选词按照概率分值排序，取前几个分支大的候选关键词作为关 键词。 本文的关键词抽取算法采用机械式学习方法。与上文提到的系统不同，本 论文的关键词抽取综合考虑了词性、词频、文档频率，尽量减少对文档结构的 依赖，使抽取算法更朴实。同时在输出关键词是并不指定输出数量，而是采用 输出阔值控制技术，实验证明这样的方法更有效。 2 3 网络蜘蛛模块 2 3 1 网络蜘蛛研究现状 由于互联网中有数以千亿计的网页，所以要人工收集网页是不现实的，现在 一般采用网络蜘蛛( w e bs p i d e 咿一一种收集网页的机器人进行网页的自动收集。 网络蜘蛛在i n t e m e t 上抓取网页一般从给定的种子u r l 开始，按照一定的策略 遍历i n t e m c t 。常用的遍历策略有深度优先和广度优先。广度优先是指网络蜘蛛 先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取 1 2 第二章信息抽取查询系统的构架 在此网页中链接的所有网页。这是最常用的方式，因为这个方法可以让网络蜘蛛 并行处理，提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始，一个链接 一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。 图2 2 是两种抓取网页的示意图。 帅帅 广皇饨 危骑矗取喷弗- p h c d 量f i i o l 图2 2 两种网页爬取方式 目前学界对于网络蜘蛛的研究，主要集中于网站网页变化趋势的数学建模 上。现在一般把网页的变化视为泊松过程( b r e w i n g t o nb ee ta 1 ，2 0 0 0 ；孟涛等， 2 0 0 6 ) 。从某个时刻0 开始，用x ( f ) 记某个网页在时刻t 变化的次数，网页的每 次变化都是独立同分布的，且变化频率是五，根据泊松过程的定义， p r x ( s + t ) x ( s ) ：k ) ：笔拿p ，七：o l ( 2 - i ) 假定网页下次变化的时刻是r ，则r 的概率密度函数为 似= f = 当k = 1 时，有式( 2 1 ) 可知网页两次变化的间隔时间服从指数分布，即( 2 2 ) 式。 对于搜集系统而言，如果它在某时刻存在本地的某网页的内容与当时该网页砸 w r e b 中的实际内容相同，就称该网页时时新的。 基于网页变化模型，需要通过搜集来估计其参数，以获得网页变化频率并 推算下次变化的时间( 孟涛等，2 0 0 6 ) 。对网页变化频率a 的直接估计，最简单的 办法就是用变化的总次数x 除以时刻o 丁的变化间隔( c h oje ta 1 ，2 0 0 0 ) 。如果用 ，表示z 与搜集频率厂比值，则，最简单的估计为 第二章信息抽取查询系统的构架 ；：喜： ( 与：墨 ( 2 3 ) ff 、t 。 n 1。 其中，n 是该时刻间隔内搜集检查的次数。这种估计方法的期望和方差分别是 昱【刁= 薹詈p r 扩= 詈 = 薹詈+ ( ：j ( 1 一g ) ”g ”4 = ，一g ” ( z - 4 ) 矿两= e 【2 卜e 畸 2 = p ”( 1 一p ”) 刀 ( 2 - 5 ) 据此可以判断，式( 2 3 ) 的估计方法是有偏差的，而且效率随着搜集次数的增大 而提高。它最大的缺点是布局别一致性偏差与h 无关，因为通常都希望搜集次 数越名，估测误差越小。 2 3 2 网页爬取面临的问题 网络蜘蛛在爬取网页时会遇到很多问题，突出表现在一下几个方面： 第一，网站的网页存在更新问题，也就是上文讨论的网页变化模型。对于 较大的门户网站，例如：s i n a ，t o m 、y a l l o o 、1 6 3 等，由于其更新频率较快，可 以采取每天爬取策略。但是在网络中更多是中小型的网站，其网页更新可能一 个星期，甚至一个月。抓取频率过高，可能重复爬取同一张网页：频率过低， 又影响网页检索的召回率。如何爬取这些网站的网页是一个挑战。 第二，i n t e m e t 中的网站可以抽象成一个有向图，这里就存在一个循环链问 题，如图2 3 所示。例如路径e d g h 形成一个闭路。闭路会使网络蜘蛛陷入 死循环，如何设计蜘蛛使之跳出循环? 同时可以看到路径b e 是一个互指路径， 也可能造成死循环。 1 4 图2 3 网页模型示意图 第二章信息抽取查询系统的构架 第三，在垂直爬虫中还存在主题孤岛问题( 叶勤勇，2 0 0 7 ) 。互联网上网页有 主题相邻性规律，然而实际的互联网并不是总是这样，与主题相关的网页并不 总是在一起的，从一张主题相关的网页出发往往要经过几张与主题无关的网页 后才能再次到达主题相关的网页。如果我们把相连在一起的主题相关网页称为 一个主题岛，那么整个互联网就是有无数这样的主题岛构成，各个主题岛被一 些主题无关网页分割。实际的互联网应该存在不计其数的这样主题孤岛，如果 我们仅仅抓取主题相关的页面的u 也，会错失很多主题孤岛，从而导致召回率 很低。因为连接主题孤岛的是主题无关页面，只有先抓取这些页面才能进入主 题孤岛，如何突破主题孤岛问题，是一个很重要的问题。 第四，网页数量的指数上升，网页的时刻变化更新，而搜索引擎无法及时 跟踪网页自身的变化更新，搜索引擎自身又受存储容量、服务器能力等资源的 限制。所以，如何在这些客观制约之下，使得搜索引擎爬行高质量的网页，提 高网页库的新鲜度，以此来提高搜索引擎的查询结果的质量，让用户得到更新 更有用的信息，已成为搜索引擎急切要解决的问题。 本论文的网络蜘蛛采用广度优先的遍历策略，同时具有剔除重复网页和地 址访问限制的功能。考虑到个人的精力及实现难度，作者忽略了信息孤岛的问 题，因而本论文设计的蜘蛛需要使用者自己提供爬取信息所在的位置信息。 2 4 网页信息抽取模块 2 4 1 半格式化网页的来源 关于半格式化数据的定义，第一章已经阐明，就是介于格式化( 如关系数据 库，面向