（计算机应用技术专业论文）基于标签树的列表页面数据抽取技术研究.pdf

d i s s e r t a t i o nf o rm a s t e rd e g r e e2 011 u n i v e r s i t yc o d e ：10 2 6 9 s t u d e n ti d ：5 1 0 8 1 2 1 1 0 0 3 e a s tc h i n an o r m a lu n i v e r s i r e s e a r c ho fd a t ae x t r a c t i o nt e c h n o l o g y b a s e do nt a gt r e ef r o ml i s tp a g e s d e p a r t m e n t ： m a j o r ：c o m p u t e ra p p l i c a t i o n & t e c h n o l o g y r e s e a r c hf i e l d ：翌选坠p p ! i 堡垒! i q 旦鱼! 量堡b 墼q ! q g y t u t o r ： c h e ns h a o - h o n ga s s o c i a t ep r o f e s s o r m a s t e rs t u d e n t ： i n gh 垒坠：蚤i 塾g c o m p l e t e d i na p r2 0 11 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文基于标签树的列表页面数据抽取技术研究， 是在华东师范大学攻读硕孟博士( 请勾选) 学位期问，在导师的指导下进行的研究工 作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均己在文中作了明确 说明并表示谢意。 作者签名：越日期v 1 年j 删日 华东师范大学学位论文著作权使用声明 基于标签树的列表页面数据抽取技术研究系本人在华东师范大学攻读学位期 间在导师指导下完成的硬彰博士( 请勾选) 学位论文，本论文的研究成果归华东师范 大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门 和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学 位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采 用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文木， 于年，月同解密，解密后适用一t - 述授权。 ( 、歹2 不保密，适用上述授权。 新签名立盟三二本人签名邋 l o l l 年s 月乃l 同 奉“涉密”学位论文廊是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此卢明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 o r i g i n a l i t yn o t i c e i np r e s e n t i n gt h i st h e s i si np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h em a s t e r sd e g r e ea te a s tc h i n an o r m a lu n i v e r s i t y , 1w a r r a n t t h a tt h i s t h e s i si so r i g i n a la n da n yo ft h et e c h n i q u e sp r e s e n t e di nt h et h e s i sh a v e b e e nf i g u r e do u tb ym e a n yo ft h er e f e r e n c e st ot h ec o p y r i g h t ，t r a d e m a r k ， p a t e n t ，s t a t u t o r yr i g h t ，o rp r o p r i e t yr i g h to fo t h e r sh a v eb e e ne x p l i c i t l y a c k n o w l e d g e da n di n c l u d e di nt h er e f e r e n c e ss e c t i o na tt h ee n do ft h i s t h e s i s a u t h o rs i g n a t u r e ： c o p y r i g h t n o t i c e d a t e ： 悯吾胁，砷f i ih e r e i na g r e et h a tt h el i b r a r yo fe c n us h a l lm a k ei t sc o p i e sf r e e l y a v a i l a b l ef o ri n s p e c t i o n if u r t h e ra g r e et h a te x t e n s i v ec o p y i n go ft h e t h e s i si sa l l o w a b l eo n l yf o rs c h o l a r l yp u r p o s e s ，i np a r t i c u l a r , s t o r i n gt h e c o n t e n to ft h i st h e s i si n t or e l e v a n td a t a b a s e s ，a sw e l la sc o m p i l i n ga n d p u b l i s h i n gt h et i t l ea n da b s t r a c to f t h i st h e s i s ，c o n s i s t e n tw i t h “f a i ru s e a s p r e s c r i b e di nt h ec o p y r i g h tl a w o ft h ep e o p l e sr e p u b l i co fc h i n a m 稍；刚啪：避衙s i 咖似堡芝堡 d a t e ：珥蛐 d a t e ：丛骂型壁! 旦i 量塞星硕士学位论文答辩委员会成员名单 姓名职称单位备注 郑骏教授华东师范大学信息学院主席 朱敏高级工程师华东师范大学信息学院 郭骏副教授华东师范大学信息学院 华东师范大学硕l 二学位论文 基于标签树的列表页面数据抽取技术研究 摘要 伴随i n t e m e t 的飞速发展，w e b 已经成为一个巨大的、共享的、分布式的信 息资源集合，如何从浩瀚的w e b 信息资源中自动获取用户感兴趣的数据记录或 有用的信息，已成为人们深入探讨的课题。目前，大多数w e b 数据都以非结构 或半结构化的形式呈现，缺乏对数据本身的描述，不包含清晰的语义，模式也不 太明确，这使得应用程序无法直接解析并利用w e b 上的海量信息。为了避免“数 据爆炸，知识匮乏”的尴尬，从海量的半结构化w e b 数据中抽取出结构化的、 与主题相关的数据，向用户提供增值服务( 如监控股市的及时行情、比较各个网 站的商品价格、跟踪合作伙伴或竞争对手的动态、集成企业内外部的各种信息 等) ，各种w e b 数据抽取技术应运而生，并日渐发挥出强大的作用。因此，w e b 数据抽取技术有着明显的优势和广阔的前景，是数据提取技术、人工智能信息检 索、自然语言理解技术在网络信息处理中的应用，是当今多个领域的研究热点。 本论文探讨了针对由模板生成的列表页面，如何检测其通用模板，并将嵌入 在模板中的数据抽取出来，实现了列表页面数据的自动抽取。 首先，简要叙述了半结构化数据、w e b 数据抽取、列表页面的概念； 接着，深入研究了w e b 数据抽取技术的发展历史、现有技术，并在对各种 技术比较后，指出现有技术的优缺点、未来可能的发展方向； 然后，详细介绍了作者前一阶段的学术成果自动抽取w e b 数据的树对 齐算法，它是本论文所提出的基于标签树的列表页面数据抽取系统的研究基础和 核心部分。本论文实现了此算法，完善了树对齐之前和之后的相关流程，形成了 完整的w e b 数据抽取系统； 最后，详细介绍了本论文所提出的基于标签树的列表页面数据抽取系统的设 计、实现与实验，该系统构造标签树、挖掘主数据区域、识别数据记录、生成记 录模式，逐步缩小目标区域大小，从而抽取用户感兴趣的数据记录或有用的信息。 实验证明，该系统能够有效地处理列表页面，抽取数据信息，能够适应广泛的实 际需求，并具有深入推广的应用价值。 关键词：w e b 数据抽取，w e b 数据挖掘，包装器，列表页面，标签树匹配 华东师范大学硕l 学位论文 基于标签树的列表页面数据抽取技术研究 a b 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 ，w e bh a sb e c o m eah u g e ，s h a r e da n d d i s t r i b u t e di n f o r m a t i o nr e s o u r c es e t h o wt oa u t o m a t i c a l l ya c h i e v et h ei n t e r e s t i n gd a t a r e c o r d so rt h eu s e f u li n f o r m a t i o nf r o mt h ev a s tw e bi n f o r m a t i o nr e s o u r c e s ，h a s b e c a m eat o p i cd i s c u s s e di nd e p t hb yp e o p l e n o w a d a y s ，m o s to fw e bd a t aa r e d i s p l a y e di nt h eu n s t r u c t u r e do rs e m i - s t r u c t u r e df o r m ，l a c kt h ed e s c r i p t i o no fd a t a i t s e l f , a n dd on o tc o n t a i nc l e a rs e m a n t i ca n ds p e c i f i ct e m p l a t e ，t h u s ，a p p l i c a t i o n p r o g r a mc a nn o td i r e c tp a r s ea n du t i l i z et h e m i no r d e rt oa v o i dt h ee m b a r r a s s m e n to f “n u m e r o u sd a t a ，s h o r tk n o w l e d g e ”，e x t r a c ts t r u c t u r e da n dr e l e v a n tt ot h et o p i cd a t a f r o mt h ev a s ts e m i s t r u c t u r e dw e bd a t a ，p r o v i d ev a l u e a d d e ds e r v i c e st ou s e r s ( e g ， m o n i t o rt h es t o c km a r k e t sp r o m p ts i t u a t i o n ，c o m p a r et h eg o o d s p r i c e ss u p p l i e db y d i f f e r e n tw e b s i t e s ，f o l l o wc o o p e r a t o r s a n dc o m p e t i t o r s t r e n d s ，i n t e g r a t ee n t e r p r i s e s i n s i d ea n do u t s i d ev a r i o u si n f o r m a t i o n s ) ，v a r i o u sw e bd a t ae x t r a c t i o nt e c h n o l o g y c o m e so u t ，a n dp l a y sm o r ei m p o r t a n tr o l ed a yb yd a y t h e r e f o r e ，t h ew e bd a t a e x t r a c t i o nt e c h n o l o g yh a sd i s t i n c ta d v a n t a g ea n dw i d ep r o s p e c t ，i sa na p p l i c a t i o no f d a t ae x t r a c t i o nt e c h n o l o g y , a r t i f i c i a li n t e l l i g e n c ei n f o r m a t i o nr e t r i e v a l ，a n dn a t u r a l l a n g u a g ec o m p r e h e n s i o nt e c h n o l o g y , i nw e bi n f o r m a t i o np r o c e s s i n g ，a n di so n eo ft h e h o t t e s tr e s e a r c ha r e a si nm u l t i p l er e s e a r c hf i e l d s i nt h i sp a p e r ，f o rt e m p l a t e - g e n e r a t e dl i s tp a g e s ，w er e s e a r c hh o wt ot e s ti t s c o m m o nt e m p l a t e ，e x t r a c te m b e d d e dd a t a ，a u t o m a t i c a l l ya c h i e v et h ed a t ai nl i s tp a g e s f i r s t l y , w eb r i e f l yi n t r o d u c et h ec o n c e p to fs e m i s t r u c t u r e dd a t a ，w e bd a t a e x t r a c t i o na n dl i s tp a g e s ； s e c o n d l y , w ed e e p l yr e s e a r c ht h ed e v e l o p m e n ta n de x i s t i n gt e c h n o l o g yo fw e b d a t ae x t r a c t i o nt e c h n o l o g y , d e m o n s t r a t et h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h e e x i s t i n gt e c h n o l o g ya n dt h ed e v e l o p m e n td i r e c t i o no ft h ef u t u r et e c h n o l o g ya f t e r c o m p a r i n g ； t h i r d l y , w ep a r t i c u l a r l yi n t r o d u c et h ea u t o m a t i c e w e bd a t ae x t r a c t i o nb a s e do n t r e ea l i g n m e n ta so u rb e f o r ea c a d e m i cp u b l i c a t i o n i ti st h er e s e a r c hf o u n d a t i o na n d 2 华东师范大学硕l ：学位论文基于标签树的列表页面数据抽取技术研究 c o r eo ft h ed a t ae x t r a c t i o ns y s t e mb a s e dt a gt r e ef r o ml i s tp a g e sw h o mt h i sp a p e r a d v a n c e d i nt h i sp a p e r , w er e a l i z e dt h i sa l g o r i t h m ，i m p r o v e dt h er e l a t e dp r o c e s s b e f o r ea n da f t e rt r e ea l i g n m e n t ，g e ta l li n t e g r a t e dw e bd a t ae x t r a c t i o ns y s t e m ； f i n a l l y , w ep a r t i c u l a r l yi n t r o d u c et h ed e s i g n ，r e a l i z a t i o na n de x p e r i m e n to f o u r d a t ae x t r a c t i o ns y s t e mb a s e dt a gt r e ef r o ml i s tp a g e s ，t h i ss y s t e mc o n s t r u c t st a gt r e e ， m i n e sp r i m a r yd a t ar e g i o n ，i d e n t i f i e sd a t ar e c o r da n dg e n e r a t e sr e c o r ds c h e m a , r e d u c i n gt h es c o p eo fo b je c t i v er e g i o ns t e pb ys t e p ，t oe x t r a c tt h ei n t e r e s t i n gd a t a r e c o r d so rt h eu s e f u li n f o r m a t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i ss y s t e mc a n e f f e c t i v e l yd e a lw i t hl i s tp a g e s ，e x t r a c td a t ai n f o r m a t i o n ，a d a p tb r o a dp r a c t i c a ld e m a n d ， a n dh a st h ea p p l i c a t i o nv a l u et op o p u l a r i z e k e yw o r d s ：w e b d a t ae x t r a c t i o n ，w e bd a t am i n i n g ，w r a p p e r ，l i s tp a g e ，t a g t r e em a t c h i n g 3 - 华东师范大学硕 = 学位论文基十标签树的列表页面数据抽取技术研究 目录 摘 要：一l a l j ；s t r a c t 2 目j j i 4 第一章 绪论一6 1 1 论文的研究背景及意义6 1 2 国内外研究现状8 1 3 论文的研究内容及创新之处一9 1 4 论文的组织结构1 0 第二章w 曲数据抽取技术的相关概述1 2 2 1 半结构化数据1 2 2 1 1 半结构化数据的定义1 2 2 1 2 半结构化数据的产生原因1 2 2 1 3 半结构化数据的特点l3 2 2 w 曲数据抽取1 3 2 2 1 w e b 数据抽取的定义1 3 2 2 2 w e b 数据抽取技术的产生与发展1 4 2 2 3 w e b 数据抽取技术的分类1 4 2 2 4 w e b 数据抽取技术的比较分析1 6 2 2 5 w e b 数据抽取技术的朱米发展方向1 7 2 3 列表页面18 第三章自动抽取w e b 数据的树对齐算法2 0 3 1 引言2 0 3 2 相关研究- 一2 l 3 3 树对齐算法2 2 3 4 实验结果2 6 3 5 结论2 8 第四章基于标签树的列表页而数据抽取系统的设计、实现与实验2 9 4 1 基于标签树的列表页面数据抽取系统的设计2 9 4 1 1 基于标签树的列表页面数据抽取系统的总体框架2 9 4 1 2 基丁标签树的列表页面数据抽取系统的基本设计思想3 0 4 2 基于标签树的列表页面数据抽取系统的实现模块1 ：标签树构造31 4 2 1 h t m l 页面预处理的。醺要性及目的3 l 4 2 2 h t m l 页面的标签树构造算法3l 4 3 基于标签树的列表页面数据抽取系统的实现一模块2 ：主数据区域挖掘3 5 4 3 1 涉及的主要概念3 5 4 3 2 相似度的计算3 7 4 3 3 基于相似度的层次划分思想3 8 4 4 基于标签树的列农页面数据抽取系统的实现一模块3 ：数据记录识别。4 4 华东师范人学硕士学位论文 基于标签树的列表页面数据抽取技术研究 4 4 1 数据记录节点的定义4 4 4 4 2 数据记录识别算法4 4 4 5 基于标签树的列表页而数据抽取系统的实现模块4 ：记录模式生成4 6 4 5 i 树距离度量标准的介绍4 6 4 5 2 基于动态规划的树匹配算法4 8 4 5 3 基于树匹配的记录模式生成算法5 0 4 6 基于标签树的列表页面数据抽取系统的实验5 4 4 6 1 评价指标介绍5 4 4 6 2 实验设计与性能分析5 7 第五章总结和展望6 2 5 1 总结6 2 5 2 展望6 3 附勇毛一6 4 参考文献6 5 致谢一7l 一5 - 华东师范大学硕 ：学位论文 基于标签树的列表页面数据抽取技术研究 第一章绪论 本章首先介绍了本论文的研究背景及意义；然后分析了国内外w e b 数据抽 取技术的研究现状；其次阐明了本论文的研究内容及创新之处；最后简述了本论 文的组织结构。 1 1 论文的研究背景及意义 作为i n t e m e t 最重要的应用，过去几十年w e b 不断迅猛发展，提供了便捷的 文档发布与获取机制，成为了世界上规模最大的公共信息资源库。作为全球性的 信息服务中心，w e b 上的信息内容丰富、分布广泛，其领域包括新闻、财经、政 治、教育、政府、商业、消费、服务、体育、文化等等。2 0 1 1 年1 月1 9 日，中 国互联网络信息中心( c n n i c ) 发布的第2 7 次中国互联网络发展状况统计报 告【l 】称，自2 0 0 3 年开始，中国的网页规模基本保持翻番增长，2 0 1 0 年网页数 量达到6 0 0 亿个，年增长率7 8 6 。2 0 1 0 年动态网页增长幅度高于静态网页，静 态动态网页的比例已经从1 3 ：1 降低为1 1 4 ：1 。与此同时，平均每个网站的网页 数量达到3 1 ，4 1 4 个，年增长率达到2 0 2 。 w e b 主要呈现h t m l 页面的形式，但由于开发的公司或组织各自独立，其 形式和内容都存在很大差异。统计显示，目前大多数w e b 数据都以非结构或半 结构化的形式呈现，缺乏对数据本身的描述，不包含清晰的语义，模式也不太明 确，这使得应用程序无法直接解析并利用w e b 上的海量信息。搜索引擎( s e a r c h e n g i n e ) 能够查询用户感兴趣的数据，但所得结果仅仅是一些不相关的h t m l 页 而，想要进一步地精确定位到数据却十分困难。 随着技术的发展，大部分h t m l 页面己不再是纯静态的，而被取代为动态 页面( 如a s p 、p h p 、j s p 等) ，它们通常从后台数据库获取数据记录，然后按 照通用模板展现给用户。为了满足人类的审美观和商业需求，除了包含与主题相 关的数据外，h t m l 页面上还充斥着大量的与主题无关的冗余信息( 如注释、图 片、导航栏、超链接、广告、网站版本、脚本语言、命名空间、& n b s p 、h i d d e n 、 s t y l e 、s e l e c t 、b u t t o n 等) ，而这无疑会给应用程序抽取w e b 数据带来干扰。 华东师范大学硕士学位论文基于标签树的列表页面数据抽取技术研究 为了避免“数据爆炸，知识匮乏”的尴尬，从海量的半结构化w e b 数据中 抽取出结构化的、与主题相关的数据，向用户提供增值服务( 如监控股市的及时 行情、比较各个网站的商品价格、跟踪合作伙伴或竞争对手的动态、集成企业内 外部的各种信息等) ，各种w e b 数据抽取技术应运而生，并日渐发挥出强大的作 用。这一技术通过包装( w r a p ) 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 用户的需求。随着i n t e m e t 的迅猛发展和用户需求的膨胀，w _ e b 上的资源 异常丰富，信息无比庞大，几乎涉及任何主题及领域。但由于w e b 页面本身结 构不统一，来自不同的数据库，所以用户很难准确获得感兴趣的数据。统计显示： “9 9 的w e b 数据对于9 9 的用户来说是无用的。每个用户真正感兴趣的数据 只是他( 她) 查询后所得结果之中很少的一部分，大量无关的信息会干扰甚至淹 没用户感兴趣的数据。”最初，研究人员对w e b 数据抽取方法的研究主要集中在 两个方面：搜索引擎( s e a r c he n g i n e ) 、w e b 查询。其中，搜索引擎主要通过关键 字进行查询，这无疑是最直接的获取w e b 数据的方法，但所得结果包含太多无 关页面，想要进一步定位到数据十分困难。 2 w e b 数据挖掘的需求。数据挖掘又被称为数据库知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) 。它通常是指从数据源( 如数据库、文本、图片、 万维网等) 中探寻有用的模式或知识的过程。这罩，所谓的“模式”必须是有用 的、有潜在价值的、并且是可以被理解的。抽取结果通常表示为概念、规则、规 律、模式等形式。p i t k o wj 指出：w e b 数据挖掘( w 曲d a t am i n i n g ，w d m ) 就 是从w e b 文档和w e b 活动中抽取用户感兴趣的、潜在的、有用的模式和隐藏的 信息【2 1 。其目标是从超链接结构、页面内容、使用日志当中探寻有用的信息。虽 然w e b 数据挖掘使用了许多数据挖掘技术，却不仅仅是传统数据挖掘的简单应 用。w e b 数据大部分是半结构化的或非结构化的，并且数据量不断迅速增长，这 华东师范大学硕士学位论文基于标签树的列表页面数据抽取技术研究 些都为w e b 数据挖掘提供了新的挑战。如果能抽取、集成w e b 数据，使半结构 化或非结构化的数据转化为结构化的，将大大改善w e b 数据挖掘的效率和性能。 3 w e b 应用的需求。现今，动态页面越来越多，数据信息及时更新，w e b 页 面的格式和内容瞬息万变。如新闻门户、证券公司、电子商务网站等都不断更新 各自的网页。所以，一些全新的基于w e b 的应用【3 】如雨后春笋，纷纷涌现出来向 用户提供增值服务( 如监控股市的及时行情、比较各个网站的商品价格、跟踪合 作伙伴或竞争对手的动态、集成企业内外部的各种信息等) 。因此，提供给用户 的数据必须是可信赖且机器可读的，而搜索引擎技术和w e b 查询技术对此却显 得无能为力。 1 2 国内外研究现状 w e b 数据抽取技术有着明显的优势和广阔的应用前景，是数据提取技术、人 工智能信息检索、自然语言理解技术在网络信息处理中的应用，是当今多个领域 的研究热点。它同搜索引擎和w e b 查询有着本质上的差异，并且对数据的处理 粒度也不相同。搜索引擎主要通过关键字进行查询，这无疑是最直接的获取w e b 数据的方法，但所得结果包含太多无关页面，且没有添加任何语义信息到数据中 去，所以用户想要进一步定位到用户感兴趣的数据十分困难。而w e b 数据抽取 分析作为输入的w e b 页面的结构特点和数据特征，能够准确抽取用户感兴趣的 数据，并将其保存到数据库或其他格式的文件中( 如t x t 、x m l 等) ，以供s q l 语言、x m l 查询语言查询，被其他应用程序使用。 在国外，研究人员很早就开始了数据抽取( d a t ae x t r a c t i o n ，d e ) 的研究。 其中，比较典型的数据抽取系统有：l i n g u i s t i cs t r i n g 项引引、f r u m p 系统【5 】、 a t r a n s 系统等。到了1 9 9 0 s ，随着w e b 的发展，研究人员开始逐渐将兴趣转向 w e b 数据抽取，这个时期出现了很多新技术和有用的抽取工具。其中，比较典型 的w e b 数据抽取系统有：m i n i n gt h ew o r l dw i d ew e b 项目和斯坦福大学j h a m m e r 等人的系统【6 】。 目前，各种w e b 数据抽取技术广泛采用“网页包装”( w 曲p a g ew r a p p i n g ) ， 研究精力主要集中在对抽取方法的研究【7 】和对包装器( w r a p p e r ) 的自动化或半自 动化生成工具的研究上。其中，抽取方法主要包括：直接解析、h t m l 结构分析、 数据建模。最初包装器的生成主要采用手工方式编写，它的开发和维护都非常困 难，无法处理数量巨大的情况。因此出现了很多包装器的自动化或半自动化生成 华东师范人学硕l 学位论文基于标签树的别表页面数据抽取技术研究 工具。其中，a r a n e u s 8 】、b y u 9 1 、r o a d r u n n e r 10 1 、x w r a p 1 1 1 、e x a l g 1 2 1 等是 非商业工具，主要由大学的研究团体开发；而商业工具则包括v i s u a lw e bt a s k 1 3 】、 x f e t c hw r a p p e r 14 1 、w 4 f t l 5 1 等。以上这些大部分是半自动化的，即采用监督学 习方法，需要人工地定义模板，不具有普适性，大部分抽取结果由正则表达式匹 配得到。 然而随着技术的发展，大部分h t m l 页面己不再是纯静态的，而被取代为 动态页面( 如a s p 、p h p 、j s p 等) ，它们通常从后台数据库获取数据记录，然 后按照通用模板展现给用户。本论文探讨了针对由模板生成的列表页面，如何检 测其通用模板，并将嵌入在模板中的数据抽取出来，实现了列表页面数据的自动 抽取。针对由模板生成的列表页面抽取数据的问题，目前常用的经典方法有 r o a d r u n n e r 1 0 】和e x a l g 1 2 】等。 1 3 论文的研究内容及创新之处 本论文的研究内容主要包括： 首先，简要叙述了半结构化数据、w e b 数据抽取、列表页面的概念； 接着，深入研究了w e b 数据抽取技术的发展历史、现有技术，并在对各种 技术比较后，指出现有技术的优缺点、未来可能的发展方向； 然后，详细介绍了作者前一阶段的学术成果自动抽取w e b 数据的树对 齐算法，它是本论文所提出的基于标签树的列表页面数据抽取系统的研究基础和 核心部分。本论文实现了此算法，完善了树对齐之前和之后的相关流程，形成了 一个完整的w e b 数据的抽取系统； 最后，详细介绍了本论文所提出的基于标签树的列表页面数据抽取系统的没 计、实现与实验，该系统构造标签树、挖掘主数据区域、识别数据记录、生成记 录模式，逐步缩小目标区域大小，从而抽取用户感兴趣的数据记录或有用的信息。 实验证明，该系统能够有效地处理列表页面，抽取数据信息，能够适应广泛的实 际需求，并具有深入推广的应用价值。 本论文的创新之处主要包括： 1 h t m l 页而预处理主要包括两项内容：一是修j 下源文件的错误( 如标签比 配错误等) ，二是删除源文件的冗余信息( 如注释、图片、导航栏、超链接、广 告、网站版本、脚本语言、命名空f n j 、& n b s p 、h i d d e n 、s t y l e 、s e l e c t 、b u t t o n 等) ， 从而减小后续抽取步骤的时| 、日j 复杂度，提高抽取系统的效率和抽取结果的精度。 华东师范人学硕十学位论文基于标签树的列表页面数据抽取技术研究 2 针对从模板生成的w e b 页面中自动抽取w e b 数据的问题，提出自动抽取 w e b 数据的树对齐算法。该算法能够确定输入w e b 页面的最大匹配结构。经过 一系列的对齐操作之后，多棵树被合并成为一棵记录着合并前多个w e b 页面上 的统计信息的合并树，树对齐算法可以发现合并树中的重复模式，在最可能内容 块上构建包装器，并按照重复模式从w e b 页面上抽取数据。实验结果表明，该 算法的抽取结果具有较高的准确性和良好的稳定性。 3 完整地提出基于标签树的列表页面数据抽取系统，该系统包括标签树构造 算法、数据区域挖掘算法、数据记录识别算法、记录模式生成算法等，引入元素 布局位置等信息用于清洗页面，采用层次划分思想实现对w e b 页面数据区域的 挖掘，通过树匹配算法生成记录模式，最终实现数据项的抽取。 1 4 论文的组织结构 第一章绪沦 本章首先介绍了本论文的研究背景及意义；然后分析了国内外w e b 数据抽 取技术的研究现状；其次阐明了本论文的研究内容及创新之处；最后简述了本论 文的组织结构。 第二章w e b 数据抽取技术的相关概述 本章简要介绍了相关于w e b 数据抽取技术的几个概念。首先介绍了半结构 化数据的定义、产生原因、特点；然后阐明了w e b 数据抽取的定义、w e b 数据 抽取技术的产生与发展、w e b 数据抽取技术的分类、w e b 数据抽取技术比较分析、 w e b 数据抽取技术的未来发展方向；最后描述了本论文针对的由模板生成的列表 页面。 第三章自动抽取w e b 数据的树对齐算法 本章详细介绍了作者前一阶段的学术成果自动抽取w e b 数据的树对齐 算法，针对由模板生成的w e b 页面中自动抽取w e b 数据的问题，本章提出一种 新的树对齐算法。该算法能够确定输入w e b 页面的最大匹配结构。经过一系列 的对齐操作之后，多棵树被合并成为一棵记录着合并前多个w e b 页面上的统计 信息的合并树，树对齐算法可以发现合并树中的重复模式，在最可能内容块上构 建包装器，并按照重复模式从w e b 页面上抽取数据。实验结果表明，该算法具 有较高的准确性和良好的稳定性。 第四章基于标签树的列表页面数据抽取系统的设计、实现与实验 华东师范人学硕上学位论文基于标签树的列表页面数据抽取技术研究 本章详细介绍了本论文所提出的一种新颖的基于标签树的列表页面数据抽 取系统，介绍内容主要分为三个部分。首先，概要介绍了该系统的设计，其中包 括总体框架、基本设计思想；然后，逐一介绍了该系统的四个实现模块，其中包 括每个模块中所涉及的概念、规则、算法；最后，给出该系统的实验，其中包括 采用的评价指标、实验设计与性能分析。 第五章总结和展望 本章首先总结回顾了本论文的研究工作；然后阐明表述了下一阶段研究工作 的方向和内容。 华东师范大学硕l 学位论文幕于标签树的列表页面数据抽取技术研究 第二章w e b 数据抽取技术的相关概述 本章简要介绍了相关于w e b 数据抽取技术的几个概念。首先介绍了半结构 化数据的定义、产生原因、特点；然后阐明了w e b 数据抽取的定义、w e b 数据 抽取的产生与发展、w e b 数据抽取技术的分类、w e b 数据抽取技术比较分析、 w e b 数据抽取技术的未来发展方向；最后描述了本论文针对的由模板生成的列表 页面。 2 1 半结构化数据 2 1 1 半结构化数据的定义 在文献【1 6 】中，作者较为模糊地定义了半结构化数据：存在一定结构，但结构 定义不严格。在文献【1 7 】中，从描述数据结构的文法是否上下文无关，作者通给出 了下面四个概念的精确定义。 定义2 1 ( 数据) 。即为一个有序流a l a 2 a 。，且满足1 ，2 ，m _ a l a 2 a n 的划分l ，2 ，a m 称为它的有序划分。 定义2 2 ( 结构化数据) 。存在全局一致的上下文无关文法。 定义2 3 ( 非结构化数据) 。不存在全局一致的上下文无关文法，且任意一个 有序划分也不存在局部一致的上下文无关文法( 如自然语言、图像等) 。 定义2 4 ( 半结构化数据) 。不存在全局一致的上下文无关文法，但某个有序 化分存在局部一致的上下文无关文法。 2 1 2 半结构化数据的产生原因 半结构化数据之所以会出现，主要有以下几点原因： 1 数据来源并不完全遵循数据形式。例如，作为全球性的信息服务中心，w e b 是世界上规模最大的公共信息资源库。但w e b 查询大多只停留在检索w e b 内容 的层面上，而忽略了w e b 结构中所包含的信息。另外地，由于w e b 足超链接关 华东师范大学硕上学位论文基于标签树的列表页面数据抽取技术研究 联起来的一组页面，它是异构的、分布式的，其上的数据并不符合任何已有的数 据模型，所以需要一种方法描述它的结构。 2 在不同数据库之间交换或转换数据时，要求数据的模式灵活。 3 考虑到便于显示的要求，必须将某些结构化数据进行半结构化处理。一般