（计算机应用技术专业论文）基于树结构的web信息抽取技术研究.pdf

r i ， a t h e s i si n c o m p u t e ra p p l i c a t i o nt e c h n o l o g y b y l i a nc h e n g y a n g a d v i s e db y m a o y u - g u a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g m a r c h ，2 0 1 0 1 i i i iiiiil 7 6 9 诤p，j 、 i _ ： & 本人授权南京航空航天大学可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：痉盘碰 e l 期： 型f 旦13 ，1 7 k 】 南京航空航大人学硕十学位论文 摘要 随着i n t e m e t 的发展，w e b 已经成为一个庞大而复杂的知识库，研究如何从w e b 中抽取信 息交得越来越重要。w e b 中有一类重要的页面是数据导向型页面，这种页面动态生成、便于更 新，研究如何从这种页面中抽取信息是w e b 信息抽取技术研究的重点。 在学习信息抽取相关理论和前人研究成果的基础上，本文针对数据导向型页面提出了一种 基于树结构的w e b 信息抽取方法。围绕此方法做了以下工作：第一，提出了一种基于二叉树的 h t m l 到x m l 的转换方法。从h t m l 到x m l 的转换是w e b 信息抽取的预处理模块，对w e b 信息抽取的效果起着决定性的作用。本文提出的基于二叉树的h t m l 到x m l 的转换方法可以 有效地处理h t m l 中三种典型的错误。第二，提出了一种新的w e b 信息抽取中数据记录的定 位方法。本文提出的数据记录定位方法分三步进行，首先通过计算节点的扇出度定位主要内容 区，然后在主要内容区内定位数据区域，最后在数据区域内定位数据记录。分析发现s t m 算 法在进行树的匹配时不够准确，本文对其进行了改进，提出了一种加权的树匹配算法s t m c t n ， 并相应地改进了树的相似度计算等算法。第三，提出了一种新的w e b 信息抽取中数据属性的对 齐方法。在定位到数据记录以后，需要对同一类的多个数据记录进行比对，将其数据属性进行 对齐，进而输出数据记录，为此本文提出了一种基于聚类和树的比对的数据属性对齐方法，本 方法避免了对齐结果冗余过多的现象。针对本文提出的三种方法，分别通过实验对方法的性能 进行了分析。 关键词：w e b 信息抽取，数据导向型页面，二叉树，数据记录定位，s t m c t n 算法，层次聚类， 数据属性对齐 基丁树结构的w e b 信息抽取技术研究 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r a c t ，w e bh a sb e c o m eal a r g ea n dc o m p l e xk n o w l e d g eb a s e ，t h e r e s e a r c ho fh o wt oe x t r a c ti n f o r m a t i o nf r o mw e bb e c o m e sm o r ea n dm o r ei m p o r t a n t t h e r ei sa n i m p o r t a n tc l a s so fw e bp a g e sc a l l e dd a t a - o r i e n t e dp a g e ，t h i sc l a s so fp a g ei sg e n e r a t e dd y n a m i c a l l y a n dc a l lb eu p d a t e de a s i l y h o wt oe x t r a c ti n f o r m a t i o nf r o mt h i sk i n do fp a g ei st h ef o c u so fw e b i n f o r m a t i o ne x t r a c t i o nt e c h n o l o g yr e s e a r c h o nt h eb a s i so fp r e v i o u sr e s e a r c hr e s u l t sa n dt h es t u d yo fi n f o r m a t i o ne x t r a c t i o nt h e o r y , t h i s p a p e rp r e s e n t s an e ww e bi n f o r m a t i o ne x t r a c t i o nm e t h o db a s e do nt r e es t r u c t u r et oe x t r a c t i n f o r m a t i o nf r o mt h i sc l a s so fp a g e ，a n dt h ef o l l o w i n gp a r t ss h o wt h ew o r k st h ep a p e rd o e sa r o u n d t h i sm e t h o d f i r s t l y , an e wm e t h o dt oc o n v e r th t m li n t ox m li sp r o p o s e d a st h ep r e - p r o c e s s i n g m o d u l eo fw e bi n f o r m a t i o ne x t r a c t i o n ，t h et r a n s f o r m a t i o nf r o mh t m lf i l et ox m lf i l ep l a y sak e y r o l ei nw e bi n f o r m a t i o ne x t r a c t i o n t h ec o n v e r t i o nm e t h o dt h i sp a p e rp r e s e n t si sb a s e do nb i n a r yt r e e ， c a l lh a n d l et h r e et y p i c a le r r o r si nh t m l s e c o n d l an o v e lm e a s u r et of i xt h ep o s i t i o no fd a t ar e c o r d s i sb r o u g h tf o r w a r d t h em e a s u r ew i l lf i xt h ep o s i t i o no fd a t ar e c o r d sb yt h r e es t e p s a tf i r s t ，m a i n c o n t e n ta r e a sw i l lb ef o u n do u ta c c o r d i n gt ot h eo u t - d e g r e eo fe v e r yn o d e a n dt h e n ，a l ld a t ar e g i o n s i ne v e r ym a i nc o n t e n ta r e aw i l lb ep i c k e do u t ，i nt h i ss t e pat r e em a t c h i n ga l g o r i t h mb a s e do nw e i g h t c a l l e ds t m c t ni sp r o p o s e d ，a n da c c o r d i n g l y , a l g o r i t h m s ，s u c ha sc a l c u l a t i n gt h es i m i l a r i t yo ft r e e s ， a 托a l s oi m p r o v e d a tl a s t ，t h ed a t ar e c o r d sw i l lb es o u g h to u tf r o me v e r yd a t ar e g i o n t h e e f f e c t i v e n e s sa n da c c u r a c yo ft h i sm e a s u r ei sd e m o n s t r a t e db yr e s u l t so fe x p e r i m e n t s t h i r d l y , t h i s p a p e rp r e s e n t sa ne f f e c t i v ea p p r o a c ht oa l i g nd a t aa t t r i b u t e s a r e ra l lt h ed a t ar e c o r d sa r ef o u n d ，a n a p p r o a c ht oc o m p a r ee v e r yd a t ar e c o r do ft h es a m ec l a s sa n da l i g na l lt h ed a t aa t t r i b u t e so ft h e mi s n e e d e d t h ea p p r o a c ht h i sp a p e rp r o p o s e st oa r r i v et h i so b j e c ti sb a s e do nc l u s t e ra n dt r e ea l i g n m e n t , i ta v o i d st h ep h e n o m e n o nt h a tt h er e s u l t so fa l i g n m e n tt a k et o om a n yr e d u n d a n t t h ep e r f o r m a n c eo f t h e s ep r o p o s e dm e t h o d sa l ea n a l y s e dt h r o u g he x p e r i m e n t s k e yw o r d s ：w e bi n f o r m a t i o ne x t r a c t i o n , d a t a - o r i e n t e dp a g e s ，b i n a r yt r e e ，d a t ar e c o r dp o s i t i o n , s t m c t n a l g o r i t h m , h i e r a r c h i c a lc l u s t e r i n g , a l i g n m e n to fd a t aa t t r i b u t e s 一 t r 1 1 2 3 1 4 本文的研究内容及组织。5 第二章w e b 信息抽取技术7 2 1w e b 信息抽取技术的概念。7 2 2 信息抽取与信息检索7 2 3 现有w e b 信息抽取技术的分类8 2 3 1 根据自动化程度分类8 2 3 2 根据抽取原理分类。8 2 4w e b 信息抽取存在的问题1 l 2 5w e b 信息抽取系统的评价指标1 l 2 6 ，j 、结1 ：! 第三章基于二叉树的h t m l 到x m l 的转换方法1 3 3 1 引言1 3 3 2h t m l 、x m l 和x h t m l 1 4 3 3x m l 和h t m l 的二叉树表示1 5 3 4 基于二叉树的h t m l 到x m l 的转换算法1 7 3 4 1 算法流程1 7 3 4 2 将h t m l 划分为段列表1 7 3 4 3h t m l 二叉树的构造1 8 3 4 4x m l 文件的输出2 0 3 4 5 算法实例2 l 3 4 6 算法修正2 1 3 5 实验及分析2 l 3 6 ，j 、2 ；2 3 基于树结构的w e b 信息抽取技术研究 第四章w e b 信息抽取中的数据记录定位2 4 4 1i ；i 言2 4 4 2 主要内容区的定位2 5 4 3 数据区域的定位2 7 4 3 1 树的编辑距离2 8 4 3 2 树的最大匹配2 9 4 3 3 树的相似度计算。3 6 4 3 4 一般节点的比较3 9 4 3 5 数据区域的定位4 l 4 4 数据记录的定位4 4 4 5 实验及分析4 6 4 6d 、结4 9 第五章w e b 信息抽取中的数据属性对齐和抽取5 0 5 1 引言5 0 5 2 数据记录的聚类5l 5 3 数据属性的对齐5 2 5 3 1 处理流程5 2 5 3 2 插入主树的条件5 3 5 4 基于聚类的数据记录对齐算法5 4 5 5 实验及分析5 7 5 6 小结5 9 第六章总结与展望6 0 6 1 总结6 0 6 2 展望6 0 参考文献6 2 墅l 【谢6 6 在学期间的研究成果及发表的学术论文6 7 一 - ， 南京航空航天大学硕士学位论文 图表清单 图1 1 数据导向型页面举例4 图1 2 本文的研究原型5 图3 1h t m l 文本与相应的x m l 格式表示1 5 图3 2 格式非严格的h t m l 文档示例。15 图3 3h t m l 文本的二叉树表示1 6 图3 4 将h n 缸，划分为段序列18 图3 5 图3 2 转换后的x m l 文本2 l 图3 6 实验结果对比。2 2 图4 1 示例d o m 树2 5 图4 2 一般节点及数据区域示意图2 7 图4 3 文本节点匹配不当图示。3 0 图4 4 父子节点信息值关系图。3 2 图4 5 节点权重计算方法示例3 2 图4 6 节点价值计算方法示例3 3 图4 7s t m c t n 算法执行过程示例。3 6 图4 8 树的相似度计算3 8 图4 9 一般节点的比较3 9 图4 1 0 数据区域示例。4 l 图4 11 函数r e c d r s 的伪代码4 3 图4 1 2 函数u n c o v e r e d d r s 的伪代码4 4 图4 1 3 数据记录不连续情况一：4 5 图4 14 数据记录不连续情况二4 6 图4 15 实验结果对比4 8 图4 1 6 实验结果对比4 9 图5 1 未匹配节点可插入主树的情况一5 3 图5 2 未匹配节点可插入主树的情况二5 3 图5 3 未匹配节点可插入主树的情况三5 3 图5 4 未匹配节点不可插入主树的情况。5 4 图5 5 代表同一簇中的三条数据记录的d o m 树5 6 基于树结构的w e b 信息抽取技术研究 图5 6 树t m 与树t 3 的对齐操作5 6 图5 7 树t m 与树1 r 2 操作。5 6 图5 8 算法的最终结果：5 6 图5 9 实验结果对比5 8 表3 1 实验数据。2 2 表4 1 图4 3 ( b ) 的错误的匹配结果3 0 表4 2 图4 3 ( b ) 的正确的匹配结果3 0 表4 3 低层节点的匹配值3 6 表4 4 高层节点的匹配值3 6 表4 5 实验数据4 7 表4 6 实验数据。4 8 表4 7 实验数据对比4 9 表5 1 示例结果5 7 表5 2 实验数据5 8 - ， f 南京航空航天人学硕十学位论文 h t m l s q l d o m x m l x h t ， m 己 w 3 c s t m s r m c t n 注释表 h y p e rt e x tm a r k - u pl a n g u a g e s t r u c t u r e dq u e r yl a n g u a g e d o c u m e n t0 b j e c tm o d e l e x t e n s i b l em a r k u pl a n g u a g e e x t e n s i b l eh y p e r t e x tm a r k u pl a n g u a g e i n f o r m a t i o ne x t r a c t i o n i n f o r m a t i o nr e t d e v a l 肋r i dw i d e 踞bc o n s o r t i 脚 s i m p l et r e em a t c h i n g s i m p l et r e em a t c h i n gw i t hc o n s i d e r a t i o no ft e x t - c o n t e n ta n d n o d e w e i g h t 南京航空航天大学硕十学位论文 第一章绪论 随着w e b 技术的发展，w e b 信息抽取逐渐成为研究的热点，本章首先介绍w e b 信息抽取 技术的研究背景和意义，然后描述在w e b 信息抽取领域国内外的研究现状，接下来阐述本文的 研究对象和研究模型，最后给出本文的研究内容和组织结构。 1 1 研究背景和意义 随着计算机网络和通信技术的发展，i n t e r n e t 逐渐成为信息获取和发布的平台，w e b 已经成 为一个巨大的、共享的和分布式的信息空间。但是，目前的w e b 页面大部分以非结构化或半结 构化的h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) 形式出现，主要目的是让人们通过浏览器浏览， 不含清晰的语义信息，无法像关系数据库那样通过结构化查询语言( s t r u c t u r e dq u e r yl a n g u a g e ， s q l ) 查询，也无法供应用程序进行利用。要从这样一个庞大的资源中找到自己想要的信息， 用户需要耗费大量的精力和时间，效率低下，并且很容易迷失在数据的海洋里，很可能多次的 ：l 二作都是零回报的。如何从w e b 页面中有效、快速地获取所需信息成为亟待解决的问题。在这 种背景下出现了搜索引擎，它帮助人们通过给定的关键词来获取相关的页面。然而，搜索引擎 只是部分缓解了信息获取的问题，效果并不能十分令人满意，它还存在很多问题需要解决，不 足之处【i 】主要表现在三个方面：一是只给出了相关页面的链接，用户还需要通过手工浏览网页 才能找到相关信息；二是搜索结果不准确，大量的搜索结果都是用户不需要的；三是检索模式 简单，无法提供类似s q l 这样强大的查询语言，由于无法定制精确的查询，想要获取精确的结 果是不可能的。 为了进一步解决“信息爆炸，知识匮乏”的现象，w e b 信息抽取技术应运而生，它将现有 的w e b 信息源进行包装，将网页上的信息以更为结构化的方式抽取出来，为应用程序利用w e b 中的数据提供了可能。w e b 信息抽取技术不但可以直接定位到用户所需的信息，而且采用一定 的方式增加了语义和模式信息，为w e b 查询提供了更为精确的方法，使w e b 信息的再利用成 为可能，因此有着明显的优势和广阔的前景，是当今多个领域的研究热点。现有信息抽取思想 的提出在一定程度上推动了w e b 信息抽取技术的研究和发展，但是，这些信息抽取方法仍具有 一定的局限性；大部分系统使用的抽取规则描述语言是自行定义的，抽取模式不能统一；为了 更大程度地提高抽取规则自动构造的能力，通常需要大量的样本学习：使用本体的方法则需要 领域专家的干预以及较多的先验知识，使得系统的适应性较差；根据特定网页结构产生的包装 器则不能适应网页的多变性等等。因此，有必要对信息抽取技术做进一步的研究。 基于树结构的w e b 信息抽取技术研究 1 2 国内外研究现状 目前，w e b 信息抽取技术已经取得了较大的研究成果，利用现有的技术水平已经能够建造 全自动的w e b 信息抽取系统，并且在很多方面都能满足用户的需求。 国外w e b 信息抽取技术的研究起步比较早，已经研究出了很多可使用的系统： ( 1 ) l i x t o 2 】系统。在该系统中，用户以可视化、交互式的方式对样本网页中的信息进行 标记，系统通过用户标记的信息生成抽取规则，从而能够实现对具有相似页面结构的网页进行 抽取。该系统在一定程度上增强了信息抽取技术的实用性，简化了信息抽取的步骤。当然它也 存在着缺点：不支持对图像信息和文献信息的处理，抽取规则中没有对抽取信息进行丰富的描 述，实现和优化抽取规则比较困难。 ( 2 ) r o a d r u n n e r t 3 】系统。此系统通过对n 个样本页面结构的比较，得到该类页面的结构模 式，然后利用得到的结构模式来完成对相似页面的信息抽取。该系统最大的优点是实现了全自 动的信息抽取，但是该系统抽取出来的信息依旧没有语义，并且在利用该系统时需要大量的训 练样本。 ( 3 ) w h i s k 4 系统。该系统对结构、半结构和无结构的文本均能进行处理。大体工作过程 是：用户在可视化的环境下根据系统提供的实例标记出感兴趣的信息，系统利用语法和语义分 析器，分析出用户标记信息的语法成分和对应的语义类，生成基于语法标记和语义标记的抽取 规则，实现信息抽取。 ( 4 ) x w r a p 5 1 系统。该系统可以实现人机交互，首先由用户通过输入在样本页面中指定抽 取区域的起始位置，系统根据用户的输入确定抽取区域及其类型：然后通过可视化的方式，用 户在样本页面中指定语义项及与之对应的实例，系统会自动产生抽取规则，进而完成信息抽取。 该系统能够根据用户的输入，对于不同的数据区域类型采用不同的抽取规贝q ，系统的灵活性和 效率比较高。但是该系统只能对具有明显区域结构的网页进行抽取，模式的表达能力有限，并 且需要用户的参与过多。 ( 5 ) m d r 6 1 系统。m d r 系统是近年来比较流行的全自动抽取方法，该系统通过标签树来 描述模版，利用字符串的匹配进行数据定位。该系统能够从网页中抽取结构化的数据记录。但 是，该系统采用字符串的匹配比较繁琐，并且对数据记录分布不连续的情况不能进行处理，需 要进一步改进。 国内迄今为止的研究基本上处于包装器的半自动生成阶段，尚未出现自动识别网页，然后 产生包装器，进而抽取数据的方法。国内较为典型的系统和算法有： ( 1 ) 中国人民大学数据与知识研究所提出的基于预定义模式的包装器【7 l 。由用户定义模式 并给出模式与i - f r m l 网页的映射关系，接着系统推导出规则，同时生成包装器。本方法人工参 与的工作很多，工作量很大，并且不具备可移植性 2 南京航空航天大学硕+ 学位论文 ( 2 ) 中科院软件所提出的基于d o m ( d o c u m e n to b j e c tm o d e l ) 的信息提取方法【b 】该方法 以文档对象模型为基础，把所要提取的信息在d o m 层次结构中的路径作为信息抽取的“坐标”， 并以这个基本原理为基础设计了一种归纳学习算法来半自动化地生成抽取规则，然后根据抽取 规则生成类，将该类作为w 曲数据源包装器组成的重要构件。 ( 3 ) 中国科技大学提出的基于多层模式的多记录网页信息抽取方法 9 1 。该方法的基本思想 是：h t m l 网页信息的抽取只利用多层模式来加以描述，以便能够利用各层模式之间相互联系 的特点动态地获取各层中与h t m l 页面内容具体描述密切相关的信息识别模式知识，并最终利 用所获得的多层信息识别模式知识，完成相应的各个h t m l 网页的具体信息抽取工作。 近年来，信息抽取技术的研究与应用更为活跃。在研究方面，主要侧重于利用机器学习技 术增强系统的可移植能力、探索深层理解技术、篇章分析技术、多语言文本处理能力、信息抽 取对时间信息的处理等等；在应用方面，信息抽取应用的领域更加广泛，除自成系统以外，还 往往与其他文档处理技术结合建立功能强大的信息服务系统。 1 3 研究对象和研究模型 随着w e b 技术的发展，目前很多w e b 页面都是动态生成的，预先定义一些模版，然后根 据不同用户的不同需求，从预先定义好的数据库中查询数据，将数据填充到模版，然后显示给 用户，供用户查询使用。把表示一条完整的数据信息的数据集合叫做一条数据记录，如图1 1 ( a ) 所示，关于南京玄武饭店的所有数据组成一条数据记录。组成数据记录的每一个数据n l j 做 一个数据属性，每条数据记录由多个数据属性组成，在图1 1 ( a ) 中房型、门市价等都是数据 属性。前述的每个页面都包含很多条数据记录，并且这些数据记录分布在相似的数据区域内， 称这种页面为数据导向型页面。这种页面动态生成、便于更新，符合现代信息发展的趋势，必 将有广阔的前景，如何从这种页面中抽取信息( 数据记录) 是未来w e b 信息抽取技术研究的重 点。 i n t e m e t 上的信息供不同的组织拥有，同一种信息可能会由成千上万个网站发布，如图1 1 中的( a ) 和( b ) 所示，都是发布南京酒店信息，但是信息的表达格式及顺序大不一样。这样 就无法用一个统一的工具来处理这两种网页上的信息。为了能够使用统一的工具处理不同网页 上的相同信息，就要采取一定的方法，将其中的数据抽取出来按照统一的格式进行存储，为以 后的应用带来方便。 综合以上两点考虑，本文提出了一种新的基于树结构的数据记录的抽取方法以完成对数据 导向型页面的信息抽取。 3 基_ 丁树结构的w e b 信息抽取技术研究 4 一 南京酒店百嚣一群帮。蒜1 趣多黑飘慧戮瓣慧裟冀鬈篡纂盖一跏 q 蠢看方式：r 湎面面订商业区地圉 电子地霞哑 j k 住b m ：2 0 1 0 - 1 - i 譬店日期：2 0 1 0 - 1 - 8 共l 寞 n 捧序方式：( 一携程推番_ ) 价格疆店星镊客户评分 共娜京疆店 i 1 1 4 页；圭曩一【：! = 苎： j ! c 舀酒店实景田 ：一一+ j j 6 i ，4 1 查看点评 ( 8 3 0 点评) 一携程用户评鳋 帚覃母咿 z 卜 。一一一j 墨南京玄武响苣台 南京玄茜嘲吉座落于觥秀丽的玄武湖畔t 邻全瞒名的。灌麟商业一量街。变逼十分便利撇国际金 议展览中心仅1 0 分钟车程- 紧部地铁站- 是您商务敏彳亍的上佳之墟 e r a 业e 裁搂地区q 电子地宙 ， 罄囊鬻i 雳蠢磷霸瑟滞落嚣菇势礓鲫搿赣募确嚼篁确! 纛确。；4 毓疑硼 特竹房 柚抽橹姗5 4 8无早 对双收费警翻 囹黼节舯姗m 嘴辑犬用姻豳 豪华市粕尊舯艄 蛐瑚 簟草 棚姻匿幽 一 ，o ；二r ：j j 。，： j i ，。，：1 ，”+ 。1 ：- ： 芷酒店雾景圉 葛南京中心大蒋店 南京中心戈浯店位于南京市最繁华的商业中心一一新街口，地理位置绝佳交通极为方便捆店舞食莓摹周圈宵 物中心、金疑机构，夜总合集中实为商r 莠散害的绝隹选择 ； o 商业区：新街口地区市中o ，囝电子地图 i ， | ：f 、过轨素o - 二，；i 矗，。，。蠢，z ： ：一。：；， ( a ) 数据导向帮页面示例1 赢宁蠢寅培 点击蠢看嚆詹洋 j 一_ 。一一 ! 豪来兰爱日大曩鹰 i 一 ( b ) 数据导向型页面示例2 图1 1 数据导向型页面举例 图1 2 本文的研究原型 其中，网页预处理模块主要是清除原始h t m l 文档中不严格的语法结构，使其成为语法结 构严格的x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 形式，具体到本文是x h t m l ( e x t e n s i b l eh y p e r t e x tm a r k u pl a n g u a g e ) 形式，为接下来的d o m 树生成及信息抽取提供便利，这部分本文提出 了一种基于二叉树的h t m l 文件到x m l ( x h t m l ) 文件的转换方法 数据记录定位模块，本文通过三级( 主要内容区，数据区域，数据记录) 定位的方式定位 到所要抽取的数据记录，在定位数据记录的过程中本文改进了树的匹配算法及其他一些算法。 数据属性抽取模块，在定位到数据记录的基础上，通过数据记录的数据属性的对齐把数据 记录抽取出来，在此部分本文提出了一种基于聚类和树的比对的数据属性对齐算法。 通过x m l ( x h t m l ) 文件建立d o m 树称为x m l 文件解析模块，因为这部分技术比较 成熟，得到了格式标准的x m l 文件，利用现成工具h t m lp a r r 1 1 0 1 即可得到结构良好的d o m 树，故本文对此模块不再介绍。 1 4 本文的研究内容及组织 本文主要对w e b 信息抽取技术进行研究，首先阐述了w e b 信息抽取技术的研究现状及其 存在的问题，然后在学习前人研究成果的基础上提出了一种新的基于树结构的w e b 信息抽取方 法围绕该方法提出了一种基于二叉树的h t m l 到x m l 的转换方法；提出了一种分三步进行 的w e b 信息抽取中数据记录的定位方法；提出了一种基于聚类和树的比对的w e b 信息抽取中 数据属性的对齐方法。具体内容及组织如下： 5 基于树结构的w e b 信息抽取技术研究 第一章：绪论。介绍了w e b 信息抽取技术的研究背景、意义和国内外研究现状，说明了本 文的研究对象和研究模型，最后给出了本文的主要内容与组织。 第二章：w e b 信息抽取技术。详细阐述了w e b 信息抽取技术的原理、现有技术及其分类、 现有技术存在的问题，最后给出了信息抽取的评价指标。 第三章：基于二叉树的h t m l 到x m l 的转换方法。从h t m l 文件到x m l 文件的转换作 为w e b 信息抽取技术的预处理模块，对w e b 信息抽取的效果有着决定性的作用，本章在分析 前人研究的基础上，提出了一种效果更好的基于二叉树的h t m l 到x m l 的转换方法，并通过 实验证明此方法是可行有效的。 第四章：w e b 信息抽取中的数据记录定位。在抽取w e b 数据记录之前需要先定位w e b 数 据记录，本章结合树的编辑距离和树的相似度匹配技术等技术，提出了一种新的数据记录定位 方法，改进了树的相似度匹配算法，并通过实验证明这种方法的优越性。 第五章：w e b 信息抽取中的数据属性对齐和抽取。根据前面定位到的数据记录，对数据记 录进行抽取。本章提出了一种基于聚类和树的比对的数据属性对齐方法，该方法能够输出数据 属性，并总结出数据模式。最后通过实验证明了此方法的高效性。 第六章：总结与展望。总结全文，并对未来的工作进行展望。 6 一 r l 一 抽取原理两个不同的角度阐述现有的w e b 信息抽取技术，并经过分析现有的w e b 信息抽取技 术，发现现有w e b 信息抽取技术中存在的问题；最后为了更好地衡量本文提出方法的性能，本 章给出信息抽取系统的评价标准。 ：2 1w ，e b 信息抽取技术的概念 二 信息抽取技术是近十几年来发展起来的新领域，起源于文本理解，是自然语言处理领域特 二 别有用的一个子领域。信息抽取( i n f o r m a t i o ne x t r a c t i o n ，i e ) 是把文本里包含的信息进行结构 化处理，变成表格一样的组织形式。输入信息抽取系统的是原始文本，输出的是固定格式的信 息点。信息点从各种各样的文档中被抽取出来，然后以统一的形式集成在一起，这就是信息抽 取的主要任务。 w e b 信息抽取技术是在传统信息抽取技术的基础上进行的进一步研究。其核心就是从w e b 页面所包含的无结构或半结构的信息中识别用户感兴趣的数据，并将其转化为更为结构化、语 义更为消晰的格式，为用户在w e b 中查询数据，应用程序利用w e b 中的数据提供便利。在i n t e m e t 上，同一主题的信息通常分散在不同的网站上，表现形式也各不相同，若能将这些信息收集在 一起，然后结构化地储存起来，那将是非常有用的。由于网页上的信息载体主要是文本，所以， w e b 信息抽取技术对于那些把因特网当成是知识来源的人来说是至关重要的。信息抽取系统可 以看作是把不同文档中存放的信息转换成数据库记录的系统。因此，成功的w e b 信息抽取系统 可以把互联网变成巨大的数据库。 传统方式下，信息抽取是通过被称作“包装器”的程序来实现的。随着需求的增加，近来 涌现出了许多信息抽取工具，采用的技术也各不相同，涉及多个领域，如数据库、人工智能、 机器学习等等。 2 2 信息抽取与信息检索 与信息抽取密切相关的研究方向是信息检索1 ( i n f o r m a t i o nr e t r i e v a l ，i r ) ，两者既相互联 系又存在相当大的差异。 信息抽取与信息检索是相互补充的，为了处理海量文本，信息抽取系统往往以信息检索系 统的输出作为输入；而信息抽取系统又可以用来提高信息检索系统的性能，两者的结合能够更 7 基于树结构的w e b 信息抽取技术研究 好地服务于用户的信息处理需求。当然两者也存在着一定的差异，主要体现于以下儿个方面： ( 1 ) 处理技术不同。信息检索通常利用关键词、统计等技术，把文本看成词的集合，不需 要对文本进行理解；而信息抽取往往要借助自然语言处理技术，通过对文本中的句子以及篇章 进行处理后才能完成。 ( 2 ) 适用领域不同。由于采用不同的技术，信息检索一般是与领域无关的，而信息抽取是 与领域相关的。 ( 3 ) 功能不同。信息抽取旨在从文本中获取用户感兴趣的信息：信息检索则是从文本中找 到与用户需求相关的文档列表。信息检索只能找到与关键字匹配的文档子集，给出的是关键字 和链接，用户需要通过链接浏览这些返回的文档才可以得到详细的信息；与之不同的是，信息 抽取得到的是感兴趣的信息。信息检索的结果不够准确，许多不是用户想要的信息，而信息抽 取的结果更为准确。 2 3 现有w r e b 信息抽取技术的分类 w e b 信息抽取技术可以从多个角度1 2 1 进行分类。下面本节分别对根据自动化程度和抽取原 理的不同进行的分类展开讨论。 2 3 1 根据自动化程度分类 根据自动化程度的不同信息抽取技术可以分为人：f 方式的信息抽取、半自动方式的信息抽 取和全自动方式的信息抽取。 ( 1 ) 人工方式的信息抽取。在这种方式下，用户通过使用通用编程语言或特别设计的语言 为每一个网站手工编制一个包装器。这样的系统有、4 一”1 等，采用这种方法需要用户有较高的 专业水平。 ( 2 ) 半自动方式的信息抽取。这种系统采用了机器学习、数据挖掘和概念建模等方式，在 一定程度上使得包装器的产生工作能够自动的进行，但是在这些技术中都需要由用户提供标示 样本，还要有一定的先验知识。具有代表性的系统是x w r a p 5 1 和s t a l k e r 4 1 等。 ( 3 ) 全自动方式的信息抽取。此方法只要输入相应的网页就能够进行分析和生成包装器， 并将数据从网页中抽取出来。具有代表性的系统是r o a d r u n n e r 3 1 和m d r l 6 1 等。 2 3 2 根据抽取原理分类 根据信息抽取原理的不同，信息抽取技术可以分为：基于自然语言处理的信息抽取、基于 包装器归纳的信息抽取、基于o n t o l o g y l l 5 1 的信息抽取、基于h t m l 的信息抽取、基于w e b 查 询的信息抽取和基于视觉特征的信息抽取等。 8 t - 南京航空航大人学硕士学位论文 2 3 2 1 基于自然语言处理的w e b 信息抽取技术 自然语言处理技术通常用于自由文本的信息抽取，需要经过的处理步骤包括：句法分析、 语义标注、专有对象识别和抽取规则获取。具体地说就是把文本分割成多个句子，对每一个句