（计算机软件与理论专业论文）面向复杂数据源的数据抽取模型和算法研究.pdf

摘要 摘要 随着信息技术的飞速发展，互联网上的电子文档已经成为一个巨大的信息 源。在这个巨大的信息源面前，人们自然希望利用成熟的数据库技术对感兴趣的 数据进行方便的查询、分析和报告。这就刺激了围绕这些数据源开发数据集成系 统的研究工作。数据集成系统组合来自不周数据源的数据，目的在于以一个统一 的视图提供给用户使用。 数据抽取是数据集成系统的基础问题之一，这一问题可简单地描述为：给定 数据源s ，确定一个s 到数据库冠的映射朋，该映射用数据抽取模型、抽取规则 和抽取算法去抽取j 中的数据对象，用数据库模式、映射规则和组装算法将已抽 取的数据对象组装到览中( 本文将数据抽取模型、抽取规则、数据库模式和映射 规则通称为元数据) 。实现映射埘的计算机程序称为包装器。数据集成系统常用 包装器生成工具生成所需的包装器。由于数据源的多样性和复杂性，如何快速准 确地为各种数据源建立包装器是数据集成系统实现的关键。这一课题已成为计算 机界研究的热点，也是本文研究的核心问题。 本文的研究动机是从各种生物数据源中抽取感兴趣的数据对象，将这些数据 对象组装到生物数据集成系统中，目的在于为生物学家搭建方便的查询分析平 台。从数据抽取的角度讲，生物数据源不仅规模庞大，抽取准确度要求高，而且 往往具有一些会导致现有包装器生成工具失效的复杂特性。首先，生物数据源中 的数据对象具有结构复杂性：数据对象往往具有多层嵌套结构，对象的成分可以 缺失、多次重复、有序出现或无序出现：其次，抽取规则具有复杂性：生物数据 源常用非标准标签对数据对象进行分隔，许多需抽取的对象甚至没有恰当标签， 某些指定的标签可能会在数据对象内容中出现，导致歧义( 即数据源中含有噪声 成分) ；第三，映射规则具有复杂性：往往需要对已抽取的数据对象实施一些扩 展操作后才能将它们组装到数据库中。 本文从分析现有包装器生成工具在处理复杂生物数据源时存在的问题入手， 提出了两种面向复杂数据源的数据抽取模型和算法，在此基础上设计和实现了 r e d e 包装器生成工具和l 树包装器生成工具。本文的主要研究成果包括： ( 1 ) 提出了一套面向无噪声复杂数据源的新型数据抽取方法 针对现有包装器生成工具需要手工生成和维护大量元数据的问题，本文实现 了利用元数据间的依赖关系，从正则表达式( r e g u l a re x p r e s s i o n ，简称r e ) 自 动导出其他元数据的映射方法。这一方法降低了元数据生成和维护的工作量，保 证了元数据间的一致性；针对传统r e 匹配算法在解决数据抽取问题时存在的不 足，本文设计了一种基于传统r e 匹配的新型数据抽取算法，该算法将传统r e 匹配作为基本建筑模块，利用r e 分析树在数据源中递归地进行数据对象的切分、 面向复杂数据源的数据抽取模型和算法研究 i v 复旦大学博士学位论文 摘要 抽取和组装。本文也给出了分析抽取算法效率的代价模型，在此基础上讨论了抽 取算法的伸缩性和时间复杂度并用实验进彳亍了验证。 ( 2 ) 提出了一种新的r e 二义性检查算法 在构造r e 时，用户往往会有意地引入一些可简化r e 构造的有益二义性， 也会无意地遗留一些危害抽取结果准确性的有害二义性，而现有的r e 二义性处 理方法却不能区别对待这两种二义性。为解决这一问题，本文对r e 中的切分二 义性问题进行了深入研究，首先给出了r e 切分特征的形式定义，然后以一组定 理为基础给出了计算r e 切分特征的方法，最后基于r e 切分特征给出了有害二 义性的形式定义并设计了检查算法，目的在于帮助用户对r e 进行调试。 ( 3 ) 提出了一种面向含噪声复杂数据源的新型数据抽取模型 针对现有数据抽取模型对含噪声复杂数据源缺乏表达能力的问题，本文用自 行设计的扩展正则表达式( e x t e n d e dr e g u l a re x p r e s s i o n ，简称e r e ) 来描述数据 源，提出了面向含噪声复杂数据源的d e - 树数据抽取模型，给出了数据对象定位 器的构造方法。用一组定理论证了数据对象之间的切分条件并给出了切分方法， 讨论了结点的定位能力，基于结点的定位能力和数据对象的可切分性给出了d e 一 树合法性检查方法( 合法的d e 树称为l 树) 。 ( 4 ) 挺出了一种面向含噪声复杂数据源的新型数据抽取算法 针对现有数据抽取算法不能准确抽取含噪声复杂数据源的问题，本文设计了 l 树匹配算法。在抽取数据对象时，该算法摈弃基于关键词搜索的传统思路，采 用基于数据对象切分的“试探一回溯”策略，用定位器来估算搜索分区，用匹配约 束来修正搜索分区并过滤噪声，从而可准确抽取含缺失、嵌套、有序、无序和噪 声成分复杂组合的数据源。 ( 5 ) 设计并实现了l 树包装器生成工吴 l 树包装器生成工具包括：用作数据抽取脚本语言的e r e ；支持e r e 可 视化构建、e r e 逻辑检查和抽取结果可视化评价的编辑调试环境 抽取结果的 x m l 表达格式。l 树包装器生成工具和现有包装器生成工具的比较结果表明： l _ 树包装器生成工具的各项指标都具有优良性能。l - 树包装器生成工具已用于构 建一个整合的生物信息在线数据仓库系统。 关键词：数据抽取，数据抽取模型，抽取算法，复杂数据源，d e - 树，l - 树，噪声 中图分类号：t p 3 0 2 面向复杂数据源的数据抽取模型和算法研究 v 复旦大学博士学位论文 a b s t r a c t a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , e l e c t r o n i cd o c u m e n t s o n l i n eh a v et u r n e do u tt ob eah u g ei n f o r m a t i o ns o u r c e u s e r sw o u l dl i k et oa p p l y m a t u r ed a t a b a s et e c h n o l o g yt oq u e r y , a n a l y z ea n dr e p o r td a t ao fi n t e r e s t sf r o mt h i s h u g ei n f o r m a t i o ns o n r c e t h i sh a ss p u r r e dt h er e s e a r c ho fd e v e l o p i n gd a t ai n t e g r a t i o n s y s t e m sa r o u n ds u c hd a t as o u r c e s d a t ai n t e g r a t i o ni sam e t h o dt h a tc o m b i n e sd a t a f r o md i f f e r e n td a t as o u r c e sa n dp r o v i d e su s e r s 、丽t l lau n i f i e dv i e wo f t h e s ed a t a t h eb a s i so fd a t ai n t e g r a t i o ns y s t e mi sd a t ae x t r a c t i o ni s s u et h a tc a nb es i m p l y d e s c r i b e da s ：g i v e nad a t as o u r c esd e t e r m i n ef r o mst oad a t ar e p o s i t o r yr a m a p p i n g 兜t h a ts e a r c h e sf o rd a t ao b j e c t si ns u s i n gad a t ae x t r a c t i o nm o d e l ，as e to fe x t r a c t i o n r u l e sa n da ne x 仃a c f i o na l g o r i t h m ，a n dp o p u l a t e s 冠谢t 1 1d a t ao b j e c t sf o u n di ns u s i n ga d a t a b a s es c h e m e ，as e to fm a p p i n gr u l e sa n dap o p u l a t i n ga l g o r i t h m ( i nt h i st h e s i s ， d a t ae x t r a c t i o nm o d e l ，e x t r a c t i o nr u l e s ，d a t a b a s es c h e m ea n dm a p p i n gr u l e sa r ec a l l e d m e t a d a t a ) ac o m p u t e rp r o g r a mt h a tr e a l i z e sm a p p i n gm i sc a l l e daw r a p p e r d a t a i n t e g r a t i o ns y s t e m so f t e ng e n e r a t ew r a p p e r s 、i 也w r a p p e rg e n e r a t i o nt o o l k i t s a s t h e r em a yb ev a r i o u sd a t as o u r c e sw i t hv a r i o u sc o m p l e x i t i e s , h o wt oa c c u r a t e l yb u i l d w r a p p e r sf o rt h e s ed a t as o u r c e s i st h ek e yt or e a l i z ed a t ai n t e g r a t i o ns y s t e m s t h i sh a s b e c o m eah o tr e s e a r c ht o p i c ，a n di sa l s ot h ec o r eo f t h i st h e s i s t h em o t i v a t i o no ft h i st h e s i si st oe x t r a c td a t ao b j e c t sf r o mv a r i o u sb i o l o g i c a l d a t as o u r c e sa n dp o p u l a t e sa b i o l o g i c a ld a t ai n t e g r a t i o ns y s t e mw i t ht h e s ed a t ao b j e c t s ， a i m i n ga tb u i l d i n gac o n v e n i e n tq u e r ya n da n a l y s i sp l a t f o r mf o rb i o l o g i c a ls c i e n t i s t s i np o i n to fd a t ae x t r a c t i o ni s s u e ，b i o l o g i c a ld a t as o u r c e sa r eh u g ed a t as o u r c e sn o t o n l yw i mh i g he x t r a c t i o na c c u r a c yd e m a n d b u ta l s ow i 血s o m ec o m p l e x i t i e st h a t p a r a l y z et h ep r e s e n tw r a p p e rg e n e r a t i o nt o o l k i t s f i r s t l y , d a t ao b j e c t si nb i o l o g i c a l d a t as o u r c e so f t e nt a k et h ef o r mo fah i e r a r c h i c a l l yn e s t e ds t r u c t u r e 、i t ht h e i r c o m p o n e n t sm i s s i n g ，r e p e a t ，o r d e r e da n d o ru n o r d e r e d t h i sr e s u l t si nt h es t r u c t u r a l c o m p l e x i t yo f d a t ao b j e c t s s e c o n d l bb i o l o g i c a ld a t as o u r c e so f t e nd e l i m i tt h e i rd a t a o b j e c t su s i n gs e t so fn o n s t a n d a r ds e g m e n t a t i o nt a g s ，w i t hm a n yd a t ao b j e c t sh a v i n g n op r o p e rt a g sa n ds o m ep r e - a n n o u n c e dt a g so c c a s i o n a l l ya p p e a r i n gi nt h ec o n t e n t so f d a t ao b j e c t s ( i ，et h e r em a yb es o m en o i s yc o m p o n e n t si nt h ed a t as o u r c e s ) t h i s g i v e sr i s et ot h ec o m p l e x i t yo fe x t r a c t i o nr u l e s t h i r d l y , b e f o r ep o p u l a t i n gd a t a b a s e ， e x t r a c t e dd a t ao b j e c t so f t e nn e e dt ou n d e r g os o m ee x t e n d e do p e r a t i o n s t h i sb r i n g s a b o u tt h ec o m p l e x i t yo f m a p p i n gr u l e s s t a r t i n gf r o ma n a l y z i n gt h ep r o b l e m st h a tt h ep r e s e n tw r a p p e rg e n e r a t i o nt o o l k i t s 面向复杂数据源的数据抽取模型和算法研究v i复旦大学博士学位论文 a b s t r a c t e n c o u n t e ri nd e a l i n gw i t hc o m p l e xb i o l o g i c a ld a t as o u r c e s ，t h i st h e s i sp r e s e n t st w o d a t ae x t r a c t i o nm o d e l sa n da l g o r i t h m sf o rc o m p l e xd a t as o n r c e s ，a n dt h e nd e s i g n sa n d r e a l i z e sr e d ew r a p p e rg e n e r a t i o nt o o l k i ta n dl t r e ew r a p p e rg e n e r a t i o nt o o l k i t c o n t r i b u t i o n so f t h i st h e s i sm a i n l yi n c l u d et h ef o i l o w i n g ： ( 1 ) an e wd a t ae x t r a c t i o nm e t h o df o rc o m p l e x d a t as o n r c e sw i t h o u tn o i s e s t h ep r e s e n tw r a p p e rg e n e r a t i o nt o o l k i t so r e nr e q u i r em a n u a l l yg e n e r a t i n ga n d m a i n t a i n i n gm a n ym e t a d a t a i no r d e rt oo v e r c o m et h i sf l a w , w er e a l i z ea na u t o m a t i c m e t a d a t ag e n e r a t i o nm e t h o dt h a tc a nd e d v em e t a d a t af r o mar e g u l a re x p r e s s i o n ( r e ) b yt a k i n gt h ef u l la d v a n t a g eo ft h ed e p e n d e n c i e sa m o n gm e t a d a t a t h i sm e t h o d l o w e r st h ew o r k l o a do fg e n e r a t i n ga n dm a i n t a i n i n gm e t a d a t a ，a n dc a nk e 印t h e c o n s i s t e n c ya m o n gm e t a d a t a a sc o n v e n t i o n a lr em a t c ha l g o r i t h mc a r m o tb ed i r e c t l y u s e dt os o l v ed a t ae x t r a c t i o np r o b l e m s ，w ed e s i g nan e wd a t ae x t r a c t i o na l g o d t h m b a s e do nc o n v e n t i o n a lr em a t c h t l l i sa l g o r i t h ma d o p t sc o n v e n t i o n a lr em a t c ha s t h eb a s i c b u i l db l o c k ，a n dr e c u r s i v e l ys e g m e n t s ，e x t r a c t sa n da s s e m b l e sd a t ao b j e c t si n t h ed a t as o u r c eu s i n gar ep a r s et r e e w ea l s og i v eac o s tm o d e lt oa n a l y z et h e e f f i c i e n c yo ft h ea l g o r i t h m , a n dt h e n d i s c u s sa n dv e r i f yw i t he x p e r i m e n t st h e s c a l a b i l i t ya n dt h et i m ec o m p l e x i t yo f t h ea l g o r i t h m ( 2 ) an e wr ea m b i g u i t yc h e c k i n ga l g o r i t h m i n c o n s t r u c t i n gr e s ，u s e r s o f t e ni n t e n t i o n a l l yi n t r o d u c es o m eb e n e f i c i a l a m b i g u i t yt os i m p l i f yr ec o n s t r u c t i o n ，a n dm a ya l s ou n c o n s c i o u s l yl e a v es o m e b a n e f u la m b i g u i t yt h a tw i l lh a r mt h ee x t r a c t i o na c c u r a c y h o w e v e r , t h ep r e s e n t d i s a m b i g u a t i o nm e t h o d s f o rr e sc a n n o tm a k ead i f f e r e n c eb e t w e e nt h e s et w ok i n d so f a m b i g u i t i e s i no r d e rt o t a c k l et h i sp r o b l e m ，w es t u d yt h es e g m e n t i n ga m b i g u i t y p r o b l e mi nr e sb yt h ef o l l o w i n gs t e p s ：1 ) g i v et h ef o r m a ld e f i n i t i o n so fs e g m e n t a t i o n f e a t u r e si nr e s ；2 ) p r o p o s eam e t h o dt h a tc a l c u l a t e ss e g m e n t a t i o nf e a t u r e si nr e s b a s e do nas e to f t h e o r e m s ；a n d3 ) g i v et h ef o r m a ld e f i n i t i o no f t h eb a n e f u la m b i g u i t y i nr e sa n dd e s i g nac h e c k i n ga l g o r i t h mf o ri tb a s e do ns e g m e n t a t i o nf e a t u r e si nr e s ， a i m i n ga th e l p i n gu s e r st od e b u g r e s ( 3 ) an e wd a t ae x t r a c t i o nm e t h o df o rc o m p l e x d a t as o u r e e s 埘t l ln o i s e s t h ep r e s e n td a t ae x t r a c t i o nm o d e l so f t e nl a c kt h ee x p r e s s i v ep o w e rf o rc o m p l e x d a t as o u r c e sw i t hn o i s e s i no r d e rt oo v e r c o m e “sd r a w b a c k ，b yd e s c r i b i n gd a t a s o u 3 t 君s u s i n ge x t e n d e dr e g u l a re x p r e s s i o n s ( e r e s ) d e s i g n e db yo u r s e l v e s ，w e p r o p o s ead a t ae x t r a c t i o nm o d e ln a m e da sd a t ae x t r a c t i o nt r e e ( d e - t r e e ) f o rc o m p l e x d a t as o u r c e s 、v i t hn o i s e s g i v eam e t h o df o rc o n s t r u c t i n gl o e a t o r sf o rd a t ao b j e c t s ， 面向复杂数据源的数据抽取模型和算法研究 v i i复旦大学博士学位论文 a b s l l 眦t a r g u eo nt h ec o n d i t i o n so fs e g m e n t i n gd a t ao b j e c t sv i aas e to f t h e o r e m sa n dp r o p o s e am e t h o df o rs e g m e n t i n gd a t ao b j e c t s ，d i s c u s st h el o c a t i n ga b i l i t yo f n o d e s , a n dg i v ea l e g a l i t yc h e c k i n gm e t h o df o rd e - t r e eb a s e do nl o c a t i n ga b i l i t yo fn o d e sa n d s e g m e n t a b i l i t yo f d a t ao b j e c t s 阳l e g a ld e t r e ei sc a l l e da i ll - t r e e ) ( 4 ) an e w d a t ae x t r a c t i o na l g o r i t h mf o rc o m p l e xd a t as o u r c e sw i t hn o i s e s t h ep m s e n td a t a e x t r a c t i o na l g o r i t h mc a n n o ta c c u r a t e l ye x t r a c tc o m p l e xd a t a s o u r c e sw i t hn o i s e s i no r d e rt oo v e f c o m et h i sd r a w b a c k ，w ed e s i g nl - t r e em a t c h a l g o r i t h m i ne x t r a c t i n gd a t ao b j e c t s ，t h i sa l g o r i t h mg i v e su pc o n v e n t i o n a lk e ys e a r c h s t r a t e g ya n da d o p t sat e s t - a n d - b a c k t r a c ks t r a t e g yb a s e d0 1 1t h es e g m e n t a t i o no fd a t a o b j e c t s b yu t i l i z i n gi o c a t o r so nn o d e st oe s t i m a t es e a r c l l i n gp a r t i t i o n sa n dt e s t i n g b i n d i n g so nm a t c h e st oc o r r e c ts e a r c h i n gp a r t i t i o na n df i l t e rn o i s e s ，l t r e em a t c h a l g o r i t h mc a na c c u r a t e l y e x t r a c td a t af r o md a t as o u r c e sc o n t a i n i n g c o m p l e x c o m b i n a t i o no f o p t i o n a l ，n e s t e d ，o r d e r e d ，u n o r d e r e da n dn o i s yc o m p o n e n t s ( 5 ) l - t r e ew r a p p e rg e n e r a t i o nt o o l k i t l - t r e ew r a p p e rg e n e r a t i o nt o o l k i ti n c l u d e st h ef o l l o w i n g ：1 ) t h ee r et h a ti su s e d a sad a t ae x t r a c t i o ns c r i p tl a n g u a g e ；2 ) a l le d i t i n ga n dd e b u g g i n ge n v i r o n m e n tt h a t s u p p o r t s v i s u a l i z e de r ec o n s t r u c t i o n ，e r e l e g a l i t yc h e c k i n ga n dv i s u a l i z e d e x t r a c t i o nr e s u l t se v a l u a t i o n ；3 1t h ex m lf o r m a tf o re x t r a c t i o nr e s u l t t h er e s u l t so f c o m p a r i n gl - t r e ew r a p p e rg e n e r a t i o nt o o l k i tw i t ht h ep r e s e n tw r a p p e rg e n e r a t i o n t o o l k i t ss h o wt h a t l t r e ew r a p p e rg e n e r a t i o nt o o l k i tb e h a v e sw e l li nm a n ya s p e c t s l - t r e ew r a p p e rg e n e r a t i o nt o o l k i th a sb e e na p p l i e dt ob u i l da no n l i n ei n t e g r a t e d b i o l o g i c a ld a t aw a r e h o u s e k e yw o r d s ：d a t ae x t r a c t i o n ，d a t ae x t r a c t i o nm o d e l ，e x t r a c t i o na l g o r i t h m ，c o m p l e x d a t as o u r c e ，d e - t r e e , l - t r e e , n o i s e 面向复杂数据源的数据抽取模型和算法研究 v i i i复旦大学博士学位论文 y7 6 9 7 0 3 面向复杂数据源的数据抽取模型和算法研究 s t u d yo nd a t ae x t r a c t i o nm o d e la n da l g o r i t h m f o rc o m p l e xd a t as o u r c e s 导师 邓绪斌 指导小组成员 禾簪睡囊挚总 朱扬勇教授 施伯乐 汪卫 张亮 教授 教授 教授 第一章绪论 1 1 研究背景 第一章绪论 随着信息技术的飞速发展，互联网上的在线电子文档已经成为一个巨大的信 息源，且数据量仍在高速增长。在这个巨大的信息源面前，人们自然希望获得数 据库系统的支持，以便对感兴趣的数据进行快速方便的查询、分析和报告。然而 常规的数据库技术需要结构化的数据 l r d + 0 2 1 ，而在线电子文档却常以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 g m l ( s t a n d a r dg e n e r a l i z e d m a r k u pl a n g u a g e ，标准通用标记语言) 、x m l ( e x t e n d e dm a r k u pl a n g u a g e ，扩 展的标记语言) 、非标准的展开文件( f l a tf i l e ) 、电子表格等半结构化的形式存 在，而且这些在线电子文档的结构经常是不规则的，不具有预先定义的结构，并 且是动态变化的。这就刺激了围绕这些数据源开发数据集成系统的研究工作。 1 1 1 数据集成系统简介 数据集成系统组合来自不同数据源的数据，目的在于以一个统一的视图提供 给用户使用 l e n 0 2 。近年来，随着w e b 数据集成研究的深入开展，使得数据集 成系统成为研究的热点 h a l 0 3 1 。自9 0 年代中期起，数据库和人工智能学界在数 据集成的研究方面取得了大量的研究成果。这些研究成果集中在模式m e d i a t i o n 语言、查询处理、查询优化和查询执行等方面 t a 0 0 4 】。 数据集成系统目前有数据仓库和包装器中介器( w r a p p e r m e d i a t o r ) 两种 实现方案【a b s 0 0 】。数据仓库方案 s b b + 0 0 ，e a 0 3 事先将所涉及数据源中的相关 数据全部抽取到本地进行集成，适用于对数据即时性要求不高的情形。数据仓库 方案的关键是数据抽取、转换和装载( e x t r a c t i o n ，t r a n s f o r m a t i o na n dl o a d ，简称 e t l ) 以及增量更新技术。包装器中介器方案 s s 0 3 ，p a r 0 2 适用于对数据即时 性要求比较高、不可能或者很难从数据源抽取所有数据的情形。在基于包装器 中介器的数据集成系统中，数据并不事先抽取到本地，而是在客户发出查询请求 的时候，先由中介器将查询分解成子查询发送到相关的数据源包装器，再由包装 器到数据源中抽取回答子查询的相关数据，最后由中介器将来自不同包装器的相 关数据组合成查询结果返回给客户。由于不同数据源的数据格式可能有很大差 别，这就要求包装器将抽取结果“包装”( 即映射) 成一致化的数据格式。 在数据集成系统的上述两种方案中，需要解决的基础问题是数据抽取问题。 虽然数据抽取问题在数据仓库方案中被称为e t l ，在包装器中介器方案中被称 为“包装”，但从底层实现的角度看，它们本质上是一样的。例如，只需适当地 调整查询条件，能够实时回答查询的包装器也可以为数据仓库抽取数据。因此本 面向复杂数据源的数据抽取模型和算法研究 复旦大学博士学位论文 第一章绪论 文并不严格区分这两个概念。 由于数据源的多样性和复杂性，如何快速准确地为各种数据源建立包装器是 数据集成系统实现的关键。这一课题已成为计算机界研究的热点，也是本文研究 的核心问题。 1 , 1 2 数据抽取问题简介 文献 l r d 0 2 给数据抽取问题下了一个非常好的定义：给定数据源s ，确定 一个s 到数据库盹的映射刑，该映射从s 中抽取数据对象并将这些数据对象按 一定的格式组装( p o p u l a t e ) 到览中。实现这一映射的计算机程序就是数据抽取 程序，俗称包装器( w r a p p e r ) l r d 0 2 】。 要构造一个可以正常工作的包装器，必须回答下列问题： 要在数据源中找怎样的数据对象? 数据源中的数据对象可以是简单的字符串，也可以具有树形结构，甚至具 有有向图结构( 其中结点又称数据类型) 。为使包装器具有通用性，通常用数据 抽取模型来描述数据源中数据对象的结构。 如何在数据源中找到这些数据对象? 通常用抽取规则驱动一个通用抽取算法在数据源中搜索与抽取规则匹配的 数据对象。 用什么格式组装找到的数据对象? 通常用符合某个数据库模式的格式来组装找到的数据对象，这个数据库模 式可以是关系的、对象关系的、面向对象的或是x m l s c h e m a 的。 如何将找到的数据对象组装到数据库中? 通常的方法是用一组映射规则描述数据类型到数据库字段之间的对应关 系。当抽取算法找到一个数据对象时，先用映射规则根据数据对象所属的数据类 型找到对应的数据库字段，然后将这个数据对象组装到这个字段中。一般并不单 独设计组装算法，数据对象的组装通常在抽取算法中进行f a d e 9 8 ，l r d 0 2 ， l d r + 0 2 1 。因此抽取算法有时也称为抽取和组装算法。 如何生成和维护数据抽取过程所需的元数据? 为了使数据抽取和组装算法正常工作，必须向它提供数据抽取模型、抽取 规则、数据库模式和映射规则等参数，本文将这些参数称为元数据( 文献 v d 0 1 1 将数据仓库系统中的元数据定义为“用于支持数据仓库管理和有效应用的任何信 息”。本文的元数据和这一定义类似，不同之处是本文的元数据仅涉及数据抽取 问题) 。一个数据源需要用一套元数据进行描述。由于数据集成系统往往会涉及 大量的数据源和相关元数据，使得生成和维护这些元数据的工作成了沉重的负 面向复杂数据源的数据抽驭横型和算法研究 2 复旦大学博士学位论文 第一章绪论 担。因此元数据的生成和维护问题对于数据集成系统而言很值得研究，例如文献 【v d 0 1 和 v a d 0 给出了数据仓库系统中各种元数据管理方法的综述。 1 1 3 本文的研究目标 本文的研究是围绕一个生物数据集成系统的构建工作而开展的。在所有亟 待处理的数据源中，生物数据是增长最快的在线资源之一。随着生物信息学研究 的纵深开展，这一资源显得日益重要。如何围绕这些生物数据源构建数据集成系 统，为生物学家搭建方便的查询分析平台，已成为计算机界研究的热点 d r 0 4 ， m l l + 0 4 ，d m b + 0 4 1 。构筑这一平台的基础是解决生物数据源的抽取问题，本文 的工作正是为了解决这一问题而开展的。为了阐述本文的研究目标，在此先结合 数据抽取问题，对生物数据源的特点进行简单介绍。 与其他应用领域的半结构化数据源相比，生物数据源有下列特点： 多样性 全球有价值的生物数据源有上千种 c a 0 0 4 ，抽取时一种数据源要用一套元 数据来描述，元数据的生成和维护工作量相当大。 复杂性 首先，数据对象结构具有复杂性。生物数据源中欲抽取的数据对象往往具有 多层嵌套结构，数据对象的成分可以缺失、多次重复、有序出现或者无序出现， 甚至在较高层次上是有序的，在较低的层次上却是无序的( 即有序成分中包含着 无序的子成分) 或反之( 即无序成分中包含着有序的子成分) ，构成了有序成分 和无序成分间的复杂嵌套组合。这些特点构成了数据对象结构的复杂性。 其次，抽取规则具有复杂性。生物数据源常用非标准标签对数据对象进行分 隔，不同的数据源所用的标签集及其语义不同，许多需抽取的数据项没有恰当标 签，抽取时只能靠上下文甚至靠自身的特征来判断。更具挑战性的是，对于某些 生物数据源而言，说明书中指定的分隔字符串可能会在数据对象内容中出现，导 致歧义( 即数据源中含有噪声成分) 。这些特点构成了抽取规则的复杂性。 第三，映射规则具有复杂性。其一，由于不同的生物应用关注不同的信息层 次，组装到数据库字段的数据对象可能来自数据源中多个区域，组装时需要将它 们合并成一个字段值( 例如，在如图1 所示的g e n b a n k 生物序列展开文件中， 可能需要将 a u t h o r s ”、“t i t l e ”和“j o u r n a l ”后的字符串合并成一个参考文献 项。实际应用中需要合并的情况非常多) ；其二，生物数据源中一般都含有可用 作主键的数据项( 例如“l o c u s ”后的 a a 0 0 0 0 2 4 ”) ，因此需要包装器在输出抽取 结果前用这个数据项作为主键值替换掉系统生成的整型i d 。合并和主键替换等 扩展操作构成了映射规则的复杂性。 面向复杂数据源的数据抽取模型和算法研究 复旦大学博士学位论文 第一章绪论 易变性 目前生物学的许多研究领域仍然处于发展阶段，生物数据源中的数据常常是 不完整的，并且经常发生前后不一致的情况。随着生物学研究的进展，生物数据 源的结构会发生变化，即修改一些标签的表达结构或增加一些新标签。 某些文档非常庞大 一个文档通常含有多个源自同一语法的条目( e n v y ) ，但某些文档可能会过 于庞大，超出了现有包装器的处理能力。例如g e n b a n k 生物序列展开文件总 计已达1 7 0 g b ，并以每1 4 个月翻一番的速度快速增长 b k l + 0 4 。这样的数据源 应该用文本流方式逐条目地进行处理，而不能将其全部读入内存或多次扫描外存 进行预处理。 抽取准确度要求很高 由于生物学研究仍然处于发展阶段，目前还不能分析的数据可能构成未来 研究的基础，因此生物数据集成系统对生物数据抽取的准确度要求非常高，不允 许由于抽取方法的简化而导致的信息损失。 l o c u sa a 0 0 0 0 2 45 4 3b pm r n al i n e a re s t d e f i n i t i o nm 9 3 3 e 0 6 r ls o a r