（计算机应用技术专业论文）网络数据源模式识别方法及策略研究.pdf

k 叼 0 c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g t h er e s e a r c ho fn e t w o r kd a t as o u r c e p a t t e r nr e c o g n i t i o nm e t h o da n ds t r a t e g y c a n d i d a t e ：l i uf u j i a n g s u p e r v i s o r ：p r o f w a n gn i a n b i n a c a d e m i cd e g r e e a p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo f s u b m i s s i o n ：j a n u a r y1 ，2 0 1 0 d a t eo f o r a le x a m i n a t i o n ：m a r c h1 2 ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 92 唧98am 8 iiiii舢y 一 n j i 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：训伤江 日期：扣l o 年弓月f 琴日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可q 任授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 筮a - y - ) ：- 鸭儿 日期：旦d p 年弓月i 妄日 导师( 签字) ：乏会文 如f o 年弓月眵日 ，、 “ n 合尔滨t 程大学硕+ 学位论文 摘要 当今，网络上存在许多在线的可搜索数据库，称为网络数据库。这些数 据库的数量以惊人的速度增长，网络已经快速的被“加深”了。由于网络数 据库中的数据隐藏在查询表单背后，不能被传统的搜索引擎索引，所以这种 网络数据库又被称作深层网络，而含有查询表单的网页被称作网络数据源。 不像传统的以提供链接为导航的表面网络，这种深层网络支持以查询的方式 访问隐藏在查询接口背后的数据库。在2 0 0 0 年发布的调查中，深层网络中蕴 含的信息量超过表面网络上千倍，而且这个比例仍在持续不断地上升。u i u c 大学曾经在2 0 0 4 年对整个深层网络的规模作了一次估计，结果表明深层网络 中可访问的网络数据库的数量超过了4 5 万个。对于这些实际上数量无限的信 息资源，大规模集成深层网络是必需的而且意义深远。 针对被“保护”起来的数据，查询接口就成为了访问深层网络的入口。 这些接臼，例如：查询表单，通过查询条件访问背后的数据实体。为了模型 化和集成化网络数据库，首要问题是理解查询表单。针对于深层网络数据集 成的研究需要，基于国内外有关网络数据源模式识别的研究成果，本文提出 了一种识别网络数据源模式的方法。该方法建立在统计分析的基础上，通过 观察大量含有查询表单的数据源，发现查询表单表现的一般结构，从而确定 可能存在的表单语法。虽然来源不同，但是表单语法引导着查询表单的生成。 因此，本文建立了识别网络数据源模式的系统框架，通过设计一个代码序列 语法和一个自动机解析器实现对表单语法的捕获，进而理解并自动提取网络 数据源表单信息。实验结果表明这种方法是有效的，识别网络数据源模式的 整体准确率和整体召回率均达到9 4 以上。 关键词：网络数据源：模式识别；深层网络：代码序列语法 一 一。l ， i 哈尔滨t 程大学硕十学位论文 a b s t r a c t n o w a d a y s ，t h e r ea r em a n ys e a r c h a b l ed a t a b a s e so n l i n ew h i c ha r ek n o w na s t h ew e bd a t a b a s e s t h en u m b e ro fw e bd a t a b a s e sh a se x p e r ie n c e da l li n c r e a s ea ta s u r p r i s i n gr a t e ，a n dt h ew e bh a sb e e nr a p i d l y “d e e p e n e d ”t h ed a t ai nt h ew e b d a t a b a s e sa r eh i d d e nb e h i n dq u e r yf o r m sa n da r en o ti n d e x e db yat r a d i t i o n a l s e a r c he n g i n e 。s ot h i sk i n do fw e bd a t a b a s e si sn a m e dd e e pw e b ，a n dt h ew e b p a g e sc o n t a i n i n gq u e r yf o r m sa r ec a l l e dt h en e t w o r kd a t as o u r c e s u n l i k et h e s u r f a c ew e bp r o v i d i n gl i n k - b a s e dn a v i g a t i o n ，t h e s e “d e e pw e b s o u r c e ss u p p o r t q u e r y b a s e da c c e s st h ed a t aw h i c ha r eh i d d e nb e h i n dt h e i rq u e r yi n t e r f a c e s t h e i n v e s t i g a t i o ni n2 0 0 0i n d i c a t e dt h a tt h ea m o u n to fi n f o r m a t i o ni nd e e pw e b w a s t h o u s a n d so ft i m e sm o r et h a nt h a ti ns u r f a c ew e b ，a n dt h er a t i oc o n t i n u e dt or i s e t h eu n i v e r s i t yo fi l l i n o i sa tu r b a n ah a dm a d ea ne s t i m a t eo ft h ee n t i r ed e e pw e b i n2 0 0 4 t h er e s u hs h o w e dt h a tt h en u m b e ro fa c c e s s i b l ew e bd a t a b a s e sw a sm o r e t h a n4 5 0 ，0 0 0 r e g a r d i n gt h e s ei n f i n i t ei n f o r m a t i o nr e s o u r c e s ，t h el a r g e s c a l e i n t e g r a t i o no fd e e pw e b i se s s e n t i a la n ds i g n i f i c a n c ep r o f o u n d g u a r d i n gd a t ab e h i n dt h e m ，s u c hq u e r yi n t e r f a c e sa r et h e “e n t r a n c e t od e e p w e b t h e s ei n t e r f a c e s ，o rh t m lq u e r yf o r m s ，e x p r e s sq u e r yc o n d i t i o n sf o r a c c e s s i n go b je c t sf r o md a t a b a s e s b e h i n d f o rm o d e l i n ga n di n t e g r a t i n gw e b d a t a b a s e s ，t h ev e r yf i r s ts t e pi st o u n d e r s t a n d ”w h a taq u e r yi n t e r f a c es a y s f o r t h er e s e a r c hn e e do fd e e pw e bi n t e g r a t i o n ，b a s e do nt h ed o m e s t i ca n df o r e i g n r e s e a r c hr e s u l t sa b o u tt h ep a t t e mr e c o g n i t i o no fn e t w o r kd a t as o u r c e s ，t h i sp a p e r i n t r o d u c e sam e t h o dw h i c hi se s t a b l i s h e do nt h eb a s i so ft h es t a t i s t i c sa n da n a l y s i s b yo b s e r v i n gal a r g en u m b e ro fw e bp a g e sc o n t a i n i n gq u e r yf o r m s ，t h ea u t h o r f o u n dt h eb a s i cs t r u c t u r eo ft h e ma n dc o n f i r m e dt h ee x i s t e n c eo faf o r ms y n t a x w h i c hg u i d e st h ec r e a t i o no ft h e m ，a l b e i tf r o md i f f e r e n ts o u r c e s s ot h ea u t h o r d e v e l o p e das y s t e mf r a m e w o r kf o rr e c o g n i z i n gn e t w o r kd a t as o u r c e s p a t t e r n s ， c a p t u r e dt h ef o r ms y n t a xt h r o u g had e r i v e dg r a m m a r - c o d es e q u e n c eg r a m m a r ， 一 哈尔滨t 程大学硕十学何论文 a n dd e s i g n e da na u t o m a t o np a r s e rt ou n d e r s t a n dq u e r yf o r m sa u t o m a t i c a l l y t h e e x p e r i m e n t a lr e s u l t si n d i c a t e dt h i sm e t h o di sv a l i d ，a n db o t ht h eo v e r a l lp r e c i s i o n a n dr e c a l la c h i e v ea b o v e9 4 k e yw o r d s ：n e t w o r kd a t as o u r c e ；p a a e mr e c o g n i t i o n ；d e e pw e b ；c o d e s e q u e n c eg r a m m a r c 、 哈尔滨t 程大学硕十学何论文 目录 第1 章绪论1 1 1 课题研究背景及意义1 1 1 1 课题的背景1 1 1 2 课题的意义2 1 2 研究现状3 1 2 1 深层网络的研究现状3 1 2 2 网络数据源模式识别研究现状6 1 3 主要研究内容和预期研究成果”8 1 4 本文的组织结构“8 第2 章网络数据源模式识别相关研究1 0 2 1 网络数据源模式识别的主要问题和方法1 0 2 1 1 网络数据源模式识别的主要问题1 0 2 1 2 一种网络数据源模式识别方法1 l 2 2 模式匹配1 3 2 2 1 模式匹配的定义及分类1 3 2 2 2 模式匹配的方法1 4 2 3 本章小结1 7 第3 章网络数据源模式识别方法及策略1 9 3 1 研究概述1 9 3 2 网络数据源模式识别框架2 2 3 2 1 网络数据源模式识别框架”2 2 3 2 2 相关概念描述”2 2 3 3 解析网络数据源模式2 6 3 3 1 观察查询表单2 6 哈尔滨t 稃大学硕十学位论文 3 3 2 发现协定结构2 9 3 3 3 假设表单语法3 0 3 3 4 解析方法及策略3 2 3 4 代码序列语法3 2 3 4 1 代码序列语法的定义3 2 3 4 2 代码序列语法规则3 3 3 4 3 最大匹配原则3 4 3 5 自动机解析器3 5 3 5 1 有穷自动机的工作原理3 5 3 5 2 表单元素序列3 7 3 5 3 基于代码序列语法规则构建有穷自动机3 7 3 6 本章小结3 8 第4 章网络数据源模式识别系统及实现3 9 4 1 系统设计目标3 9 4 2 网络数据源模式识别系统体系结构”3 9 4 3 基于代码序列语法的系统功能实现4 1 4 3 1 过滤器4 1 4 3 2 分析器4 4 4 3 3 分组器”4 7 4 3 4 构造器4 7 4 4 应用平台及工具5 0 4 5 程序结构设计5 0 4 6 本章小结5 4 第5 章实验及结果分析5 5 5 1 数据集”5 5 5 2 实验衡量标准5 5 5 3 实验结果分析5 6 卜 哈尔滨t 程大学硕十学何论文 5 4 代码序列语法与2 p 语法5 8 5 5 本章小结5 9 结论一6 0 参考文献6 1 攻读硕士学位期间发表的论文和取得的科研成果6 6 致谢6 7 哈尔滨丁稗大学硕十学伊论文 1 i v i i i i i 宣i i i i i 置i 宣i 宣i 宣宣i i i i i i 宣宣i i i i i i i i i i i 暑i i i 宣i i i i i i i i i 暑i 誓薯i i i 宣萱i i i i i i 萱i i 第1 章绪论 1 1 课题研究背景及意义 1 1 1 课题的背景 随着互联网技术的飞速发展，网络数据库技术已得到广泛应用。目前依 托网络数据库的在线网站的数量正在急剧增长，这些网站可以根据用户的需 要，将后端数据库中数据以动态网页的形式展现给用户，这些网页不能被传 统的搜索引擎检索到，所以又被称为看不见的网页。d r j i l le l l s w o r t h 在1 9 9 4 年首次提出了“看不见的网页”的概念，但考虑到用“看不见来描述网页 不准确，所以他在2 0 0 0 年以后发表的文章中使用深层网络以取代看不见的网 页，并把不属于深层网络的页面归为表面网络。 通过网页中的超链接，传统的搜索引擎可以检索到大量的网页，但是在 互联网上大约还有2 1 3 的页面由于缺乏指向的超链接而没有被搜索引擎检 索到，这两部分的网页都属于表面网络的范畴。而对于深层网络，文献 2 中 认为深层网络是指网络中不能被传统的搜索引擎索引到的那部分网页，特别 是指那些通过查询动态生成的页面：然而，随着搜索爬虫能力的增强，使得 深层网络这个概念变得复杂且不容易界定，所以很难提供一个共识的定义。 文献 3 】对深层网络提出了一个较为完整的描述：深层网络是指网络中可访问 的在线数据库，简称为网络数据库或w d b ，其内容存储在真正的数据库中。 这些内容只有在被查询时才会由网络服务器动态生成页面，并把生成的结果 页面返回给用户，因此这些页面并没有超链接指向，这也是和那些通过网址 或超链接访问的静态页面的本质区别。 在2 0 0 0 年，b r i g h tp l a n e t 公司对深层网络做了一次统计，并发布了深层 网络的白皮书【4 】：深层网络蕴含的信息量是表面网络的4 0 0 到5 0 0 倍；深层 网络蕴含的信息量比表面网络质量更高：对深层网络的访问量高出表面网络 1 5 ；深层网络的增长速度远高于表面网络；深层网络中有超过5 0 的内容 是面向特定领域的，并且这个深层网络几乎覆盖世界中所有领域；除此之外， 0 哈尔滨t 稃大学硕十学伸= 论文 深层网络中9 5 的信息是免费的，可以公开访问。在2 0 0 4 年4 月，u i u c 大 学对整个深层网络做了一次估算，以1 0 0 0 0 0 0 个随机生成的i p 为样本进行实 验从而得出如下数据：整个深层网络大约有3 0 7 0 0 0 个站点、4 5 0 0 0 0 个后台 数据库( 其中约4 5 为结构化数据库) 和1 2 5 8 0 0 0 个查询接口。 深层网络的信息来源于后台数据库，其中绝大部分是结构化的数据。这 些数据“隐藏”在查询接口的后面，存储在a c c e s s 、o r a c l e 、s q ls e r v e r 、 d b 2 等关系数据库系统中。当需要检索数据时，必须使用本网站的检索工具 进行查询。在互动搜索表单中输入检索内容或选择搜索选项，数据库响应请 求并将相应的检索结果按照一些规则进行排序显示在特定网页上。联机检索 数据库一般可分为两类：自由获取的公共数据库以及需要付费的数据库。由 于搜索引擎的爬虫程序尚不具备在查询表单中自动填写或选择所需字段信息 的能力，不能提交给数据库搜索；对于一些必须使用用户名和密码登录的网 站，搜索引擎的爬虫程序同样没有足够的智能注册登录系统，因此，无论是 何种类型的数据库，传统的搜索引擎都无法访问其中的数据，用户只能通过 填写查询表单获取数据库中的数据。网上可检索的数据库是深层网络的重要 组成部分，蕴含着海量且高质量的信息资源。为了有效地利用深层网络资源， 必须要对深层网络数据进行大规模的集成。数据集成的基本步骤主要包括： 网络数据库的发现、网络数据源模式( 查询接口模式) 抽取、网络数据库的 分类、查询接口的集成、查询转换、查询结果的抽取、查询结果的整合等七 个方面1 3 】。其中，网络数据源模式抽取是整合深层网络资源的首要工作，想 要大规模的集成，自动提取网络数据源信息的能力是必不可少的。 1 1 2 课题的意义 深层网络中蕴含着海量的数据，且这些数据具有较高的质量，它支持以 查询的方式访问隐藏在查询接口背后的数据库，所以大规模集成网络数据库 是必需的而且也是一种挑战。针对被“保护”起来的数据，查询接口就成为 访问网络数据库的入口。这些接口( 例如：h t m l 查询表单) 通过查询条件 访问背后的数据实体。 网络数据源模式，即查询接口模式，是一组领域相关的属性集合，通过 哈尔滨丁稗大学硕十学伊论文 对其中若干属性赋值形成一个对该查询接口所代表网络数据库的查询。为了 模型化和集成化网络数据库，第一步是要理解一个查询接口说了什么，也就 是一个数据源支撑什么样的查询能力。查询接口模式可以看作是建立在对应 网络数据库上的一个视图。对查询接口模式的抽取是指对查询接口属性的获 取与分析f 6 】，其主要目的是为了下一步的网络数据库分类和查询接口集成。 获取查询接口属性后，需要把查询接口形式化地表示出来以便于下一步 的处理。表示查询接口的形式与下一步的应用目的相关，如果是为了对网络 数据库分类，则倾向于关注查询接口的整体信息，即查询接口反映的领域信 息或领域特点：如果是为了查询接口集成，则倾向于关注查询接口内各个属 性的细节信息以及查询接口元素间的语义关系，即找到不同查询接口之间元 素及属性的匹配关系i t 。最有效的方法是将查询接口看作是一个接口元素的 集合，每个元素包含着一些属性。文献 8 提出了一种形式化的表达方式：将 整个查询接口表示为一个三元组，其中包括查询接口所在网站的相关信息、 构成查询接口的元素集合，由元素形成的查询条件之间的关联关系。元素集 合包含对每个接口元素信息的描述，每个元素表示为一个七元组，包括元素 的名称、元素在查询接口中的布局信息、元素的域类型、元素的缺省值、元 素值的类型、元素值的单位。 由于网络上数据源数量多而且在不断变化，所以对于很多事情来说，例 如：通过查询接口模型化网络数据库，聚类查询接口州，匹配查询接口l 1 0 1 或建 立统一的查询接口【1 1 1 ，自动提取能力是必不可少的。然而，目前数据源信息 的提取基本上还是手工完成，所以这被看成是大规模集成的首要障碍【1 2 j 。 本课题以实现深层网络数据集成为背景，研究一种网络数据源模式的识 别方法及策略。该方法能够自动的提取数据源接口属性信息且具备较高的准 确率和召回率。自动提取能力提高了对海量查询接口的处理效率，并为下一 查询接口集成提供了格式化的信息。 究现状 海量的可供访问的信息，并且还在迅速地增长。这些 哈尔滨t 程大学硕十学伊论文 信息来源于查询接口背后的网络数据库。由于深层网络数据的异构性和动态 性，有效地把这些信息加以利用是一件具有挑战性的工作。深层网络技术至 今仍然是一个新兴的研究领域，其中包含若干需要解决的问题。对深层网络 研究的根本目的是提供给用户一个统一接口来查询及获取分布在整个网络上 各个领域丰富的信息。目前国内外对深层网络技术的研究主要集中在对后台 数据库的访问。传统的搜索引擎无法提供对深层网络的搜索服务，分类目录 服务是一种检索深层网络的方法，国内外也有一些深层次的网络分类目录服 务网站，但基本上是手工处理，还无法实现自动化或半自动化索引处理。 1 国外深层网络的研究现状 ( 1 ) 华盛顿大学计算机科学系开发的s h o p b o t 【1 3 j 是一个能并行访问多个 商店同时对商品进行比较的“软件机器人”，它主要针对以表单形式提供查询 的页面，并以表格的形式显示检索到的产品信息，其中结合了启发式搜索、 模式匹配和归纳式学习等技术从结果页面中抽取信息。s h o p b o t 的运行分为 两个阶段：离线学习阶段和在线比价阶段。在学习阶段，系统分析每一个购 物网站，将分析结果进行符号化描述，然后在比价阶段，利用获得的符号化 描述，从网站上提取信息，找到用户指定的最低价格的产品。 ( 2 ) 哥伦比亚大学的p a n a 昏o t i s 、g i p e i r o t i s 等人组成的q p r o b e r 小组【1 4 】 提出了一种自动地将w e b 页面所连接的后台数据库进行分类的方法。该方法 采用类似于雅虎的网络分类目录体系来组织分类的结果，基本思路是：首先 用一组预先分好类的文档训练一个基于规则的文档分类器，然后抽取分类器 规则和基本u r l 组合成查询u r l ，对后台数据库进行查询探测，最后根据 类目体系中每个类目对应的返回结果总数来确定数据库所隶属的类目。其研 究只集中在对文档数据库的分类，而大量的深层网络数据库提供的内容是结 构化的数据。 ( 3 ) 斯坦福大学的h i w e t l 5 3 ( h i d d e nw e be x p o s e r ) 是s r i r a m 等人提出的 一个抽取动态信息的实验原型，也可以认为h i w e 是一种可以抽取深层网络 信息的爬虫。h i w e 的基本思想是分析每个表单元素，并提取某些类型的描 述性信息或标签，从而达到自动处理、提交表单的目的。h i w e 使用一种称 为“基于编排的信息抽取技术 ( l a y o u t b a s e di n f o r m a t i o ne x t r a c t i o n t e c h n i q u e ，l i t e ) 从检索页面和响应页面处理和抽取有用的语义信息。在这 4 哈尔滨t 稃大学硕十学何论文 个系统中，爬虫管理器主要负责搜集含有查询表单的w e b 页面。它简单分析 下载的w e b 页面，将包含表单的页面交由表单处理器处理。表单处理器首先 从页面中提取表单，然后从预先准备好的数据集中选择数据填写表单，并调 用页面中的提交，由爬虫管理器下载响应的结果页面。该方法要求用户事先 准备好相应的表单数据集，每个表单项只跟一个文本相关联。但是，该方法 不能从全局的观点来处理表单项，且不能处理i a v a s c r i p t 脚本，而且整个过程 需要人工辅助完成，因此存在较大的局限性。 ( 4 ) 伊利诺斯大学的m e t a q u e r y t 】研究小组为有效获取网络上结构化的 信息源，开发了一个元查询系统( m e t a q u e r y ) t n ，用于帮助用户有效地、统一 地发现和查询网络数据库。m e t a q u e r y 系统将搜索接口视为一种视觉语言 ( v i s u a ll a n g u a g e ) 。通过使用统计概率的方法获取隐藏的模式模型，但是他 们的应用只考虑到了属性标签，忽略了搜索接口中的其他有用的信息，而这 些信息在查询接口的构造过程中是很有效的，并且没有从语义的角度来考虑 属性之间的关系，所以准确性得不到相应的保证。 m e t a q u e r y 系统包括m e t a e x p l o r e r 和m e t a i n t e g r a t o r 。m e t a e x p l o r e r 项目 致力于发现、模型化和重构网络数据库，从而建立一个可搜索的数据源知识 库。该项目开发了一个网络数据库搜索引擎，它可以有效地发现网络上的数 据库，并设计模型来描述这些数据库；而且还设计了多个包装器用于自动抽 取这些模型中的参数，重组和索引检索到的网络数据库。另一方面， m e t a i n t e g r a t o r 项目致力于集成在线的数据源。通过选择数据源、查询转换和 模式集成从而建立m e t a i n t e g r a t o r 。与传统的信息检索不同，m e t a q u e r y 系统 是动态的，即可以将实时发现的新数据源加入到系统中，并动态选择数据源 将用户查询进行相应转换，从而获取用户查询结果。 2 国内深层网络的研究现状 目前国内对深层网络的研究还处于学习和探索阶段，在该领域做的比较 突出有。 ( 1 ) 人民大学的孟小峰等人提出了深层网络数据集成框架，该框架共分 为三个主要的模块：查询接口集成模块、查询处理模块和查询结果处理模块。 查询接口集成模块提供了一个统一的查询接口，以便它能同时向同一领域内 的多个查询接口提交查询，即实现同时访问属于同一领域的多个网络数据库 哈尔滨t 程大学硕十学伊论文 的目的。该模块共有4 个主要的子模块：网络数据库的发现、查询接口模式 的抽取、基于领域网络数据库的分类和查询接口集成。查询处理模块将用户 在集成的查询接口上填写的查询转化到对各个网络数据库本地查询接口的查 询。查询结果处理模块将各个网络数据库返回的结果抽取并合并到一个统一 的结构化的模式下。该模块包括结果的抽取、结果的注释和结果的合并【，】。 ( 2 ) 人民大学开发的j o b t o n g 州系统是一个面向工作领域的信息集成系 统。其框架就是上文所提到的深层网络数据集成系统框架【1 9 】，其核心是基于 配置文件的深层网络数据集成系统。j o b t o n g 集成系统的核心思想是：利用针 对每一个网站的配置文件，对深层网络进行数据集成。它的基本工作机制类 似于基于w r a p p e r 的数据集成系统。但是有两点不同：第一，j o b t o n g 基于 配置文件的集成系统将某一个具体网站的数据集成过程抽象出来，这样集成 程序是统一的，而针对网站只需要写配置文件，并且这个配置文件与数据库 属性是相关联的；第二，j o b t o n g 的这种工作机制比基于w r a p p e r 的集成系 统要节省内存，同时能够使用多线程进行爬取。该系统先将深层网络上工作 信息领域的数据爬取下来，放在本地数据库中。用户通过j o b t o n g 网站提供 的查询界面，可以查询自己想要申请的职位信息，而此查询关键字会被提交 到本地服务器上进行处理，然后将查询到的结果返回给用户。由于对于用户 的查询来说，直接在本地进行处理，无需再将查询分派到网络上的深层网络 相应查询接口查询，因此，能够大大提高查询速度，缩短用户等待时间。 ( 3 ) 上海交通大学宋晖1 2 0 1 等人提出基于标签树的对象抽取方法( t a g t r e e - b a s e do b j e c te x t r a c t i o n ) ，自动提取深层网络表单中的信息，并在此基础上给 出了结构化的深层网络信息检索算法。 ( 4 ) 苏州大学的郑冬冬，赵朋朋等人也对深层网络进行了相关的研究， 在爬虫研究与设计1 2 1 】一文中提出使用启发式规则集和领域本体知识库来 自动发现相关表单，同时自动填写表单及收集相关结果页面。 1 2 2 网络数据源模式识别研究现状 本文谈至t j o o 网络数据源是指含有查询接口的w e b 页面，而网络数据源模 式即查询接口模式，该模式常常以一种查询表单的形式表示出来。深层网络 6 哈尔滨t 稃大学硕十学伊论文 查询接口是获取后台数据库内容的唯一入口。查询接口往往由不同的h t m l 控件组成，常见控件元素类型有：文本框( t e x t b o x ) 、单选按钮( r a d i o ) 、复 选框( c h e c k b o x ) 和选择列表框( s e l e c t ) 等。查询接口允许用户键入或选择 相应的信息并提交，从而查询后台数据库中的数据。深层网络查询接口是嵌 在h t m l 页面中的，由标签名和对应的元素构成。查询接口上的按钮包括了 连接后台数据库的查询方式，可以表示为对象的操作方法。目前对网络数据 源模式的识别，人们普遍采用的是基于文本与查询元素的位置关系从而建立 一些推论或者人工预先从大量网页中总结出来一些常用的位置关系的模板， 例如：人们认为最接近查询元素的文本就应该是它的标签。 查询接口抽取 2 2 2 5 1 已经得到了广泛的研究。r a g h a v a n l ，5 1 等人提出了基于临 近和候选队列的原则进行一对一结合的方法，随后z h a n g 2 , j 等人通过观察， 发现这些查询接口似乎存在着一些固定的结构，所以他们假设在这些查询接 口中存在着一种隐含的语法结构，并将查询接口看成是一种有着固定语法的 隐含的表达语言，这样对接口模式的识别问题就转化成了对这种隐含语言的 解析问题。为了发现这些隐含的语法结构，他们观察了大量含有查询接口的 网页，分析出了一些固定结构，并且这些结构的数量随着网页数量的增加呈 收敛趋势。为了能够准确地从一个具体的查询接口中将表示属性的各个元素 的组合方式识别出来，他们通过构建解析树对整个查询接口进行解释，确定 它们的语义角色，并利用优先级解决分组方式之间存在的冲突。 除了考虑出现在查询接口中的这些标签和元素，h a ih e l 2 7 2 8 1 等人还发现， 在查询接口中存在一些隐含的语义信息。通过观察，他们提出了类似于值的 类型，领域类型，查询元素之间关系的推论，并结合元素在页面中的位置关 系提出一种自动识别这些隐含的语义信息的算法，以便将这些语义信息变成 机器可以识别的信息。通过使用这些方法来指导机器识别查询条件，但是由 于没有考虑文字本身所携带的语义信息，在一些没有给出推理并且存在歧义 的情况下往往会产生错误。 依赖于结构的规律性，提取网页潜在结构的工作，其中还包括已经得到 广泛研究的包装器归纳技术 2 3 2 9 3 0 1 。c r e s c e n z i t m 和m r a s u l 3 0 1 研究的网页均由相同 的背景模板产生，所以在他们的环境中，语法的存在不是一个假设，而是实 际存在的。其次，在其他几个工作中1 8 1 5 2 s ，理解查询接口这个问题被提到过， 哈尔滨t 稃大学硕十学伶论文 ；| i i ii i i i i i i i i i | 但没被作为焦点。也有不少工作，依赖于自动填写查询表单f j 3 ： j 】或处理简单 的关键字查询表单或使用选择列表作为简单集成：特别是，文献 1 5 建议用 简单的启发式信息，如从接近和邻近两方面配对表单中的元素和文本。 1 3 主要研究内容和预期研究成果 本文的研究内容包括，网络数据源( 网页表单) 模式自动识别方法及策 略研究。通过深入分析大量网页表单，发现查询表单表现的固定结构，从而 确定可能存在的表单语法。虽然来源不同，但是表单语法引导着查询表单的 生成。为此本文将提出一种新的网络数据源模式识别方法并建立提取查询表 单信息的系统框架，通过开发一个派生语法和一个解析器实现对表单语法的 捕获，进而理解并自动提取表单信息。 本文的主要研究目标有，针对于深层网络数据集成的研究需要，基于国 内外有关网络数据源模式识别的研究成果，通过深入分析网络数据源模式结 构，提出一种新的网络数据源模式识别方法。由于网络上数据源数据量多且 在不断变化，所以该方法需要自动提取表单信息的能力，并具备高准确率。 为了便于深层网络数据接口模式集成，本文将数据源的解析结果以x m l 的 形式输出。 1 4 本文的组织结构 本文共分五章，结构安排如下。 第l 章绪论，介绍课题的研究背景和意义。介绍了深层网络和表面网络 的定义，网络数据源接口作为访问深层网络资源的唯一入口，对网络数据源 模式的识别就成为集成深层网络资源的首要问题。因此，本章阐述了深层网 络和网络数据源模式识别的研究现状。 第2 章介绍了与网络数据源模式识别相关的研究，其中包括网络数据源 模式识别的主要问题和目前较为流行的识别方法，模式匹配的定义和方法以 及基于本体的模式集成方法。 第3 章是本文的核心。在前两章理论研究的基础上，本章通过观察分析 大量含有查询接口( 即表单) 的网页，从而发现“表单语法”规范表单的构 哈尔滨t 程大学硕十学何论文 成，并且表单元素在网页上的分布与它们在表单代码中的顺序存在一定的关 系。根据这些特征，本章设计了一个代码序列语法和一个自动机解析器，用 于识别网络数据源模式。 第4 章主要介绍网络数据源模式识别系统。本章提出一种新的网络数据 源模式识别系统的体系结构，该结构由三大模块：过滤器、自动机解析器和 构造器组成，其中自动机解析器又分为分析器和分组器，并且详细介绍了各 个模块的功能和实现。 第5 章是实验及结果分析。通过实验验证本文所介绍的网络数据源识别 方法的合理性和准确性。在由四个领域1 4 0 个数据源组成的测试集上，测得 识别网络数据源模式的整体准确率和整体召回率分别为9 6 1 和9 4 5 ，实 验结果表明代码序列语法是一个全局语法，它在处理差异较大的领域时表现 出了很好的效果。 哈尔滨丁稃大学硕十学位论文 第2 章网络数据源模式识别相关研究 通过上一章对网络数据源模式识别方法研究现状的了解，本章阐述了网 络数据源模式识别的主要问题，以及与之相关的模式匹配技术和网络数据源 模式集成框架。 2 1 网络数据源模式识别的主要问题和方法 2 1 1 网络数据源模式识别的主要问题 识别网络数据源模式的目的是让计算机从语义上理解这些数据源中的查 询接口。由于这些查询接口( 通常指表单) 嵌入在h t m l 文件中，并通过浏 览器显示给用户，所以为了让计算机可以理解这些查询接口中所要表达的语 义信息，必须得到一个形式化的表达方式，这样才能使用户的查询被准确的 、翻译到各个深层网络的数据库中去。 一个深层网络查询接口实际上是由一组查询条件组成，而每个查询条件 是由表单元素按照一定组合构成。通过抽取查询接口中的元素及相关属性， 并根据它们在查询条件中所担当的语义角色把它们组合成一个个有语义层次 的查询条件。然而，在h t m l 文件中没有明确的信息表示表单元素所处的语 义角色，所以只能通过表单元素在页面中的位置等信息来推测它们之间的关 系，这个过程包含了很多的挑战。 首先，将表单元素组合在一起是困难的。因为每个查询条件类型可能由 不用数量、不同类型的表单元素组成，并且每个查询条件的表现方式可能各 不相同( 对于不同的查询表单) 。但是，借助观察和分析可以解决一部分这样 的问题，例如组成同一个查询条件的表单元素在表单中是聚集分布的。 其次，表单元素与它对应的文本相结合也是困难的。表单中的文本反映 了与它关联的表单元素的语义。而h t m l 文件中并没有明确的指明元素和文 本之间的对应关系，所以只能通过位置关系和语义关系进行推理，从而确定 它们之间的对应关系。例如表单元素和它对应的文本一般是相邻的，但是有 时候一个表单元素在表单中可能没有文本与之对应，例如：下拉式列表 哈尔滨t 挥大学硕十学何论文 i z 2 ( s e l e c t ) ，设计者将解释下拉式列表( s e l e c t ) 含义的信息存放在它的列表中， 并设置成默认显示内容。对于这种情况，还需要对表单元素的属性进行分析。 最后，由于网页是由不同的设计者设计而成，因此在设计的风格，书写 的格式，使用的嵌入技术等方面存在较大差异，从而为识别网络数据源模式 带来了很大的困难。 2 1 2 一种网络数据源模式识别方法 目前人们普遍采用的都是基于文本和查询接口元素位置关系建立起一些 推论或者人工预先从大量网页中总结出来一些常用的位置关系的模板，从而 实现对网络数据源模式的识别。本节主要介绍由z h a n g ：q 等人提出的一种基 于2 p 语法和最有效解析器的网络数据源模式识别方法。 z h a n g 等人通过观察发现网络数据源中的查询接口似乎存在着一些固定 的结构，所以他们假设在这些查询接口中存在着一种隐含的语法结构，并将 查询接口看成是一种有着固定语法的隐含的表达语言，这样对接口模式的识 别问题就转化成了对这种隐含语言的解析问题。为了解析这种隐藏语法， z h a n g 等人开发了2 p 语法和用于捕获2 p 语法的最有效解析器。 1 2 p 语法 2 p 语法用于捕获查询接口中存在的协定结构，