（计算机应用技术专业论文）web数据库重叠估计技术研究.pdf

w e b 数据库重叠估计技术研究 中文摘要 w e b 数据库重叠估计技术研究 中文摘要 集成d e e pw e b 中的数据信息是一项非常重要的工作，在这项工作中常会遇到信 息冗余和记录去重问题，它们常成为集成工作成败的关键。估计w e b 数据库重叠率， 可以优化信息冗余和记录去重工作，减少集成的盲目性。 本论文主要包含三部分内容： 1 提出了在理想情况下的w e b 数据库重叠估计方法，包括一种朴素方法和在朴素 方法基础上的改进方法。朴素方法研究覆盖了从采样到估计的整个流程，但忽略了 w e b 的复杂性；改进方法通过高频字采样，提高采样和估计效率。 2 针对理想情况下的w e b 数据库重叠估计方法省略掉的w e b 数据库记录匹配问 题，提出了w e b 数据库重叠估计中的实体识别方法。根据d e e pw e b 查询接1 ：3 和返回 记录的特点，引入领域知识和预处理，计算记录相似度，从工程的角度降低识别复杂 度，提高识别准确性和效率。 3 为了进一步提高重叠估计的适应性，提出了w e b 数据库重叠估计的修正方法， 通过回归分析建立数据库相似度和估计偏差之间的关系，利用数据库相似度预测估计 偏差，提供真实值可能存在的范围。 本文进行了大量的实验，验证提出的各种理论和方法，同时提出了有待进一步深 入解决的问题，展望该领域科研发展的方向和前景。 关键词：d e e pw e b ，w e b 数据库，重叠，估计，高频字 作者：苗忠义 指导老n - 崔志明 a b s t r a c t r e s e a r c ho no v e r l a pe s t i m a t i o nt e c h n o l o g yf o rw e bd a t a b a s e s r e s e a r c ho no v e r l a pe s t i m a t i o nt e c h n o l o g yf o rw e bd a t a b a s e s a b s t r a c t i n t e g r a t i n gd a t ai n f o r m a t i o ni nd e e pw e bi sav e r yi m p o r t a n tj o b ，i nt h i sw o r kp e o p l e o f t e ne n c o u n t e rt h ep r o b l e mo fr e d u n d a n ti n f o r m a t i o na n dr e m o v i n gt h ed u p l i c a t ed a t a b a s e r e c o r d s ，t h e yo f t e nb e c o m et h ek e yt ot h es u c c e s so rf a i l u r eo fi n t e g r a t i o n e s t i m a t i n gt h e o v e r l a p p i n gr a t eb e t w e e nw e bd a t a b a s e sc a nh e l pt oo p t i m i z e t h ew o r ko fr e s o l v i n g r e d u n d a n ti n f o r m a t i o na n dr e m o v i n gt h ed u p l i c a t ed a t a b a s er e c o r d s ，t or e d u c et h e b l i n d n e s so ft h ei n t e g r a t i o nw o r k t h et h e s i sc o n t a i n st h r e em a i np a r t s ： 1 i nt h es e c o n dc h a p t e r , w ep r o p o s et h ea p p r o a c ho fe s t i m a t i n gt h eo v e r l a pb e t w e e n w e bd a t a b a s e si nt h ei d e a lc a s e ，i n c l u d i n gt h en a i v ea p p r o a c ha n dt h ei m p r o v e da p p r o a c h b a s e do nt h en a i v ea p p r o a c h t h en a i v ea p p r o a c ho fe s t i m a t i n gt h eo v e r l a po fw e b d a t a b a s e sc o v e r st h ee s t i m a t i o nf l o wf r o mt h ef i r s ts t e pt ot h ee n d ，b u ti g n o r e st h e c o m p l e x i t yo ft h ew e b t h ei m p r o v e da p p r o a c hi m p r o v e st h ee f f i c i e n c yo fs a m p l i n ga n d e s t i m a t i o n 、析t ht h em e t h o do f h i g h f r e q u e n c yw o r d ss a m p l i n g 2 c o n t r a p o s i n gt h er e c o r d sm a t c h i n gp r o b l e mo fw e bd a t a b a s e si g n o r e db yt h e o v e r l a p p i n gr a t ee s t i m a t i o na p p r o a c hi nt h ei d e a lc a s e ，w ep r o p o s et h em e t h o do fe n t i t y r e c o g n i t i o ni nt h ew o r ko fe s t i m a t i n gt h eo v e r l a p r a t eb e t w e e nw e bd a t a b a s e s b a s e do n d e e pw e bq u e r yi n t e r f a c ea n dr e t u r nc h a r a c t e r i s t i c so ft h er e c o r d ，w ei n t r o d u c ed o m a i n k n o w l e d g ea n dp r e p r o c e s s i n gi ne n t i t yr e c o g n i t i o n ，a n dc a l c u l a t et h es i m i l a r i t yo ft h ew e b d a t a b a s er e c o r d s f r o mt h i se n g i n e e r i n gp o i n to fv i e w , t h em e t h o dc a l lr e d u c et h e c o m p l e x i t yo fr e c o g n i t i o n ，i m p r o v et h ea c c u r a c ya n de f f i c i e n c yo fr e c o g n i t i o n 3 i no r d e rt of u r t h e ri m p r o v et h ea d a p t a b i l i t yo fe s t i m a t i o na p p r o a c h ，w ep r o p o s et h e a m e n d a t o r ys o l u t i o n sf o r t h ea p p r o a c ho fe s t i m a t i n go v e r l a p p i n gr a t eb e t w e e nw e b d a t a b a s e s u s i n gt h er e g r e s s i o na n a l y s i s ，w ec a ns e tu pr e l a t i o n s h i pb e t w e e nt h ed a t a b a s e s s i m i l a r i t ya n dt h ee s t i m a t i o n sb i a s t h er e l a t i o n s h i pc a nh e l pu st op r e d i c tt h ee s t i m a t i o n s b i a sw i t l lt h ed a t a b a s e s s i m i l a r i t y , w h i c hc a np r o v i d ear a n g eo ft h er e a lo v e r l a p p i n gr a t e b e t w e e nt h ew e bd a t a b a s e s w ec a r d e do u tm a n ye x p e r i m e n t st ov e r i f yt h ev a r i o u st h e o r i e sa n dm e t h o d sp r o p o s e d i nt h i st h e s i s ，p r o p o s et h ep r o b l e m sw h i c hn e e dt h ef u r t h e ri n - d e p t hs o l u t i o n ，a n dl o o k f o r w a r dt ot h ed i r e c t i o na n d p r o s p e c t so fr e s e a r c ha n dd e v e l o p m e n ti nt h ef i e l d k e yw o r d s ：d e e pw e b ，w e bd a t a b a s e ，o v e r l a p ，e s t i m a t e ，h i g h f r e q u e n c yw o r d i l w r i t t e n b y ： s u p e r v i s e db y ： m i a oz h o n g - y i c u iz h i m i n g 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 益垫= 盥 日 期：2 理乒： z 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 黔作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 ，复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：_ 融：望 日 导师签名：日 w e b 数据库重叠估计技术研究第一章引言 第一章引言 1 1 论文背景 互联网飞速发展，信息呈爆炸性增长态势，使互联网成为一个拥有海量数据的空 间。为了更好地认识和利用这一数据空间，人们根据信息蕴涵的“深度”，将其划分 为两部分：表层网( s u r f a c ew e b ) $ n 深层网( d e e pw e b ，也被称作i n v i s i b l ew e b 或h i d d e n w e b ) 。表层网由传统静态网页组成，很容易被传统搜索引擎索引；深层网以数据库 为后台，我们将这样的后台数据库称作w e b 数据库( 简称w d b ) ，用户通过网页提交 查询，w e b 服务器最终动态地将查询结果返回给用户。由于要动态提交查询关键字， 传统搜索引擎爬虫欠缺这样的功能，所以很难索引到d e e pw e b 页面。由于功能、内 容和可维护性的需要，d e e pw e b 站点越来越多，w e b 数据库中蕴藏着大量高质量的 结构化数据，成为数据挖掘和集成的宝藏【l 】。 文献【2 】在2 0 0 0 年6 月对全球d e e pw e b 的规模进行了宏观统计，称约有4 3 ，0 0 0 - - 9 6 ，0 0 0 个d e e pw 曲站点，数据量为7 , 5 0 0 t b ，约为静态页面的5 0 0 倍；2 0 0 4 年4 月 文献 3 】对其进行重新统计称有3 0 7 ，0 0 0 个d e e pw e b 站点，四年间增长了3 - - - 7 倍。文 献 4 】对中国d e e pw e b 的规模、分布和结构进行了研究，称约有2 4 ，0 0 0 个d e e pw e b 站点，2 8 ，0 0 0 个d e e pw r e b 数据库。d e e pw e b 站点已成为人们高质量信息的重要来源。 由于网络的开放性，大量数据集成、数据挖掘研究工作已经在d e e pw e b 上展开。 包括：数据源发现【5 一、数据源分类1 7 , 8 , 9 】、d e e pw | e b 爬虫1 0 , 1 1 , 1 2 】、查询接口匹配 1 3 , 1 4 】、 数据库大小估计【1 5 , 1 6 、d e e pw 曲数据抽取【1 7 , 1 8 , 1 9 , 2 0 、实体识别【2 1 2 2 1 、数据集成【2 3 ，2 4 】 矗盘 寸o d e e pw e b 研究还有较大潜力【2 5 1 ，数据集成的一些基础问题有待深入研究。如现 在集成主要见于同领域，如何在更广的范围内进行全局集成；效率如何提高；集成冗 余怎么解决；冗余的量是多少等等。 本论文就和解决集成中的冗余有关。但重叠估计作为一项较为基础的研究，应用 不限于此，详见研究意义部分。 1 2 研究意义 第一章引言 w e b 数据库重叠估计技术研究 w e b 数据库的特点是：结构化、主题集中、对外开放、控制分散、数量大、质量 高、接口和操作简单。w e b 数据库的内容较难被传统搜索引擎利用，而且即使索引到 了，也被当作普通网页分词、索引，失去了结构化特点，所以进行深层次集成就显得 尤为重要。 在数据集成的时候，首先要发现数据源，集成以前须判断数据源的质量，重叠率 是衡量数据源质量【2 6 】的一个重要指标。 为了更好地利用众多w e b 数据库中的信息，需以结构化的方式将他们集成口7 ，2 8 】 起来，一般情况下是对同领域的数据库进行集成，但在同一领域有众多数据源，信息 冗余问题非常严重，如何解决信息冗余、做好记录去重常常成为信息集成成败的关键。 若可以通过较少的数据源，找到领域全集，则可以有效减轻信息冗余问题的困扰。若 其中一个数据源被一个或多个覆盖( 即重叠率高) ，那么可以判断这一数据源包含的信 息是冗余的，没有必要集成，从而在后续集成中减轻去重的压力，提高集成效率。所 以估计重叠率就成为一项非常重要的工作。 重叠估计还可以用于判断一个数据源的权威性，比如新闻w e b 数据库，如果一 个数据库中的内容被多个其他的数据库包含，相当于它是多个数据库的交集，那么可 以判断它是比较权威的。 最近有学者提出数据空间 2 9 , 3 0 的概念，它是数据集成领域一个全新的研究方向， 但同样会遇到信息的冗余及去重问题，相信重叠估计在该领域同样有很大的应用价 值。 1 3 主要工作 本文研究工作主要包括以下几个方面： 从数学原理的角度给出了w e b 数据库重叠估计的模型。将两个w e b 数据库看 作两个集合，重叠部分即是它们的交集，计算它们的重叠率就是计算交集占 每个数据库的比例。 提出一种估计两个w e b 数据库重叠率的朴素方法，它是一种最自然的方法， 覆盖了w e b 数据库重叠估计的整个流程，但有较大的局限性。 提出诱导w e b 数据库某字段上高频字的方法，该方法从汉字高频字开始，在 某个字段上提交这些高频字，从返回结果中得到第一代高频字，再用第一代 2 w e b 数据库重叠估计技术研究第一章引言 高频字查询得到第二代高频字，以此类推，直到满意。 在朴素方法的基础上，提出一种改进方法，在诱导高频字的方向上获得样本， 估计w e b 数据库重叠率，由于在较短时间内获得大量样本，所以估计的效率 提高了。 提出了一种基于可查询字段的实体识别方法，在该方法中引入领域知识、字 段预处理以提高识别准确性，解决字段权值分配问题，并给出记录相似度计 算公式。 提出w e b 数据库相似度的概念。借鉴几何的相似概念，在文本意义上衡量两 个数据库的相似性，给出了计算两个w e b 数据库相似度的公式。 通过一定的训练集，收集数据库相似度和重叠估计偏差数据，利用统计学上 的回归分析，确定相似度和估计偏差之间的关系，进一步修正w e b 数据库重 叠率估计。 进行了大量的实验，以证明文中提出方法的有效性。 1 4 论文结构与基本内容 全文共六章，各章的内容安排如下： 第一章引言 主要介绍课题背景、主要工作以及课题的研究意义。 第二章理想情况下的w e b 数据库重叠率估计 首先介绍w e b 数据库重叠估计在数学上的理论依据，基于此，提出一种朴素的 估计方法，在朴素方法的基础上提出改进方法，w e b 数据库的重叠率估计效率明显提 高。 第三章重叠估计中的实体识别 针对第二章未解决的问题，引入字段匹配、领域知识以及对返回字段的预处理， 提出基于可查询字段的实体识别方法，降低了实体识别的复杂性，提高了识别的准确 性。 第四章重叠率估计值修正 为了提高重叠率估计的适用性，引入数据库相似度的概念，并且提出基于文本的 数据库相似度计算方法，通过一定的训练数据，使用回归分析的方法建立数据库相似 3 第一章引言 w e b 数据库重叠估计技术研究 度和估计偏差之间的关系，进而利用数据库相似度预测估计偏差，提供真实值可能的 存在范围。 第五章实验及分析 该章通过实验验证前面提出的各种方法，并对实验结果进行深入分析。 第六章总结与展望 对前面提出的方法进行总结及评价，指出本论文存在的不足，展望该领域的发展 趋势。 4 w e b 数据库重叠估计技术研究第二章理想情况下的w e b 数据库重叠估计 2 1 概述 第二章理想情况下的w e b 数据库重叠估计 d e e pw r e b 数据库大都专注于特定领域，所以其上的数据集成多是面向领域【2 8 ，3 1 】 进行的。在同一领域内有众多的w e b 数据库，重叠自然不可避免，因此必然面对集 成过程中的信息冗余问题。在很多情况下信息冗余问题非常严重，如何做好记录去重， 常常成为信息集成成败的关键，所以能够减少信息冗余的方法就显得极为重要。估计 两个同领域w e b 数据库的重叠就是这样的方法之一，它可以帮助在数据集成过程中， 通过尽可能少的w e b 数据库找到该领域的记录全集，尽可能减少信息冗余，减轻记 录去重的工作。 为了降低论述及理解的难度，本章的w e b 数据库重叠估计是在理想化状态下进行 的，即流程上严格按照w e b 数据库重叠估计方法进行，遇到复杂的w e b 操作，以一 个函数( 黑盒) 代替，具体函数如何执行留待下一章介绍。 2 1 1 问题描述 现设有两个同领域的w e b 数据库w d b l 和w d b 2 ，两者之间有交集i s l 2 ，f w d b ，l 、 i w d b ：i 、f i s 。：1 分别是三者的记录数量， i s 。：i i w d b 。i 是w d b l 的重叠率，i i s ，：i j w d b ：l 是w d b 2 的重叠率，由于我们很难确切的知道1 w d b 。i 、l w d b ：l 、i i s ，：i 三者的值，所 以需要通过一定的方法估计它们的重叠率。 2 1 2 相关工作 目前在w e b 数据库重叠估计方面尚未有研究成果问世。1 9 9 8 年k r i s h n ab h a r a t 在 文献 3 2 中最早提出采用随机抽样的方法估计两个搜索引擎的相对大小及重叠。 2 0 0 6 年r o n a kd e s a i 等人在文献 3 3 中讨论了在较大规模上元搜索引擎的信息冗余问 题，另有文献 3 4 ，3 5 ，3 6 讨论了搜索引擎之间的重叠问题，和本文的工作有一定的相 似性。 搜索引擎的重叠问题和w e b 数据库的重叠问题有一定的相似性，但也有明显的不 同。首先，初衷是不一样的，搜索引擎重叠研究主要针对搜索引擎的特性而言，w e b 第= 章理想情况t w c b 数据库重叠估计 w e b 数据库蕈叠怙* 技术研究 数据库重叠研究主要解决集成中的冗余和去重问题：其次，对象不同，一个面向全文 索引，一个面向在线数据库；再次，面对的查询接口不同，搜索引擎只有一个查询文 框，而d e e pw e b 查询接口多种多样，一个是非结构化查询，一个是结构化查询；犀 后，w e b 数据库重叠率估计较容易验证，而搜索引擎重叠估计验证较难。 2 2 朴素的估计方法 2 2 1 基本原理 设有两 幽2 - i 蚺个集台a 、b 用、吲表示两个集合中元素的个数，那么恤n b l 表示两个集合交集的元素个数t 现 从a 、b 两个集合中随机抽样、伟个元素构成两个抽样集台a 、b 。，若a 中恰有 口个元素属于b ，b + 巾恰有卢个元素属于a ，设p ( x ) 表示一个元素出现在集合x 中 的概率，p ( x l v ) 是一个条件概率，则有： 刖叫耻号铲= 鲁 弘- ， ，( a c 、b = 号斧= 罢 弘z ， 式2 - i 和2 - 2 为我们提供了估计两个w e b 数据库重叠的理论模型。 2 22 问题的挑战 理论模型只能当作指导，w e b 数据库重叠估计还要面临如下的挑战： l _ w d b 的信息隐藏在特定的查询接口后面，我们不能通过s e l e c t f r o m w d b 来获得其中的内容，进而求得两个数据库的重叠率。为了获得w d b 中的内容， 人们开发了一些面向d e e p w e b 的爬虫1 1 ”i ，可以用于获取w d b 中的内容叭1 3 1 9 州， 以此来判断两个数据库的重叠。这种方法一方面会占用大量的网络带宽，另一方面会 w e b 数据库重叠估计技术研究第二章理想情况下的w e b 数据库重叠估计 产生很多重复的记录，去重任务很重，可以说带来的问题比解决的更多，同时对d e e p w e b 站点也是不友好的。 2 如何采样。虽然文献 3 7 ，3 8 讨论了面向w d b 的采样，但也不得不承认对在线 数据库的采样是一项极具挑战性的工作，而要作到随机采样则几乎是一项不可能完成 的任务，即使做到随机采样效率也很低。 3 获得了记录以后，需要判断该记录是否存在于另一个w e b 数据库中，如何进行 实体识别。 4 虽然我们研究的是同领域数据库，但不同的w e b 数据库，描述同一个实体使用 的字段不尽相同，如何协调。 2 2 3 朴素方法的步骤 以中文为背景，现讨论一种朴素的估计方法。设现有两个w e b 数据库分别为 w d b l 、w d b 2 ，对应的查询接口为i l 、1 2 ( 至少有一个文本框) ，朴素方法的步骤： ( 1 ) 在字典中随机选择n 个字，形成查询关键字集合w = w l ，w 2 ，w n ) ； ( 2 ) 对w 中的每个字，将w i ( 1 i n ) 作为关键字在i l 上进行查询； ( 3 ) 收集查询结果形成结果集r i ； ( 4 ) 对r i 中的每一个元素( 抽取得到的记录) ，在1 2 上进行查询，检测其是否存在( 实 体识别黑盒) 于w d b 2 中，若在，记入集合o i ； ( 5 ) 对w i ，根据公式( 2 - 1 ) 或( 2 2 ) 会得到一个重叠率o r i ( o v e r l a p p i n gr a t e ) = i o i l i r i l ； ( 6 ) 计算平均丽： yd 冠 - _ _ 一_ _ o r = 上l 1 0 0 ( 2 3 ) 以 该步骤实现了w e b 数据库重叠估计的整个流程，得到的结果是一个百分比。如果需 要重叠绝对大小，可先估计w e b 数据库的大d x 1 5 , 1 6 1 ，再乘以重叠率就可得到，比较简 单，所以我们讲的重叠估计主要是重叠率的估计。 2 2 4 朴素方法的局限性 朴素方法虽然简单，但是具有较多的局限性： 7 第二章理想情况下的w e b 数据库重叠估计 w e b 数据库重叠估计技术研究 1 从字典取词的随意性很大，很难做到随机取词。 2 假设随机取词能够保证，一般字典的汉字收录量动辄几千甚至上万，用随机取 到的词进行查询，很多情况下没有返回记录，采样效率很低。 3 如果将字典内容限定在汉字常用字范围内，是否可行呢? 假设我们现在选定几 个常用字 “的，“一 ，“中”，“人 ) ，据观察网上大量w d b 查询接口发现，接1 2 1 内文本框大多对应后台数据库中长度较短的字段，例如在图书领域，提供的查询接口 属性往往是：书名、作者、出版社等，而像图书简介等含有大段文字的字段一般不包 含在查询接口内， “的 ，“一”，“中 ，“人”) 很可能在这些字段上不是最常出现的 字，因此返回的结果也不理想。 4 最后一步计算平均重叠率的时候，没有考虑每一个重叠率的影响系数，个别估 计值可能会使平均重叠率大幅偏离真实值，稳定性差。 总的来说，朴素方法是一种简单但准确性、稳定性不高的方法，原因在于w d b 隐藏在查询接口的后面，对其内容及记录分布情况不了解，我们是在无的放失地提交 查询。如能找到一种方法，尽可能少提交查询，多返回记录，这样的结果集会更大程 度逼近w d b 记录分布的真实情况，从而使估计的重叠率更接近真实值。 2 3 改进的估计方法 通过以上分析可知，问题的关键在于查询得到的记录集要尽可能按近w d b 记录 分布的真实情况，要完全得到w d b 记录分布不太容易，也没有必要，所以我们将问 题作一个转化，如果能得到w d b 上和查询按口文本框相对应字段上的高频字，用这 样的高频字进行查询将得到更多的返回记录，这样不光会提高采样的效率，而且估计 会更准确。 2 3 1 z i p f 定律 1 9 3 2 年，哈佛大学的语言学专家z i p f 在研究英文单词出现的频率时发现，如果 把单词出现的频率按由高到低的顺序排列，则每个单词出现的频率与它的名次的常数 次幂存在简单的反比关系： ，1 尸( ，) = i ( 2 4 ) 这里c 0 1 ，q 1 ，后人把这种分布就称为z i p f 定律1 3 9 1 ，它表明在英语单词中，只 8 w e b 教据库重叠估计技术研究第= 章理想情m 下的w e b 数据库i 叠估计 有极少数的词被经常使用，而绝大多数词很少被使用，实际上，包括汉语在内的许多 国家的语言都有这种特点1 4 0 , 4n i 。 2 32 汉语中的高频字 汉语中字是最小的语言单位，g b 2 3 1 2 8 0 4 2 共收录6 7 6 3 个汉字其中一级汉字 3 7 5 5 个，二级汉字3 0 0 8 个，这6 7 6 3 个汉字并不以等概率出现在汉语中，其中存在 少量出现频率很高的即我们称之为高频字的汉字。 以清华大学统计的汉字频度表为例4 ”，其语料库总字数为8 6 ，4 0 5 ，8 2 3 个，获取前 若干个频繁汉字及其对应的出现频率，结果见表2 - 1 ，出现频率最高的前1 0 个汉字分 别为“的”、“一”、“国”、“在”、“人”、“了”、“有”、“中”、“是”，“年”。其中前5 0 0 常用汉字的覆盖率为7 85 3 ，这代表了现代汉语的一种普遍现象 表2 - i 高频汉字字频( 片断) 序号 汉字出现扶数万分比 是 6 5 7 7 3 97 6 1 2 2 2 33 获取宇段上的高频字 昙三_ 孽罴了 _ 一s* 一 一_ 。 。 一 一_ 一* e 一_ l l _ 】 岬“二 一 一 = “ * jm 目 s _h t ? j 目d一女! ! e ab o o k s c h i n a 嘲摈i3 e 甄i 赢c n a 搜索站粜( 片段 第二章理想情况下的w e b 数据库重叠估计w e b 数据库重叠估计技术研究 图2 - 5 中国图书网查询接口及返回结果( 片段) 根据观察结果1 ，通过高频字查询采样效率高，样本集更接近w d b 的真实分布， 所以找一种方法获得w d b 某字段上的高频字就成了解决问题的关键。我们提出一种 以汉语高频字为起点，从结果页面抽取对应内容【1 7 , 1 8 , 1 9 , 2 0 】( 观察结果2 ) ，统计字频，再 以其中高频字构造查询迭代诱导的方法。 2 3 2 节中提到，存在少量高频字是现代汉语的一种普遍现象，虽然某些字段的 高频字可能不是 “的 、“一 、“国”、“在”、“人 、“了、“有”、“中 、“是 、“年”) ， 例如：姓名字段的高频字可能为 “王”、“陈”、“李”、“张 、“刘”、“英 、“华 、“王 、 “秀”、“明 、“珍 ) ，但汉语中的高频字会在这些字段上成为次高频字或次次 高频字，除个别字会被当作停用字外，汉语中的高频字，大多数情况下都会有一定的 覆盖率。所以以这些汉语高频字为起点，可以迭代诱导出字段上的高频字。 现设有一个w | e b 数据库为w d b l ，对应的查询接口模式i = ，其中a i ( 1 i n ) 为查询接1 ：3 上的属性；对应的数据库模式为m = ，其中弓( 1 j s ) 为w d b l 上的字段，汉语高频字集c f w = w l ，w 2 ，w t ) ，下面分两种情况讨论获取高 频字的方法： 情况1 ：查询接口只提供一个查询的文本框： 算法l ；诱导某属性上的高频字i n d u c e _ f w l ( v e c t o rc f w ，s t r i n gi ，i n tn ，f l o a t6 ) 输入：汉语中的高频字集合c f w , 查询接口l ，每次获取高频字个数n ，增长率阈值6 。 输出：同i 相对应字段上的高频字集合。 步骤： 1v e c t o rf w p = - 1 2 i ，f w i = o ，f w 2 = o ： 高频字池f w p ，f w l 、f w 2 存放高频字 2v e c t o rr e s u l t = 1 2 l ： 存放查询结果 3i n tn u m ： 记数己放入f w 2 中的高频字个数 4f w i = c f w ； 以汉语中的高频字为起点 5w h i l e ( t r u e ) 6 7 f o r ( i n ti = o ；i 1 2统计r e s u l t 和i 中文本框相对应属性值上的字频，形成字频列表l 1 1 3 依字频由高到低对l l 排序 1 4 n u m = o ； 15 f o r ( i n tj = 0 ；j l1 s i z e o ；j + + ) 1 0 w e b 数据库重叠估计技术研究第二章理想情况下的w e b 数据库重叠估计 情况2 ：查询接口提供两个或两个以上可输入文字的文本框：文献 1 1 】在对大量w e b 查询接口进行统计( 表2 2 ) 后显示，大多数领域的w e b 数据库允许在单个属性上提交 查询，即查询接口模式中提供多个属性，但用户可以只使用其中一个属性而保持其它 为空。 表2 - 2 单属性值查询支持度 领域支持度( )领域支持度1 - ) 图书1 0 0电子 9 6 工作 9 6 计算机 9 6 电影1 0 0游戏 9 6 汽车5 8家具 1 0 0 音乐 l o o珠宝 1 0 0 为降低分析的复杂性，仅以有两个文本框为例，这样可以交替在两个文本框上查 询，通过抽取结果页面上的内容统计对方的高频字。 算法2 ：诱导某属性上的高频字i n d u c e _ f w 2 ( v e c t o rc f w , s t r i n gf t , s t r i n gs t , i n tn ，f l o a t6 ) 输入：汉语的的高频字集合c f w ，查询接口中的第一个文本框属性f t ，第二个文本框属性s t ， 每次获取高频字个数n ，增长率阈值6 。 输出：同f t 相对应字段上的高频字集合。 步骤： lv e c t o rf w p = o 。f w = l z i ： 高频字池f w p ，f w 高频字集合 2v e c t o rr e s u l t = o ：腑放查询结果 3i n tn u m ；对收集到的高频字进行记数 4f w = c f w ；以汉语中的高频字为起点 5s t r i n gq t = f t , c a = s t ； q t 为查询文本框，c a 为收集字频字段 6w h i l e ( t r u e ) 7 8 f o r ( i n ti = o ；i 当f w p 元素的增长率小于6 那么r e t u r nf w 玩唇f w p 的增长率判断是否结束 若q t = f t 那么q t = s t , c a = f t 否则q t - f t , c a = s t ； 我们把曾经出现过的高频字放到一个高频字池中，当池的增长率小于阈值6 时程 序结束，并返回最新收集到的高频字作为结果输出。 2 3 4 改进方法的步骤 现设有两个w e b 数据库分别为w d b l 、w d b 2 ，对应的查询接口模式为i l = 、1 2 = ，其中a l l ( 1 i n ) ，a 2 j ( 1 j m ) 分别为查 询接口上的属性，对应的数据库模式为m l = 、1 2 = ，其中f l i ( 1 i s ) ，f 2 j ( 1 j t ) 分别为w d b i 、w d b 2 上的字段，改进的算法步 骤如下： ( 1 ) 求w d b l 、w d b 2 对应字段上的高频字集合f w l 、f w 2 ，形成集合f w = f w l u f w 2 = w l ，w 2 ，w d ； ( 2 ) 对f w 中每个字，将w i 作为关键字在i l 进行查询； ( 3 ) 收集查询结果形成结果集r i ( 4 ) 对r i 中的每一个元素，在1 2 进行查询检测其是否存在于w d b 2 中，若在记 入集合o i ，第三章将提到如何识别实体2 8 2 9 】； ( 5 ) 对w i ，据公式( 2 1 ) 或( 2 2 ) 会得到一个o r i ( o v e r l a p p i n gr a t e ) = l o i l i r i ； ( 6 ) f w 所有元素得到的返回记录总数为r ，r j r 将是o r i 在计算； ( 7 ) 去掉最大、最小的重叠率，计算平均孺； 丽：兰冬伽f 1 0 0 ( 2 - 5 ) 鲁r 1 2 3 4 5 6 7 8 9 o l 2 3 4 5 b m b m他侈加扰勉筋m筋 w e b 数据库重叠估计技术研究第二章理想情况下的w e b 数据库重叠估计 改进方法使用了高频字采样，为了防止偏倚，将两个w e b 数据库的高频字相并形成 查询关键字集合；为了防止个别数据对平均重叠率产生较大影响，我们给每个重叠率 确定了一个权值，权值主要取决于关键字的返回记录数，这样可以进一步稳定估计准 确性。 2 4 本章小节 本章是本论文的中心，涵盖了w e b 数据库重叠估计的整个流程。介绍了方法的 数学原理，按照这一原理提出了一种朴素的w e b 数据库重叠估计方法，针对朴素方 法的不足，根据字段上的词频特性，提出一种基于字段高频字的w e b 数据库重叠估 计的改进方法。 第三章重叠估计中的实体识别w e b 数据库重叠估计技术研究 第三章重叠估计中的实体识别 第二章论述了理想情况下估计w e b 数据库重叠率的方法，没有考虑两个数据库 中记录的对应，认为他们可以正确匹配，但实际情况并非如此，因此需要进行实体识 别。 3 1 概述 w e b 数据库和本地数据库最大的不同是我们可以对本地数据库施以很多操作，即 使是检索也有多种选择，而对w e b 数据库的检索只能通过其网站提供的查询接口进 行，控制权不在用户手中。因此对w e b 数据库的研究只能适应其特点，提供一些关 键字，通过查询接口，获得一些包含有返回列表的网页，然后通过一定的抽取方法， 得到其中的记录。他们来自于w e b 数据库，可以看作是其中的一个子集，或者一个 样本集合，通过它们来研究其对应的w e b 数据库。 这些记录描述现实生活中的对象，可能是一个事物或一种关系，我们将他们描述 的对象称作实体，将判断两条记录是否描述同一个对象的活动称作实体识别。本文在 估计w e b 数据库重叠率时需要用到实体识别的方法。例如：现有两个同领域的w e b 数据库a 、b ，要估计它们的重叠率，我们前面的方法是先从数据库a 中获得一个样 本集a ，测试样本集彳中的每一个元素是否包含于另一个数据库b 。设样本集么中 属于b 的元素个数为a ，样本集彳元素个数为b ，那么a b 就是样本集彳相对于b 的 重叠率。最后用多次采样重叠率的平均值估计数据库a 相对于数据库b 的重叠率。 这其中有一个非常重要的问题是如何确定样本集彳中的某一元素i 是否在数据库b 中。我们知道，i 是由多个数据项构成的记录，用于描述一个对象，通常手工识别的 步骤是：先从i 中选择一个字段，在b 的网站查询接口上查找，会得一个包含返回结 果的网页，抽取其中的内容得到包含返回记录的l i s t ( o 个或多个元素) ，人们可以确 定i 所描述的对象是否存在于l i s t 中，这一问题如果完全采用手工操作，研究的意义 就大打折扣，而且对于较大的样本集也不现实，本章的内容就是要较自动的完成记录 匹配或叫实体识别。 目前实体识别方面已经出现了很多研究成果，人们主要着眼于两个方向：第一种 1 4 w e b 数据库重叠估计技术研究第三章重叠估计中的实件识别 是对实体记录以字段为单位进行分割，然后基于文本特征通过字符串匹配( 如t o k e n 距离、编辑距离) 建立实体匹配函数，最后和一定的闽值比较，确定两条记录是否指 向同一实体。文献【2 2 较为真型它通过记录块划分、相似度计算、迭代的训练可以 实现d e e pw e b 实体识别自动化。另一种通过上一f 文的语意或领域知识，利用数据挖 掘方法来识别实体。文献f 4 4 】将表象间的语义关联咀图形化的方式表示，通过图分割 技术对表象集进行聚类每组结果由对应于同一实体的表象集组成。文献 2 1 】结合前 面两个方向，利用文本匹配模型、语义分析模型和分组统计模型的三段式逐步求精策 略提出了一种基于语义及统计分析的实体识别机制。 上面的方法均能较好的解决实体识别的问题，但都有同一个较严重的问题，那就 是比较复杂，可咀称作重量级实体识别方法。我们这里的实体识别要为w e b 数据库 重叠估计服务，需要轻量级的，为此我们也提出一种方法，基于字符串匹配，但加入 了领域知识和预处理，由于比较简单，所以处理速度快，而且准确性也可以保证。 32 准备工作 3 2 l 字段匹配 w e b 数据库的搜索结果是一个含有记录列表的网页，同领域：j f _ = 同网站以不同的形 式出现，但有一定的相似性，如图3 1 ： ! ! ! ! ! ! k 卫e 艇坠 “n m q 矾 * ”：口舯 e 【 m 自附蝌 自 m n t 1 m l2 s 1 5 $ 自f rv 帐自y 一# 十目m 6 i f * t h ! 日j m m m 01 ： $ m 日日日瞄 * r m t 2 图3 1b o o k s c h i n a 和c 1 1 i n a p u b 搜索结果对比 图3 1 是从中国互动出版社和中国图书网两个网上书店的搜索结果中截屏得到的，可 以看到描述一本书的关键字段在两个网站上几乎完全相同，包括书名、作者、出版社、 i s b n 、出版同期、价格，通过一定抽取方法可以很容易抽取到这些信息，我们这里 的实体识别是为重叠估计服务的，没有必要采用特别复杂的方法，所以采用人工匹配。 3 22 领域知识 在实体识别的时候需要进行字段的匹配，如果仅靠字符