（计算机软件与理论专业论文）deepweb环境下数据抽取及模式识别的研究.pdf

o 0 。毒 i ；-l，l】l1。，1，11 静， 0，11，、11 j j 1 b yl i uw e i s u p e r v i s o r ：p r o f e s s o rs h e nd e r o n g n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 l-i-i 5 54 jlll 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 ；亡厶 恧o 学位论文作者签名：友l 】为 日 期：溯、 、i 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ：一 半年0一年口一年半口两年口 学位论文作者签名：去p 匆 导师签名： 岢憎莩 签字日期： 加勺8 7 ，f 签字日期： 争彦、7 、j k，jr -i， 一r l 岁 东北大学硕士学位论文 摘要 d e e pw e b 环境下数据抽取及模式识别的研究 摘要 d e e pw e b 是指那些存储在w e b 数据库里、不能通过超链接访问而需要采用动态网 页技术访问的资源集合。随着w e b 数据库的不断增长，通过对d e e pw e b 的访问逐渐成 ，为获取信息的主要手段，能够自动地获取蕴含在d e e pw 曲中丰富的数据资源并对其进 、|行大规模集成显得尤为重要。 现有的d e e pw 曲数据源结构化数据抽取方法主要以数据为重点，对结构的重视还 不够，很多方法抽取的结果还是无结构或水平结构的。其次，d e e pw e b 数据源往往会 发生变化的，比如数据的过期失效、模式信息的改变、页面结构的调整，这些变化都影 响原有抽取方法的准确率，带来大量维护问题。此外，目前还没有成熟的方法，将各个 数据源中获取的数据整合。可见，这些问题都给d e e pw 曲数据源中结构化数据的抽取 带来了困难，本文针对这些问题做了深入研究，并提出了可行的解决方案。 本文提出了一套完整的数据抽取及模式识别解决方案，主要内容包括： 提出了一种有效的d o m 模型下基于聚类的数据抽取方法，结合d o m 结构信息与 可视化信息分析结果页面，并采用基于聚类方法实现响应页面中的数据抽取，在面对结 构复杂的数据和大量的噪声节点时，仍能够完整、准确的获得数据信息。 提出了一种基于标签的结果模式抽取方法，通过一种两阶段式的标签获取方法，同 步标签获取，对以往的标签获取方法做了很大的改进，一定程度的提高了获取标签的数 量与准确性。此外，采用了基于l c s 的模式标签匹配技术，提高了模式与标签之间的 匹配精度。 提出了一种简单有效的包装器模型，提高了数据抽取的时间效率。此外，还对包装 o 、器的集成问题进行了深入的研究，解决了由d e e pw 曲数据源更新造成的包装器维护问 1 咫。 ：经过实验验证，本文提出的数据抽取方法能够真正有效的抽取响应页面中的有用信 叠 息，并且在准确率和召回率方面都要优于现有方法，使得d e e pw 曲中丰富的高质量结 构化信息得到充分利用，具有很高的应用价值，可以广泛的应用到各类d e e pw e b 信息 集成中。 关键词：d e e pw e b ；页面解析；数据抽取；模式识别；包装器 一i i ，、誓、 f j 夸 东北大学硕士学位论文a b s t r a c t r e s e a r c ho nd a t ae x t r a c t i o na n ds c h e m a r e c o g n i t i o n o nd e e pw e b a b s t r a c t d e e pw e b r e f e r st od a t as o u r c e st h a ta r es t o r e di nd a t a b a s e sa n dc a l ln o tb ea c c e s s e db y h y p e r - l i n k sb u to n l yb yd y n a m i cw e bp a g ea c c e s s i n g a st h ei n c r e a s eo fw e bd a t a b a s e s ， a c c e s s i n gd e e pw e bf o ri n f o r m a t i o ng r a d u a l l yb e c o m e st h em a i nm e t h o dt oa c q u i r e i n f o r m a t i o n ，f o rw h i c ha u t o m a t i ca c q u i r i n gd e e pw e bd a t as o u r c e sf o rl a r g es c a l ei n t e g r a t i o n i se v e nt h em o r ei m p o r t a n t t h ee x i s t i n gd a t ae x t r a c t i o na p p r o a c h e so nd e e pw e bf o c u so nd a t ar a t h e rt h a ns t r u c t u r e , w h i c hd o n tc a r er e s u l ts c h e m a a n dm a n ym e t h o d sa r en o ta b l et op r o c e s sc o m p l e xd a t a i n a d d i t i o n ，t h ed e e pw e bd a t as o u r c e st e n dt oc h a n g e ，s u c ha st h ec h a n g e so fp a g es t r u c t u r ea n d r e s u l ts c h e m a , w h i c hw i l la f f e c tt h ea c c u r a c yo fo r i g i n a le x t r a c t i o nm e t h o d s t h e s ei s s u e s b r i n gal a r g en u m b e ro f d i f f i c u l t i e st od a t ae x t r a c t i o nw h i c hi sm a i n l yd i s c u s s e di nt h i sp a p e r t or e s o l v et h e s ep r o b l e m s ，ac o m p l e t ea n de f f e c t i v em e t h o ds u p p o r t i n gd a t ae x t r a c t i o n a n ds c h e m ar e c o g n i t i o ni sp r o p o s e di nt h i sp a p e r t h ec o n t e n ti n c l u d e s ： t oe x t r a c td a t a , an o v e la l g o r i t h mb a s e do nc l u s t e r i n gi sa d o p t e d ，w h i c hc o m b i n eb o t h d o ms t r u c t u r ei n f o r m a t i o na n dv i s u a li n f o n 】& a t i o n i ti sa l s oe f f e c t i v ew h e nf a c e dc o m p l e x d a t aa n dn o i s e i na d d i t i o n ，as c h e m ar e c o g n i t i o nm e t h o db a s e do nl a b e l i n gi sp r o p o s e d ，w h i c ha d o p t s 2 - p h a s el a b e la s s i g n m e n ta n dl a b e lm a t c h i n gb a s e do nl c st oi n c r e a s et h ep r e c i s i o n f i n a l l y , as i m p l ee x t r a c t i o nr u l em o d e li sd e f i n e dt od e c r e a s et h et i m ec o s ti fd a t a e x t r a c t i o na n dr e s o l v et h ep r o b l e mo fm a i n t e n a n c e t h ee x p e r i m e n t sh a v es h o w nt h a tt h em e t h o d sw ep r o p o s e dh a v eg o o dp e r f o r m a n c eo n p r e c i s i o na n dr e c a l l i tc a ns o l v et h ed a t ae x t r a c t i o na n ds c h e m ar e c o g n i t i o np r o b l e m ，a n d v e st h e o r e t i c a ls u p p o r tf o rd a t ai n t e g r a t i o no nd e e pw e ba sw e l l k e y w o r d s ：d e e pw e b ；p a g ep a r s i n g ；d a t ae x t r a c t i o n ；s c h e m ar e c o g n i t i o n ；w r a p p e r i i i x tlfp，。 、 ， f 一10，、 0 i；，。 l j 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t 。i i i 第1 章引言1 1 1 课题背景1 1 2 国内外研究现状。2 1 3 本文研究的内容6 1 。4 本文研究思路及组织结构6 第2 章相关概念与技术9 2 1w e b 相关技术9 2 1 1h t m l 1 0 2 1 2x m l 1 1 2 1 3d o m 1 2 2 1 4j a v a s c r i p t 1 3 2 2 、7 i 厂e b 2 0 一1 4 2 3 搜索引擎15 2 4 本章小结1 8 第3 章d w s e a r c h 中预处理子系统的设计1 9 3 1 基本需求1 9 3 2d w s e a r e h 体系结构2 0 3 3 预处理子系统的设计2 2 3 4 本章小结2 5 第4 章d o m 模型下基于聚类的数据抽取2 7 4 。：建立d o m 模型2 9 4 2 基于聚类的识别数据区节点算法3 1 4 3 识别数据记录3 4 4 4 比对分析3 5 4 5 属性分离3 8 4 6 本章小结3 8 第5 章基于标签的结果模式识别及包装器的构造3 9 5 1 建立数据源实例库4 0 5 2 本地标签获取4 0 5 3 全局标签获取4 2 一一 东北大学硕士学位论文目录 5 4 模式标签字典4 3 5 5 基于l c s 的模式标签匹配4 3 5 6 包装器的生成。4 5 5 6 1 包装器模型4 6 5 6 2 包装器的集成4 6 5 7 本章小结4 6 第6 章实验与分析4 9 6 1 实验设置4 9 6 2 实验结果及分析5 0 6 3 本章小结5 4 第7 章结论5 7 7 1 本文的主要贡献与结论5 7 7 2 进一步的工作：5 8 参考文献5 9 致谢6 4 攻硕期间参加的项目及发表的论文6 5 一v 一 气 东北大学硕士学位论文第1 章引言 第1 章引言 1 1 课题背景 i n t e m e t 是世界上规模最大、用户最多、影响最广的一个全球化的、开放性的互联 网络，它蕴藏着丰富的信息资源，为人们工作、生活带来了许多方便。随着w o r l dw i d e w e b 的飞速发展，其中蕴含了海量的信息可供我们利用。根据文献最新的调查，目前整 个w e b 超过了2 0 0 ，0 0 0 t b 的信息量，而且仍在快速的增长。然而，虽然w e b 上的信 息量大而丰富，但真正被应用的却很少，尤其是结构化的信息。 w e b 上的信息可分为：s u r f a c ew e b 和d e e pw e b 。s u r f a c ew e b 是指可以通过超链接 被传统的搜索引擎索引到的页面的集合；而d e e pw 曲是指w e b 中不能被传统的搜索引 擎索引到的那部分内容，只能通过查询接口动态提交查询来访问w e b 中的内容。2 0 0 0 年7 月，b r i g h t p l a n e t 对d e e pw e b 从宏观上做了统计调查【1 1 ，结果表明： ( 1 ) d e e pw e b 蕴含的信息量是s u r f a c ew e b 的4 0 0 5 5 0 倍； ( 2 ) 对d e e pw e b 的访问量比s u r f a c ew e b 要高出1 5 ； ( 3 ) d e e pw 曲蕴含的信息量比s u r f a c ew e b 的质量高出10 0 0 2 0 0 0 倍； ( 4 ) d e e pw e b 的增长速度要远大于s u r f a c ew e b ； ( 5 ) d e e p w 曲上的内容主要是主题相关的，即面向某个特定领域； ( 6 ) 整个d e e pw e b 覆盖了现实世界的各个领域，如商业、教育、政府等； ( 7 ) d e e pw e b 上9 5 的信息是可以公开访问的，且是免费获取。 2 0 0 4 年4 月，u i u c 大学对i n t e m e t 上有效的i p 地址空间中随机选取不重复的1 0 0 万个口地址进行实验，实验表明，w e b 数据库网站的数目比2 0 0 0 年增长了6 倍多。据 2 剃年统计 2 1 ，w 曲上有3 3 0 0 0 0 个在线数据库，而到2 0 0 4 年，w 曲上已有4 5 0 0 0 0 个 f 3 1 。并且该规律依然存在嗍，每年还在成倍地增加。 然而，目前w e b 上的信息获取还主要基于g o o g l e 、y a h o o 、百度等搜索引擎，为人 们提供导航的信息。而对于w e b 上深层的数据库知识，虽然我们可以通过逐一点击的 方式获取需要的信息，但需要人们繁琐的信息收集过程，给人们带来许多不便。尽管如 此，用户得到的还是零散的、不完备的且非系统的信息。例如：用户希望查询有关“数 据库”的书籍。通常人们采用两种搜寻策略，一是直接输入关键字“数据库”和“书”信息， 或是先查“网上书店的网址”，进而在相应的网站查询有关数据库的书。不论那种方法， 东北大学硕士学位论文第1 章引言 提供给用户的都是一系列推荐的u r l 地址，需要用户进一步选择点击，才能获得相关 的信息。可见，要想获得集成的信息，需要用户自己整理来自于多个网址的信息，很繁 杂。因此，人们希望w e b 能替代人智能地访问深层w e b 的数据库资源，并能按需为用 户提供系列的集成数据。如上例，智能完成如下过程：首先发现w e b 上所有有关图书 的深层数据库资源，之后查询出所有有关数据库方面的图书信息，最后，将集成结果提 供给用户。用户可一目了然了解自己需要的信息知识。 对d e e pw e b 中信息的获取主要的途径是对网站中所提供的查询接口提交查询，并 从响应页面中来获得用户感兴趣的内容，可见，在d e e pw e b 数据集成中，对响应页面 内容的分析并抽取出有用信息具有十分重要的意义。而用户所感兴趣的信息往往是那些 结构化的信息，信息中包含若干个属性，比如查询一本图书，查询结果中可能会包含书 名、作者、价格、出版社、i s b n 等属性。这些属性就构成了响应页面的模式信息，也 称为结果模式，对结果模式信息的研究具有极其重要的意义。 在w e b 领域的研究目的在于发展新的技术可以有效地从w e b 中获取有用的信息。 w e b 中的信息主要通过网页的形式对外发布，由不同的个人或群体开发，形式与内容有 很大的差异。正是由于这个原因，使得自动地从中获取有价值的信息和数据变成一件十 分具有挑战性的任务。 现有的深层w e b 数据源结构化数据抽取方法主要以数据为重点，对结构的重视还 不够，很多方法抽取的结果还是无结构或水平结构的。其次，深层w 曲数据源往往会 发生变化的，比如数据的过期失效、模式信息的改变、页面结构的调整，这些变化都影 响原有抽取方法的准确率，带来大量维护问题。此外，目前还没有成熟的方法，将各个 数据源中获取的数据整合。可见，这些问题都给深层w e b 数据源中结构化数据的抽取 带来了困难，给数据处理研究者们提出了新的挑战。 b 1 2 国内外研究现状 随着w o r l dw i d ew e b 的飞速发展，其中蕴含了海量的信息可供我们利用。根据最 新的调查，目前整个w e b 超过了2 0 0 ，0 0 0 t b 的信息量，而且仍在快速的增长。在w e b 领域的研究目的在于发展新的技术可以有效地从w 曲中获取有用的信息。w e b 中的信 息主要通过网页的形式对外发布，而由文本和超链接构成的网页有其独特之处：数量惊 人，信息丰富；由不同的个人或群体开发，形式与内容有很大的差异；分布在地球上 i n t e r n e t 连接的每一个角落，这就造成了w 曲数据的异质性和缺乏结构性。正是由于这 一2 一 东北大学硕士学位论文第1 章引言 个原因，使得自动地从中获取有价值的信息和数据变成一件十分具有挑战性的任务。 目前，对d e e pw 曲的研究越来越受到关注。b r i g h t p l a n e t 在2 0 0 0 年7 月对d e e pw e b 做了一次较为全面的宏观统计，并发布了d e e pw r e b 白皮书【l 】；u i u c 在2 0 0 4 年大学对 i n t e r n e t 上有效的i p 地址空间中随机选取不重复的1 0 0 万个m 地址进行实验 2 1 ，实验表 明，w e b 数据库网站的数目比2 0 0 0 年增长了6 倍多【3 】。 目前，有关d e e pw e b 数据集成的研究还处于初级阶段，研究的内容主要包括d e e p w e b 数据源的发现，查询接口的模式抽取，d e e pw e b 数据源的分类，d e e pw e b 数据源 的选择，查询结果的抽取。至今在对查询结果处理这一研究方向中，各个研究问题发展 很不平衡。从页面中抽取数据已经有了很多较成熟方法，各种技术方法被提出从理论和 应用中解决这个问题。相对来说，其它的研究问题，比如数据的语义添加、数据合并等， 还处于空白阶段或刚刚开始被研究者们关注，但作为d e e pw e b 数据集成系统不可缺少 的组成部分，需要研究者们在这些研究问题上给予更多关注与努力。 针对本文的研究内容，国内外相关工作介绍如下。 ，； ( 1 ) d e e pw e b 数据源查询接e l 模式抽取技术 对于查询接e l 的分析和处理问题，美国的u i u c 做了深入的研究，研究主要是围绕着 专 m e t a q u e r i e r 项目展开的。其中，文献【4 叫提出了以文法分析的方式来完成对查询接口模 式的抽取。对于整个页面结构的分析已经有了较为细致的工作，如文献【7 。13 1 ，但针对查 询接口结构的分析该工作属于开创。这种方法首先通过观察与统计提出了这样一个假 设：所有查询接口都是由隐藏的文法构建而成。为了能够准确地从一个具体的查询接口 中将表示属性的各个元素组合方式识别出来，该工作通过构建解析树对整个查询接口进 行解释，确定它们的语义，把查询接口中的属性尽可能的发现出来了，但还不能完全达 到实际应用的程度。 oj 另外，文献【1 6 】提出了较为完备一种形式化的表达方式，首先整个查询接口表示一个 三元组，包括查询接口所在网站的相关信息、属性的集合，由属性形成查询条件之间的 关系，比如连接、非连接、排斥等。属性集合是对每个属性信息的描述，每个属性表示 为一个七元组，包括属性的名称，属性在查询接口中的布局位置，属性的域类型，属性 的缺省值，属性的值的类型，属性值的单位。 ( 2 ) d e e pw e b 数据源结构化数据抽取技术 随着d e e pw e b 数据源数量的增加，其重要性日趋突现。这些数据源中蕴含了大量 的高质量结构化信息，并且还在迅速增长【1 7 1 引。然而，这些数据源必须通过其查询接口 一3 一 东北大学硕士学位论文第1 章引言 访问，最终返回一系列包含大量半结构化信息的w e b 页面，如何自动的、准确的获取【1 9 】 这些信息就因而提出。 早期的数据抽取方法大都为手工或半自动 2 0 - 2 6 】，即需要人为分析页面特征及文档结 构或人为提供必要的模式信息等，以完成对结构化信息的识别及抽取，如x w r a p 2 0 1 、 s g w r a p 2 2 和d e b y e 2 5 1 。 x w r a p 有一个组件库，它是提供抽取规则生成的基本模块，这个工具引导用户通 过一系列的步骤，选择每步中正确的组件。最后，x w r a p 输出特定源上的一个抽取 规则。在对象抽取这步中，为h t m l 页面预定义了六个启发式，用户可以使用其中的启 发式定位感兴趣的数据对象。用户也可以为了使抽取结果更符合自己的要求限制或放宽 每个对象的组件数目或指定数据类型。 d e b y e 是一种交互工具，把简单页面的样本对象集合作为输入，产生能够从其它 类似页面抽取新对象的抽取模式。s g w r a p 这种方法是一种预定义模式引导的数据抽 取方式，通过图形化的界面把在样本页面中要抽取的数据与预定义的模式进行连接匹 配，通过这种操作产生抽取规则，完成对同类页面的有效抽取。 随着各方面技术的成熟，手动或半自动的数据抽取方法已经不能满足要求，无法应 用到大规模的d e e p w e b 数据集成系统中，这又为d e e p w 曲研究者们提出了新的挑战。 近年来，越来越多的全自动方法被提出2 7 3 3 1 ，即不需要人工的干预就能自动完成包 装器的生成或数据的抽取，其中大部分是基于d o mt r e e 模型对网页进行抽取的。 较为典型的方法有r o a d r u n n e r 3 4 】 3 5 1 、l i x t o 3 6 1 3 7 1 、m d r 3 8 1 、m d r i i 3 9 1 、v i d r e 4 0 和e x a l g 4 1 】等。 m d r 和m d r i i 这两种抽取方法都是由美国i l l i n o i s 大学同一研究小组提出，它们 都是基于d o mt r e e 结构特征，完成对多记录页面的抽取。它们的实现关键在于利用页 面的嵌套结构和表现特征把查询结果从整个页面中分离出来，并将结果中的多个记录从 中彼此精确的划分，其意义是把每个记录作为现实世界的实体对待，首先从这个角度完 成第一步抽取，第二步把每一条记录从属性的角度进行分解。m d r 把标签树中节点的 路径看作一个字符串，并使用了比较字符串编辑距离的思想从数据区中发现代表数据记 录的结点，而m d r i i 则是以树的结构信息代替标签字符串，从而达到对数据记录更准 确的识别结果。但是，对于d o m 结构简单的页面，它可以得到很好的效果，如果页面 d o mt r e e 中结构复杂，数据区内噪声节点过多，它并不能很好的处理，另外，它还不 能支持嵌套结构的数据。 - - - 4 - 东北大学硕士学位论文第1 章引言 v i d r e 是一种基于可视化特征的抽取方法，在某种程度上模拟人眼对页面的识别过 程，最终达到识别对象信息的目的。这个方法十分新颖，但是需要建立一个有效的可视 化模型，因此，在效率上要比直接分析页面文档低一些，此外，完全依赖可视化信息显 得并不可靠，当页面没有明显的视觉特征时，抽取就会变得很困难。 r o a d r u n n e r 是一个包装器归纳系统，其方法是进一步发掘h t m l 文档内在的特征， 通过对比样本页面间的异同来生成抽取规则。为了准确的捕获在样本页面所有可能的结 构变量，必须提供多于两个的样本页面。所有的抽取过程都基于这样一个算法，比较样 本页面的标签结构产生规则的表达式来处理结构之间不匹配的情况。r o a d r u n n e r 可以 分析出模式中的可选属性和嵌套属性( 可以在一条记录中重复出现多次属性) ，而且它 对模式的推导时间复杂性是指数量级，因此在大量样本页面的情况下代价过高。 e x a l g 是s t a n f o r d 大学的研究小组提出的，它与r o a d r u n n e r 的原理相似，并解决 了时间代价的问题，但它们试图归纳页面生成模板，当网站更新时，页面结构会发生变 化，原有的模板不再有效，因此，它们不能很好的解决维护问题。 现有的深层w e b 数据源结构化数据抽取方法主要以数据为重点，对结构的重视还 不够，很多方法抽取的结果还是无结构或水平结构的。其次，深层w e b 数据源往往会 发生变化的，比如数据的过期失效、模式信息的改变、页面结构的调整，这些变化都影 响原有抽取方法的准确率，带来大量维护问题。此外，目前还没有成熟的方法，将各个 数据源中获取的数据整合。可见，这些问题都给深层w e b 数据源中结构化数据的抽取 带来了困难，给数据处理研究者们提出了新的挑战。 ( 3 ) d e e pw e b 数据源结构化数据模式识别技术 为了使从页面中抽取到的数据具有使用价值，必须要为其添加语义注释，而目前在 这方面的工作还在初步阶段，都是以启发式规则的方式对抽取到的数据进行语义注释， 如d e l a ，不仅准确性还未达到实际应用的标准，而且更重要的是不能对抽取到的全部 数据添加语义注秽4 2 1 。另外，现有的方法都没有考虑到d e e pw e b 数据集成的环境，忽 视了各个数据源之间的模式匹配关系，这给最终的查询结果集成带来了很大的困难。 d c l a 4 3 】采用了t o k e ns u f f i x t r e e 数据结构来处理数据抽取问题，并对所抽取数据的 语义进行分析，为每列数据分配一个标签，但它对数据语义的分析还不够深入，并不能 得到一个真正的模式信息。 ( 4 ) 国内相关研究 d e e pw e b 在国内的研究工作还不是非常成熟，但其也越来越受关注。有关网页信 一5 一 ， l， 擘 ，一。 、 东北大学硕士学位论文第1 章引言 息抽取的研究工作主要有清华大学与微软亚洲研究院合作提出的h c r f 模型【删，其中使 用概率模型将抽取w e b 页面数据与属性相结合。微软亚洲研究院的相关工作主要针对 面向对象的垂直搜索【4 5 1 ，其中的对象抽取技术使用一种基于条件随机场的机器学习方 法。中国人民大学的国家自然科学基金“w e b 数据抽取与集成技术研究”中采用基于视 觉信息的方法从w e b 页面中提取数据信息蛔，典型的研究成果有d e e pw 曲数据集成中 的实体识别方法和d e e pw 曲数据集成问题研究【4 7 5 2 】。 1 3 本文研究的内容 随着d e e pw e b 数据源数量的不断增长，d e e pw e b 环境下的数据集成技术就显得更 为重要。这些数据源中蕴含了大量的高质量结构化信息，并且数量还在迅速的增长。然 而，这类数据源只能通过其查询结构访问，并将包含结果数据的响应页面返回给用户， 因此，如何准确、自动的抽取结果数据逐渐成为讨论的热点。 现有的深层w e b 数据源结构化数据抽取方法主要以数据为重点，对结构的重视还 不够，很多方法抽取的结果还是无结构或水平结构的。其次，深层w e b 数据源往往会 发生变化的，比如数据的过期失效、模式信息的改变、页面结构的调整，这些变化都影 响原有抽取方法的准确率，带来大量维护问题。此外，目前还没有成熟的方法，将各个 数据源中获取的数据整合。可见，这些问题都给深层w e b 数据源中结构化数据的抽取 带来了困难，给数据处理研究者们提出了新的挑战。 针对d e e pw e b 上数据抽取的研究现状，本文提出了一个完整的数据抽取解决方案， 采用结构信息与可视化信息相结合的方式，在面对结构复杂的数据和大量的噪声节点 时，仍能够完整、准确的获得数据信息，还对结果模式进行了更深入的探索。 1 4 本文研究思路及组织结构 本文其它章节内容的结构安排如下： 第二章主要介绍相关的w e b 技术，包括h t m l 、x m l 、d o m 等，介绍了当今搜索 引擎的发展状况。 第三章主要概述了整个系统的设计框架，及各个子系统相应的功能。主要包括预处 理子系统、查询子系统、缓存子系统。其中，预处理子系统是本文的重点工作，也是整 个系统的核心部分。 第四章主要介绍d o m 模型下基于聚类的响应页面数据抽取方法。主要包括d o m 模型建立、数据区识别、数据记录识别、比对分析和属性分离。 一6 一 东北大学硕士学位论文第1 章引言 第五章主要介绍基于标签的结果模式抽取方法及包装器的构造。主要包括数据源实 例库的建立、本地标签获取、全局标签获取和基于l c s 的模式标签匹配算法。提出了 一种简单的包装器模型，对包装器的描述与生成做了简单的介绍，此外，还探讨了包装 器的维护问题。 第六章通过实验和测试，对前两章提出的d e e pw e b 环境下的数据抽取和模式识别 方法的性能，从准确率和召回率方面做了了评价，并且，对包装器模型的时间效率做了 深入的分析。 第七章对本文的工作进行总结，并提出有待进一步研究和改善的问题。 一7 一 查! ! 查堂塑主堂堡垒查第1 章引言 。一- 一 ： 一8 一 一 毒 ， f 东北大学硕士学位论文第2 章相关概念与技术 第2 章相关概念与技术 本章将介绍与本文所提出的系统相关的一些概念，其中包括w e b 相关的概念，以 及传统搜索引擎的发展现状。 2 1w - e b 相关技术 w e b 技术是建立在c s 模型之上，以h t m l 和h t t p 为基础，能够提供面向各种 i n t e r n e t 服务的且用户界面一致的信息浏览系统，把所有i n t e r n e t 上现有资源全部连接， 采用图形界面的、融网络技术、超文本技术以及多媒体技术为一体的信息服务系统。 w e b 技术结构如图2 1 所示。系统具有如下特点： ( 1 ) 以超文本组织网络多媒体信息； ( 2 ) 用户可在世界范围内任意查找、检索、浏览及添加信息： ( 3 ) 提供生动、直观、易于使用和格式统一的图形用户界面； ( 4 ) 网点之间可以相互链接，以提供信息查找和漫游的透明访问； ( 5 ) 具有集成各种最新信息技术和多种文件格式的能力。 图2 1w e b 体系结构 f i g 2 1t h es t r u c t u r eo f w e b w o r l dw i d ew e b ，简称w w w ，是英国人t i m b e r n e r s l e e l9 8 9 年在欧洲共同体的一 个大型科研机构任职时发明的。通过w e b ，互联网上的资源可以在一个网页里比较直观 的表示出来，而且资源之间可以在网页上相互链接。与w w w 有关的协议如下： ( 1 ) u r l ：统一资源定位器 a ) 用于唯一标识w e b 资源 b ) 格式：协议：主机名 标识符 ( 2 ) h t t p ：超文本传输协议 a ) 用来在i n t e r n e t 上传输文档的协议 ( 3 ) h t m l 超文本标记语言 一9 一 东北大学硕士学位论文 第2 章相关概念与技术 a ) 提供链接机制 b ) 关注页面布局，缺乏对结构化数据的表达能力 c ) x m l ( 4 ) c g h 公共网关接口 a ) 为w e b 服务器与外部应用程序建立桥梁，实现动态交互 2 1 1h t m l h t m l 是网页的通用语言，是本文研究的基础知识，这里将做简单介绍。 h t m l 的全称是超文本标记语言，官方的定义描述为“为了发布全球化的消息，人 们需要一种通用的礼节性语言，一种所有计算机本质上可以理解的发布母语。w w w 使用h t m l 作为这种发布语言”，它是目前w e b 上通用的描述语言，它用描述性的标记 符( 称为标记) 来指名文档的不同内容。标记是区分文本各个组成部分的分界符，用来 把h t m l 文档分成不同的逻辑结构，如段落、标题和表格等。 从结构上讲，h t m l 文件由元素( d e m e n t ) 组成，组成h t m l 文件的元素有许多种， 用于组织文件的内容和指导文件的输出格式，不同类型的元素分别描述文本、图像和超 文本链接等。绝大多数元素是“容器”，即它有起始标记和结尾标记。元素的起始标记叫 做起始链接签( s t a r tt a g ) ，元素结束标记叫做结尾链接签( e n dt a g ) ，在起始链接签和结尾 链接签中间的部分是元素体。每一个元素都有名称和可选择的属性，元素的名称和属性 都在起始链接签内标明。比如体元素( b o d y ) d e m o t h i si sm y f i r s th t m lf i l e 第一行是体元素的起始链接签，它标明体元素从此开始。第二行和第三行是体元素 的元素体，最后一行是体元素的结尾链接签，结尾链接签用 。 h t m l 标记一般有两个作用，首先是定义文档结构，以便浏览器显示该文档。其次 是提供各种路标，把w e b 客户搜索程序引导到该文档的关键区域。 h t m l 的标记间具有一定的嵌套结构，通过h t m l 解析器( p a r s e r ) 可以将h t m l 页 面转化为一棵d o m 树，在此基础上，可以利用d o m 接口完成多种操作。另一方面h t m l 不是结构化的，它的许多元素只具有显示效果( 如 ， ， 等标记) ，另外，文 件中经常夹杂着大段的脚本，( j a v a s c r i p t ，v b s c r i p t 等) 代码，这些代码完全是为了显示 一1o 一 东北大学硕士学位论文第2 章相关概念与技术 效果而增加的。 ，。 h t m l 实际上是普通的文档，没有图形，动画，声音等，但包含了指向这些类型文 件的“指针”，通常称为链接，这就使得w e b 页面包含了一些非文本因素。 正是由于有了这种通用语言，人们才可以在因特网上发布多种多样的资源，通过语 言可以做到如下几点： ( 1 ) 发布带有标题文本、表格、列表、照片等资源的网络文档； ( 2 ) 通过点击超文本链接来浏览网络文档； ( 3 ) 设计通过远程服务管理事务，比方说搜索信息、房间预定、产品订货等等； ( 4 ) 把分析表格、视频片断、声音片断和其它应用程序都直接包含在它们所在的文 档中。 h t m l 结构树是一个n 叉树，它的每一个节点对应页面中的一个h t m l 标记，树 中的父子关系意味着孩子结点的内容包含在父结点的范围之内。即： ( 1 ) 如果结点b 嵌套在结点a 之内，那么b 是a 的孩子结点。 ( 2 ) 否则，如果a 是b 最近的逻辑标题( 如h 1 ) ，那么b 是a 的孩子结点。 h t m l 结构树的构造可以直接利用h t m l 标记之间的嵌套关系。 2 1 2x 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 ，可扩展标记语言) 是由w 3 c 于1 9 9 8 年2 月发 布的一种元语言标准。它是一种通用的文档结构描述标记语言，具有很强的描述能力， 是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) 的简化子集。它 将s g m l 的丰富功能与h t m l 的易用性结合到w e b 的应用中，以一种开放的自我描述 方式定义了数据结构，在描述数据内容的同时能突出对结构的描述，从而体现出数据之 间的关系。 通过x m l 组织的数据对于应用程序和用户都是友好的、可操作的。其中应用程序 操作x m l 主要是通过d o m 和s a x 解析技术。 d o m ( d o c u m e n to b j e c tm o d e l ) 是处理x m l 数据的传统方法，使用d o m 时，数 据一次性被解析，并以树状结构的形式被加载到内存中，应用程序就根据树中上下导航 的方式从内存中直接存取数据。d o m 这种基于树的处理方式，可以把数据持久保存在 内存中，方便应用程序对x m l 文档的数据和结构进行修改，而且可以在任何时候通过 树中上下导航的方式从内存中直接存取数据。但是当x m l 文件较大的时候，构造d o m 东北大学硕士学位论文第2 章相关概念与技术 树会造成大量的内存开销，并且构造d o m 树也可能是一个缓慢的过程。 s a x ( s i m p l ea p if o rx m l ) 是一种基于事件的数据处理方式。这种处理方式类似 于流媒体的处理方式，分析能够立即开始，而不是等待所有的数据被处理后才分析数据； 而且，由于应用程序只是在读取数据时检查数据，因此不需要将数据存储在内存中。这 样可以节省内存开销，并且解析的速度也快。但是这种解析方式，应用程序没有以任何 方式存储数据，不可能使用s a x 来更改数据或在改变数据在数据流中的位置。 从上面对d o m 和s a x 两种解析技术的分析来看，它们各有优缺点，但针对系统 的具体情况，数据转换操作的触发时间是随机的，可能长时间内没有转换操作，同时， 如果大量的x m l 对象解析到