（计算机应用技术专业论文）基于半结构化数据信息检索的研究.pdf

摘要 由于半结构数据具有结构复杂、不规范和易变等特点，研究人员普 遍采用灵活的图或树形结构来设计半结构数据模型。在数据模型的基础 上，研究人员又提出了若干半结构数据的查询语言。图形的半结构数据 模型具有很强的表达能力，能够灵活的表示网络上各种格式的数据，但 是图形模型无法对数据种不同程度的结构进行明确的描述和概括，数据 所具有的结构完全隐含在数据表示当中，在描述结构规则性较高的数据 时存在大量的模式信息冗余，数据的处理效率比较低。 本文试图利用半结构数据中的规则结构来解决上述问题。从实际的 半结构数据出发，本文设计了描述数据结构规则性的方法，并根据半结 构数据的数据模式将半结构数据转化为关系数据，提高半结构数据处理 的效率。本文提出了关系和图数据相结合的半结构数据存储模型，以及 根据数据所具有的结构规则性，重新组织和存储数据的实际方法。其次， 本文给出了将半结构查询转化为关系运算表达式的算法，提出了利用关 系查询执行技术求解半结构数据查询的思路。 另外，本文结合当前搜索引擎的不足之处，提出了基于站点的分布 式检索结构：最后，本文对文本分类的算法进行了研究，在分析、比较 特征选择和权值调整对文本分类精度和效率的影响后，提出了一种给合 评估函数的t e f w a 权重调整技术，设计了一辩新的权重函数，将特征 评估函数蕴含到权值函数，按照特征对文本分类的辨别能力调整其在分 类器中的贡献。 关键词：半结构数据存储模型文本检索文本分类权重调整技术特 征评估函数 a b s t r a c t r e c e n tr e s e a r c hh a sf o c u s e do nd a t a w i t h i r r e g u l a r ，u n k n o w n ， o r f r e q u e n t l yc h a n g i n gs t r u c t u r e ：s u c hd a t ai sc a l l e ds e m i s t r u c t u r e dd a t a s u c hd a t 8i s g e n e r a ll ym o d e l e d a sl a b e l e dg r a p h s ， a n ds e v e r a lq u e r y l a n g u a g e sb a s e d o na b o v em o d e l s h a v e b e e n p r o p o s e d t h i sg i y e su s f l e x i b i l i t yt op r o c e s sa n yd a t a ，a n dw ec a nd e a lw i t hc h a n g e si nt h ed a t a s s t r u c t u r es e a m l e s s l y o nt h eo t h e rh a n d i ta l s oh a ss o m ed r a w b a c k s ：d a t a i si n e f f i c i e n tt os t o r e s i n c et h es c h e m an e e d st ob er e d l i c a t e dw i t he a c h d a t ai t e m ： q u e r i e s a r eh a r dt oe v a l u a t ee f f i c i e n t l y ， b e c a u s eo ft h e a d d i t j o n a lp r o c e s s i n go ft h er e p l i c a t e ds c h e m a ：e v e nas i m p l er e g u l a rp a t h e x p r e s s i o n a yr e q u i r et h ee n t i r eg r a p ht ob et r a v e r s e d i nt h i s p a p e r ， w ep r e s e n tam e t h o d c a p a b l e o fr e o r g a n i z i n g s e m i s t r u c t u r e dd a t aa c c o r d i n gt ot h er e g u l a r i t yo fi t ss t r u c t u r e t h e s t o r a g em o d e l ，c o m b i n i n gr e l a t i o n sa n dg r a p hd a t a ，d r o v i d e sa ne f f e c t i v e w a yf o re x p l o i t i n gr e g u l a r i t i e si nt h ed a t a ss t r u c t u r e t h ep a d e rg i v e s a na l g o r i t h mf o rg e n e r a t i n gs t o r a g em o d e l so ft h em e t h o d w ea l s og i v ea n a l b o r i t h 珥f o rt r a 兀s l a t i n gq u e r i e so ns e m i s t r u c t u r e dd a t at oo p e r a t i o n s a g a i n s tr e l a t i o n si nc h es t o r a g em o d e l n l es u b s e q u e n te x e c u t i o ne o u l db e f i n i s h e db yaq u e r ye v a l u a t i o nc o m p o n e n ti nr e l a t i o n a is y s t e m s t h i sp a p e ra n a l y s e st h es h o r t c o m i n g so fs e a r c he n g i n e s ，a n dt h e n p o i n t so u td i s t r i b u t e dr e t r i e v a ls t r u c t u r eb a s e dw e bs i t e s ，t h i sp a p e ra ls o a n a l y s e ss o m ea l g o r i t h mo ft e x tc a t e g o t iz a t i o n t h em e t h o d so ff e a t u r e s e l e c t i o na n dw e i g h ta d j u s t m e n tt e c h n i q u e sa r ed i s c u s s e da n da n a l y z e d a n d t h e i ri n f l u e n c eo nt e x tc l a s s i f i c a t i o np r e c i s i o na n de f f i c i e n c yi sp o i n t e d o u t w ei n t r o d u c e dan e ww e i g h tf u n c t i o n ，w h i c hi n c l u d e sf e a t u r ew e i g h t e v a l u a t i o nf u n c t i o na n da d j u s t st h ee f f e c to ft h ef e a t u r et e r mi nt h e c l a s s i f i e ra c c o r d i n gt ot h ef e a t u r et e r m ss t r e n g t h k e yw o r d s ：s e m i s t r u c t u r e dd a t a s t o r a g em o d e i ，t e x tr e t r i e v a l t e x tc a t e g o riz a tio n w eig h ta d j u s t r 舱n tt e c h niq u e s ， f e a t u r ee v a l u a t i o nf u n c t i o n 1 1 课题的研究背景 第一章引言 随着i n t e r n e t 及相关技术的发展与成熟，越来越多的人开始利用 网络获取信，息和相互交流，w e b 已经成为人们获取信息的重要手段。如 何在w e b 这样的分布式环境中找到有价值的信息，并从中提取出知识内 容已经成为目前信息检索、数据挖掘和知识管理等研究领域的重要课 题。但是，w e b 上的这些数据形式多样，既有保存在文件系统中的没有 严格结构的“松散”数据，也有存储在关系数据库中的高度结构化的数 据。人们采用不同的协议，通过各种接口来访问这些电子数据，如w w w 浏览器，数据库查询语言s q l ，各种应用接口和数据交换格式。其中有 些数据，如图像和声音文件等，完全没有结构。也有一些数据，虽然不 象数据库系统那样具有非常严格、明确的模式限制，但确实存在着隐舍 的规则结构。这些结构往往需要我们从数据中抽取；我们也经常出于一 些特殊的目的，比如浏览，而有意忽略这些数据的结构。我们把这种区 别于语音和图像文件等“原始数据”，具有一定程度的结构，又不象传 统的数据库系统那样存在严格模式限制的数据称之为半结构数据 ( s e m i s t r u c t u r e dd a t a ) ”。 半结构数据广泛存在于各神电子数据源，特别是i n t e r n e t 当中。 以w w w 为例，其h t m l 文件格式本身就是由标签和锚点等结构单元组成 的，因此文件的数据常常具有明显的结构。但同时数据的结构又非常不 规范，不符合传统数据库的要求，因此不能简单的应用现有的数据库技 术和工具，需要探索对半结构化数据进行描述和处理的新技术。x m l 标 准”的制定，给半结构化数据理论的应用提供了广阔的前景，进一步促 进了半结构数据研究的发展。基于半结构化文档的信息挖掘智能化信 息检索是当前网络信息获取研究最活跃的一个领域。它的研究与开发对 于如高精度智能搜索引擎、数字图书馆、电子商务、知识管理等很多信 息技术领域都具有巨大的推动作用。 搜索引擎为人们提供了检索w e b 上相关信息的方法，搜索引擎对 w e b 上的文档进行索引并进行分类，为人们提供一个w e b 内容的层次化 的目录结构；有的搜索引擎对w e b 上的页面进行全文索引，提供基于关 键词的检索。目前的基于传统信息检索”( i n f o r m a t i o nr e tr i e v a l ， i r ) 方法的搜索引擎大部分使用的是基于文档内容的词频统计，即 t f i d f 方法的索引方式。这种基于文档关键词的检索手段随着w e b 上 数据量的迅速增加而越来不适应人们的要求，它的主要缺陷有： 信息过量，返回太多的无关内容。若干个关键词构成的查询组合可 能返回上万个相关页面链接，很多检索结果和用户查询毫无关系。 w e b 的覆盖面有限，根据s t e v el a w r e n c e 的报告，目前任何搜索引 擎索引的部分不超过整个w e b 的3 0 。 面向关键字的搜索。目前搜索技术仅仅对关键字进行简单的匹配， 而不能根据用户查询目的进行查询内容的扩展，此外有些信息查询 是很难用关键词组合来准确的描述。 只能发现信惑，而不是知识。e b 中包含着大量信息，而这些信息 经过提炼加工可以上升为知识。单纯的使用统计的方法是无法把海 量的信息转化为知识的形态。 由此，我们可以看出，当前搜索引擎所使用的技术都难以解决找信 息难的问题。造成这种困难的实质在于搜索引擎缺乏知识处理能力和理 解能力，对要检索的信息仅仅采用机械的关键词匹配来实现。把信息检 索从目前基于关键词层面提高到基于知识( 或概念) 层面，是解决问题 的根本和关键。为了解决w e b 信息检索中存在的各种问题，e t z i o n i 【】 提出了w e b 挖掘( w e bm i n i n g ) 的概念：在已知数据样本的基础上，通 过归纳学习、机器学习、统计分析等方法得到数据对象闻的内在特性， 据此采用信息过滤技术在网络中提取用户感兴趣的信息或者更高层次 的知识和规律，简单的说，就是使用数据挖掘技术自动的从w e b 文档和 服务中发现和提取信息和知识的技术。应该注意到基于w e b 的数据挖掘 和传统的基于数据仓库的数据挖掘有着不同的含义。根据w j f r a w l e y 和g p s h a p ir o ”1 等人的定义，一般的数据挖掘指从大型数据库妁数据 中提取人们感兴趣的知识，而这些知识是隐含的，事先未知的、潜在的 有用信息，它侧重在于从已有的信息中提取规律性的知识。而w e b 挖掘 的研究对象是以半结构化和无结构文档为中心的w e b ，这些数据没有统 一的模式，数据的内容和表示互相交织，数据内容基本上没有语义信息 进行描述，仅仅依靠h t m l 语法对数据进行结构上的描述。为了对这种 半结构化数据进行分析和处理，w e b 挖掘越须和其研究手段结合起来。 1 2 目前的研究现状以及课题的研究内容 1 2 1 半结构数据的主要特点 下面我们主要针对半结构数据和传统数据库的区别，探讨半结构数 据的特性”2 “”。”。 l 、数据结构的非规范性 在半结构数据的应用中，经常会出现异构数据成分：一些数据 不完全，另外一些数据包含额外的信息。 同一信息也有不同的数据类型和表达方式：例如商品的价格可 能用美元或人民币来表示，地址信g 也可以用一个字符串或者 一个结构来表示。 对象的属性也可以是多值的，如一个人的姓名可能有多个。 因此，对半结构数据的非规范性结构进行建模和查询就成为半结构 数据的重要的科研课题。 2 、数据结构的隐含性 在半结构数据的许多应用中，虽然有时数据具有精确的结构，但其 结构却是隐含的。例如，电子文档通常由一个文本文件和相应语法组成 ( 如s g m l 文件及其d t d 语法) ，根据文档的语法定义，进行语法分析， 才能够从文本中析取出信息域以及信息域之间的语法关系。可见，在数 据结构隐含的隋况下，我们需要进行一定的分析、计算来获得数据的结 构。有的时候，语法分析树与文档结构的对应关系并不十分直接，这就 给文档的结构分析工作带来了相当的困难。抽取文本文件( 如h t m l 文 件) 中的数据结构信息是非常具有挑战性的。 3 、数据结构的不完整性 完全的结构化数据常常是不现实的，有些文件可能根本就没有结构 ( 如位图文件) ，还有一些数据( 如文本文件) 只存在框架性的结构信 息。 有的时候，应用系统需要将大量数据保存在数据库之外，从数据库 的角度来说，这些数据就是非结构化的。对这些外部数据的管理、访问， 及其与数据库中数据的互操作性，是需要研究的重要问题。为了提高外 部数据的调入、分析和集成的效率，往往需要采取优化技术，有选择性 的处理外部数据的特定部分，这时我们就只需要该部分数据的详细的数 据结构。 4 、模式的指示作用 在标准的数据库应用中，数据有准确的模式。而在某些应用系统中， 严格的模式信息却会造成不必要的限制，例如，在开发个人的w e b 站点 时，我们当然不希望有非常严格的数据模式限制。 在s t a n f o r d 大学的l o r e ”“系统中，用“数据指南”这个词来表示 在半结构数据的应用中所采用的，区别于传统数据库系统的模式。在传 统的数据库系统中，模式表示系统中数据必须遵守的严格限制，任何不 符合模式的数据更新都将被系统拒绝。而数据指南只是关于系统中数据 结构的一些描述信息，并不完全也不精确。所有对半结构数据库的更新 都将被系统接受，而代价是需要对数据指南作相应的修改。 5 、庞大的模式 与传统数据库的模式不同，由于数据的异构性，半结构数据的模式 往往非常庞大，例如，我们可以在网络的许多信息资源上找到有关长春 市区饭店的信息，因此这些数据的模式信息可能会很多，但数据本身却 很少。 因而，半结构数据的用户并不希望了解数据模式的所有细节，对模 式进行查询与对数据的查询同样是十分重要的。 6 、特殊的查询命令 对于一些不同于传统s q l 查询语句的命令( 如在数据中搜索特定的 字符串和数据形式) ，不能完全借助于数据的模式信息实现。这时我们 需要扩展数据库的查询语言，同时借鉴新的查询技术，如全文索引等。 7 、数据模式的动态性 传统的数据库系统，其数据模式基本上是固定的，对模式的修改很 少，模式变更的代价也非常大。因此，对于一些模式变化迅速的数据( 比 如实验数据一一随着实验技术的提高，其模式也不断更新) ，相对于关 系数据库和对象数据库，我们更倾向于采用类似a s n 1 的文件格式。对 于半结构数据，通常其模式是易改变的，可以随意的修改。 8 、数据元素结构的动态性 半结构数据的另外一个特点是数据元素的结构依赖于特定的观察 角度，或数据处理过程的特定阶段。例如，一个数据对象在数据处理 的最初阶段只是一个文件。经过分类，确定为b i b t e x 文件。再通过一 定的信息抽取，这时的对象包括属主和创建时间等信息。最后，经过语 法分析，得到一系列数据对象的集合。从这个角度看，半结构数据的模 式概念是非常灵活的。 9 、数据和模式之间的模糊性 传统数据库的基本原则之一是数据库模式和数据之间的分离。但对 于半结构数据来说，模式和数据之间的区别非常模糊，这是因为： 半结构数据的模式频繁修改： 模式的规模庞大： 数据结构和数据交织在一起： 同时对模式和数据进行处理和查询 以上这些半结构数据的特性，或者说与传统结构化数据的区别，使 得我们必须对一些传统的数据库技术进行重新考虑，并探索对半结构数 据进行管理的新技术。 从上面有关半结构数据的含义和特性的讨论中可以看出，半结构数 据仍然具有一定的结构，但是这些结构是隐含的，与数据本身交织在一 起，而且是不规则、不完整的。利用半结构数据中隐含的规则结构，是 提高半结构数据存储和处理效率的关键。 1 2 2 半结构数据的相关研究问题 1 、半结构数据的模型与语言 对于半结构的数据，首先需要考虑的问题是采用怎样的模型来描述 和管理数据。通常人们用图或树形结构来表示数据，如文献中的边标 记图。半结构数据的语言不仅仅指数据查询语言，也包括重塑数据的语 言。在集成不同数据源的半结构数据时，对数据进行重构是非常r 必要的 一种手段。半结构数据的查询语言，相对于传统的数据库查询语言来说， 主要面临如下问题：1 ) 数据的模式可能不明确。对于一个不确切的数 据模式，标准的s q l 与研究无能为力了；2 ) 数据的结构通常有多层嵌 套，甚至出现环形结构，因此数据查询语言妊须能够递归。传统的关系 代数不能适应这一需求，而最近的半结构数据的查询语言，如 u n q l “，l o r e l 和s t 川q 等，都能够对数据进行任意深度的查询，同 时具有很强的表达和重构能力。 2 、抽取数据的结构 对于只有粗略结构的数据，我们试图抽取出数据中隐含的结构信 息，并根据数据的结构对信息重新组织，以提高应用系统的性能。例如， 我们有大量包含文献索引的b i b t e x 或其他格式的文件，希望从文档中 抽取出那些最常用的文献信息，如标题、作者和关键词等，保存在关系 数据库中以便于管理和访问。如果文档或索引的格式超出了系统所能够 处理的格式范围，或者出现了信息重复等各种问题，文献信息的抽取就 会有相当的难度。 3 、数据模式 半结构数据与传统数据库的很多不同来自于两者在模式方法上的 巨大差异。例如，在某个应用系统中，半结构数据模式表示对象p e r s o n 包舍n a m e ，a d d r e ss 和f r i e n ds 等几部分信息，而a d d r e ss 可能是一个 字符串，也有可能是包含s tr e e t 和z i p c o d e 信息的数据结构。可见， 半结构的数据并没有严格的模式限制，半结构数据模式只是提供了对数 据结构的一般性的描述，即不可能完全也不十分精确。 利用半结构数据的数据模式表示不同程度的结构信息，构造和求解 数据查询，以及数据模式的维护，都是半结构数据研究的重要课题 4 、半结构数据库系统 在前面的讨论中，我们已经谈到了半结构数据需要不同于传统数据 库的查询优化方法，要借鉴和集成其它研究领域中的优化技术，如全文 索引等。在半结构数据系统中，数据项的含义相对模糊，同样的数据在 系统的不同层次中会有不同的表示方法：有的简单，有的复杂。因此， 传统的数据库系统问题，如事务处理，并发控制以及错误恢复等，都需 要重新加以考虑。数据的物理存储方法在半结构数据环境下也会有很大 的不同。另外，半结构数据的应用通常在系统外存在着大量的数据，这 些外部数据的访问优化，系统间的互操作等问题也非常重要。 目前对半结构数据的研究力图将数据库管理技术扩展到结构不规 则、易变的电子数据，研究主要集中在半结构数据的模型和查询语言。 由于半结构数据具有结构复杂、不规范和易变等特点，研究人员普遍采 用灵活的图或树性结构来设计半结构数据模型。p e n n s y i v a n i a 大学的 b u u n e m a n 等提出的“边标记图”( e d g e l a b e l e dg r a p h ) “。是其中具有 代表性的一种。其它的半结构数据模型，如t s i m m i s ”，l o r e 等系统 中所采用的模型，都可以转化为边标记模型。在数据模型的基础上，研 究人员又提出了若干半结构数据的查询语言，如u n q 一，l o r e l ”1 和 s t r u q 。这些查询语言主要以正规路径表达式为基础，以便能够递归 地搜索任意深度的数据路径。图形的半结构数据模型具有很强的表达能 力，能够灵活的表示网络上各种格式的数据，但在描述结构规则性较高 的数据时存在大量的模式信息冗余，而且难以利用高效率的传统数据处 理技术。这是由于数据所具有的结构完全隐含再数据表示当中，图形模 型无法对数据种不同程度的结构进行明确的描述和概括。另外，半结构 数据的查询执行完全依赖于对数据的遍历，数据的处理效率较低。目前， 半结构数据已经广泛的应用到数据集成( t s i m m i s ) ”1 、网络管理 ( s t r u d e l ) ”“，半结构数据管理( l o r e ) 和数据转换( y a t ) ”等众 多领域。另外，对半结构化数据的研究还包括半结构数据的模式，查询 优化，索引技术等方面。总体来说，有关半结构数据的系统研究还处于 相对不成熟的阶段，还有许多问题需要进一步的研究。 国内的研究者也对半结构化数据模型进行了许多研究。复旦大学的 研究者设计了一个半结构化数据模型s d o m n ”和基于其上的查询语言 s d o q l “”，东南大学的研究者设计了一个半结构化数据模型o i m 和基于 其上的查询语言0 i q l u 。”。 1 2 3 搜索引擎的相关研究问题 搜索引擎”“实质上是一种网页网址检索系统，有的提供分类和关 键词检索途径，有的仅提供关键词检索途径。它根据检索规则和从其他 信息服务器上得到数据并对数据进行加工处理，自动建立索引，并通过 检索接口为用户提供信息查询服务，能够自动对w w w 资源建立索引或进 行主题分类，并通过查询语法为用户返回匹配资源的系统。搜索引擎主 要是由c r a w l e r 、s p i d e r 、w o r m 、r o b o t 等计算机软件程序自动在因特 网上漫游，不断搜集各类新网址及网页，形成数以千万甚至上亿条记录 的数据库。它是通过采集标引众多网络站点来提供全局性网络资源控制 与检索机制、将全球w w 网络中所有信息资源作一完整的集合、整理和 分类、方便用户查找所需信息的网络检索软件。具有检索面广、信息量 大、信息更新速度快，特定主题的检索专指性强等特点。 一、搜索引擎的检索机制 搜索引擎定期自动搜寻有关w e b 站点、采集关于这些站点上的各类 信息，自动对这些资源进行标引、编制目录和文摘，自动将这些数据整 合到数据库，并能提供以w e b 为基础的包括布尔检索、短语或词组检索、 自然语言检索和各种限制检索在内的数据检索，按相关度输出检索结 果。搜索引擎的主体部分包括了数据采集模块、数据组织模块和数据 检索模块。对应地，其资源组织和检索机制包括了数据采集标引机制、 数据组织机制和用户检索机制，见图卜1 。 图卜1 搜索引擎的检索机制示意图 由于w e b 资源的特殊 生，搜索引擎的检索语法和检索规则与传统的 光盘检索和联机检索等有所不同。 二、搜索引擎的分类研究 w w w 网络搜索引擎不仅数量增长快，而且种类也比较多。但目前尚 无统一的分类标准。以下是一些主要的分类方法： 1 、索及资源内容的详略划分，有目录型、全文索引型、文摘型。 2 、按索及资源的来源划分，有万维网和非万维网检索工具。 3 、按覆盖范围划分，有通用查询引擎和专业查询引擎。 4 、按检索方式划分，主要有关键词索引、主题指南和元搜索引擎， 或按范畴层次查询的搜索引擎和词语查询引擎。此外，还有作者将搜索 引擎划分为分类主题目录、搜索引擎、主题索引、多种合一的集成检索 工具。也有文献将其划分为检索型、目录型和混合型检索工具：或浏览 式、按主题指南分类目录查询方式、利用检索软件进行关键词或自然语 言的查询方式、集成式和多线索的查询。 5 、按检索机制划分，有常规搜索引擎和元搜索引擎，或单独型和 集合型检索工具；或人工分类式、自动搜寻式和混合式搜索引擎：或基 于目录的搜索引擎、基于机器人的搜索引擎、基于客户的搜索引擎、元 搜索引擎，分布式搜索引擎。离线式搜索软件需下载后安装运行方可进 行检索，这类离线式搜索引擎多为元搜索引擎，主要有t u r b o s t a t 、 w e b s e e x e r ，飓风搜索通、小猎狗、s e a r c h x 等中外离线式元搜索引擎。 以上各类型搜索引擎，除分布式搜索引擎尚无实际营运的研究成果外， 其他类型的搜索引擎均已有较多的实际应用。 三、搜索引擎的比较研究 搜索引擎的功能在于将分散的网址集中起来，分类提供给用户，以 便快速查找到所需的信息。常规搜索引擎一般都带有数据库资源，因此 对搜索引擎的比较主要集中在数据库资源和搜索引擎的性能两个方面。 数据库资源方面的比较研究主要包括：数据库规模、索引方式、以及资 源内容( 如声音、图像、u s e n e t 、f t p 、n e w s g r o u p 、g o d h e r 、e m a “等 其它资源) 。检索性能的比较，主要有布尔检索、复杂布尔检索、相邻 和相邻a n d o r 检索( n e a r 、a d j 、f a r 、b e f o r e 、f o l l 0 w e db y 、 、 ) 、截词检索、检索范围限定、出版日期限定、多语种检索、 多种版本选择、大小写有别、概念检索、词语加权、词语限定、自然语 言检索、特定字段检索、缺省值、检索结果显示方式、显示数量选择、 相关排序、站点评价、相似性检索、结果过滤、用户界面、查准率、响 应时间等方面的比较研究。 国外学者对a 1 t av is t a 、e x c i t e 、l y c o s 从检索方式、响应时间、 准确性等方面进行比较与评价，a l t av is t a 检索功能较强，l y c o s 的覆 盖范围较广，a l t av is t a 真正地支持词语检索。此外，即使功能最完 善的搜索引擎也只能找到w e b 上大约1 3 的网页，1 9 9 8 年6 种主要搜索 引擎的w e b 网页搜索覆盖率：h o t b o t3 4 ；a 1 t a v is t a2 8 ；n o r t h e nl i g h t 2 0 ；b x c i t e1 4 ；i n f o s e e k1 0 ：l y c o s 3 。19 9 9 年被测试的1 1 种 搜索引擎中查询到网页最多的前三名是n o r t h e r n l i 曲t 、s n a p 、 a 1 t a v is t a ，没有任何一种搜索引擎可以包罗超过1 6 的网上信息资源， 搜索引擎的覆盖能力与一年前相比明显萎缩。近些年来陆续出现了许 多比较网络检索工具的研究和报道，绝大多数研究是就一些检索提问， 比较和评价多个检索工具，采用的比较和评价标准不统一。 国内对于搜索引擎的比较研究主要在两个方面：一是对搜索引擎的 基本检索性能和数据库内容进行比较；二是通过一定的检索提问进行上 网测试。已有作者从数据库的内容和结构、检索方式及特点、检索结果 的显示、数据库的更新及有无扩展功能等方面四个方面加以比较，发 现目录型检索工具y a h o o 、l i b r a r i a n s7 的检索功能相对较弱，检索型 检索工具的检索功能则相对较强。在布尔逻辑检索方面，仅仅少数搜索 引擎做得比较好。与传统的光盘数据库检索相比，因特网信息缺乏深度、 质量和可靠性不稳定，搜索引擎查询和光盘检索在用户服务方面均有优 势和不足。 四、存在的问题 第一，互联网上的文本信息具有不规范性。数据库中的资料通常都 是经过整理的，有确定格式的文档，而且有专人的维护，绝大多数是正 确的，可以信赖的。而互联网上的文本信息有多种语言，多种文件格式， 存在于不同的主机之上，没有统一的要求，并且通常没有专门的维护和 审查。可以说，是一种完全无序的、自发的状态。更糟糕的是，作为 w w w 上文本信息存在的主要方式的h t m l 是一个极其不严格的标准。加 之微软和网景( a o l ) 的浏览器之争，使得广泛使用的浏览器对于不符 合规范的h t m l 文件任意纵容，进而导致网络上实际存在的文本资料质 量良莠不齐，大大增加了检索的难度。 其次，互联网上的文本信息具有分散性。数据库中的资料都是集中 存储的，读取和查询不需要消耗大量的时问。而互联网上的文本信息分 散在世界各地的主机上，又是以超链接、超文本的形式组织，访问时间 很长，甚至由于主机当机或网络拥塞等原因不可访问。这些都给信息的 检索造成了困难。 第三，互联网上的文本信息具有海量性，这势必造成信息检索的不 全面。 第四，互联网上的文本信息更新十分迅速。数据库中的资料具有一 定的稳定性，一定时期内不会发生变化。而互联网为所有用户提供了发 布信息的平台，他们有权利更新、删除旧信息和发布新信息。由于信息 的发布者数量极多。所以信息存在的周期很短，几乎是刚刚访问过就会 发生变化。这使得针对互联网信息的检索系统很容易由于信息过期而发 生错误。 第五，互联网上的文本信息无效和重复信息较多。数据库中的资料 经过整理，并且有专人维护，一般不会出现重复和无效的信息。但是互 联网上的信息发布人员数量众多，而且没有规范，很容易造成同一信息 的多次发布或者发布无效信息。甚至有人出于特殊目的，故意发布错误 信息。例如，为了增加自己站点在搜索引擎中的检索命中率，故意在页 面中加入数十个常用的查询关键词，误导用户。 9 本文在对半结构化数据的管理以及对半结构化数据信息检索的相 关技术进行研究的过程中，着重完成以下问题： 1 ) 提出了关系和图数据相结合的半结构数据存储模型，以及根据 数据所具有的结构规则性，重新组织和存储数据的实际方法。 2 ) 在存储模型的基础上提出了利用关系查询执行技术求解半结 构数据查询的思路。 3 ) 研究文本检索的相关技术，探索如何改进目前的搜索引擎存在 的问题： 4 ) 设计实现文本分类的算法。 1 3 论文的结构 本文的主要内容分为六章： 第一章是引言，介绍了本文研究课题提出的背景、课题目前研究的 现状以及课题的研究内容， 第二章具体介绍了半结构数据管理的图形方法的主要内容：半结构 数据的模型和查询语言。对图形方法存在的问题进行了分析，并指出了 利用数据中的结构信息如何加以改进。 第三章提出了关系和图数据相结合的半结构数据的存储模型，并给 出了从图数据库到存储模型上的生成算法；另外，本文给出了将半结构 查询转化为关系运算表这式的算法，提出了利用关系查询执行技术求解 半结构数据查询的思路。 第四章讨论了文本检索相关的算法和设计实现，提出了一个基于站 点的分布式检索结构，并分析了采用这种结构的搜索引擎和其他搜索引 擎相比的优势。 第五章针对文本分类方法进行了讨论，提出了文本分类方法改进的 意见。 第六章是结论，对本论文的工作进行了系统的总结，同时进一步探 讨了下一步工作的设想。 第二章半结构数据管理的图形方法与结构方法 本章具体介绍半结构数据管理的图形方法的主要内容：半结构数据 的模型和查询语言。对图形方法存在的问题进行了分析，并指出了利用 数据中的结构信息如何加以改进。 2 1 半结构数据的模型 在本节中，我们首先对半结构数据模型设计的基本思想进行了探 讨，然后详细的介绍查询语言u n q l 所采用的边标记图模型“1 。 2 1 1 模型的选择 半结构数据的模型设计，首先要考虑的问题是模型的选择：是采用 复杂的、表达能力丰富的数据模型，还是只需要简单的、概要性的模型。 l 、简单模型 当我们从i n t e r n e t 上获取数据时，如果采用e b 协议进行传输， 那么数据最初的结构信息是很少的。而且，数据有可能来自一个新发现 的站点，其结构是我们的系统所未知的。面对千变万化的数据，要设计 出通用的满足所有需求的复杂模型是不可能的。由于数据的不规则性， 简单的模型可能会更加灵活和适用。因此，我们更倾向于采用概要性的 数据模型。这样，任何数据都可以转化成这种半结构数据模型。即使不 利用任何专用工具，我们也能够对数据进行访问。 2 、复杂模型 选择简单的数据模型并不排斥系统采用相容的复杂模型，以充分的 利用数据中的结构信息。比如，系统有时要对传统的关系数据进行处理， 如果我们忽略数据特有的索引信息，就会对系统的性能造成损害。在前 面的讨论中，曾经谈到半结构数据元素的结构具有动态性，数据对象的 结构信息随着不同的处理阶段而不断变化。同样的信息，处于原有系统 时是高度结构化的；通过网络进行交换，结构信息也随着减少；经过分 析和抽取，又具有了丰富的结构信息。因此，系统必须采用灵活的数据 模型，对简单和复杂的数据结构都能够进行处理。 下面我们简单的讨论一下组成复杂通用模型的一些必要的元素，当 然这里所列出的这些成分还远远不够。实际上，与设计半结构数据的通 用模型相比，面向特定应用数据的模型更加具有可行性。 一个描述半结构数据的通用性的复杂模型，至少应包括如下一些元 素： 1 、d m g ( o b j e c td a t a b as em a n a g e m e n tgr o up ) 模型“：表示对象、 类和类层次结构的符号表示；集合、链表、包、树组等结构元 素。 2 、空值：在半结构数据模型中，需要完善的空值处理。 3 、异构集合：半结构数据的集合常常由异构数据组成，可以通过 联合类型来解决这个问题。 4 、文本和索引：文半和索引是半结构数据非常重要的组成部分。 5 、多态类型：即同一数据可以表现出不同的结构。 6 、版本与时间：有时，我们更关心数据的更新变化，而不需要检 索整个数据源。 7 、对象标识的引用和维护。 显而易见，不论复杂模型的表达能力有多么丰富，都会存在着某个 应用或数据交换格式，其所具有的特征是模型所不能完全包容的。因此， 人们转而借助于简单、基本的数据模型。 2 1 2 边标记图模型 由于半结构数据具有结构复杂、不规范和易变等特点，研究人员普 遍采用灵活的图或树形结构来设计半结构数据的简单模型。半结构查询 语言u n 0 l 所采用的模型，也是一个边上有标记的有唯一根节点的有向 图，称为边标记图模型。图2 1 是一个数据库研究小组主页的边标记图 数据库。一般的边标记图数据中还可以存在共享的节点扣环路，但由于 边标记图中所有的数据节点都可以从唯一的根节点访问到，并且查询语 言u n q l 类似于对树进行遍历的语言，因此这里我们常常将边标记图不 加区分的统称为树。 假设我们局限于无环的图形结构，那么边标记图可以按照下面的语 法来构造： f )空树 1 j t )根节点有唯一一条标记为l 并且指向子树t 的出边 的树 t 1u t 2将两棵树t 1 和t 2 的根节点重合所形成的树 另外， 我们将树 j ， u ，2j ，2 u u j ，。) 简化为 j f 。，2 寸f 2 ，j ) 。例如图2 一l 中有关第一篇论文的部分数据可 以表示成( t i t l e j ( “”jf ) ) ，p a l a c e j ( “v l d b ”j ) ) ， y e a r j ( 19 9 8 j ( ) ) ) 。我们进一步将最底层的边l j ( ) 简化为l ，并 且瘩略两边的括号，则上面的表示方法可以简化为 t i i e j “”， p a l a c e ，“v l d b ”，y e a r = 亭1 9 98 ) 。 d b g r o u p 图2 1 边标记图模型的一个实例 在边标记图模型中，标记包含了所有的基本信息，因此我们需要指 定可用作标记的数据类型。首先，在传统的关系数据中可作为属 生数据 的那些基本的数据类型，如i n t e g e r ，r e a l ，s t r i n g 等，可以作为标记。 另外，我们定义一个新的类型s y m b o l 表示那些对应于关系数据中属性 名的标记的数据类型。综上所述，边标记图模型中的标记可以是符号、 整数、字符串、实数等等，其数据类型是这些基本的数据类型的并集。 边标记图可以形式化为成对的标记和数的集合： jr ，f 2j f ：，j ，其中，f 2 ，为标记，f i ，岛，f 。是其他的树。 其数据类型的形式化的定义为： t y p e 1a b e l = i n t ls tr i n g i is y m b o l t y p e tr e e = s e t ( 1 a b e l t r e e ) 1 、边标记图模型与关系和嵌套关系数据库 采用边标记图模型可以很容易的表达关系数据。假设一个关系其属 性为4 ，呜，4 ，关系中的一个元组为 ，则该 元组可表示为边标记图 4 jv 1 ，4 jv 2 ，4 | j k 。我们用一个特殊 的标记t u p 表示关系中的元组，则关系可以表示成 7 印j ，脚j ，2 ，聊j 0 ) ，其中，f ：，f m 为图数据中表示关系元 组的树。因此该关系可表示成图2 2 中的边标记图。对于嵌套的关系数 据，也可以类似的用边标记图模型来表示。 卜 t u pt u p t u p v a ri nv ar r ：= p r e dl ( r = r ) l ( r l r ) l r 查询语句“s e l e c tqw h e r e ”的执行结果是图数据库中的一系 列节点的集合。文法中的变量v ar 表示图数据中的节点；用符号e 来表 示一个空树。形如“r = xl ny ”的查询条件表示从节点y 到节点x 存 在符合路径表达式r 的路径。另外，正规路径表达式中还包括对标记和 原子数据的谓词条件p r e d 。 为了便于讨论，这里忽略了数据存储中的图数据，而只考虑其中的 存储模式和关系数据。首先我们按照存储模式s ，对形如“r = xi ny ” 的单个查询条件进行转化。根据路径表达式r ，构造等价的不确定自动 机a ，其状态之间的转移上标注着谓词。假设a 有p 个状态d 。o ，疗。， 模式s 有n 个状态s ，s ：，s 。，构造n + p 个状态的自动机s a 。对模式 s 中的转移j j 。和a 中的转移d 山d 。，如果p ( 1 ) = t r u e ，则在s a 中存在转移( s ，口) 旦_ ( 5 。，口) ，式中关系r 为模式节点s 包含属性域 l 的主关系或从属关系。自动机的起始状态为所有形如( 凡，口) 的状态 其中l 为变量y 所对应的模式节点，a 为自动机a 的起始状态；类似的， 其终止状态为所有形如( s ，a ) 的状态，其中a 为自动机a 的终止状态。 创建自动机s a ，并消除其中的无用状态后，我们采用类似于将自动 机转换为正则表达式的方法，得到等价于条件r = ) xi ny ”的关系运 算： ( 1 ) 对形如s 与s 。苎b s “的转移，变化为j 些! ! b s ( 2 ) 对形如s 士5 的转移，变化为j 坐! 墨b j r 2 ( 3 ) 对形如旦寸s j 曼b的自环，变化为 ! - j 些灿j 里呻，式中状态s 为临时状态 ( x s ( 月) = 八j r u r 睁司r u 为关系r 连续操作的闭包。 上述变换一直持续到只剩下起始状态和终止状态时为止，这时标注 在两个状态间的唯一转移上的表达式即为所求的关系运算。由于自动机 a 的状态数目与路径表达式r 的规模相当，因此变换可以在r 和s 的规 模的行列式时间内完成。 忙8 竺叟二蛔。 s 2 ，a 1 s3 ，a l s 4 ，a 1 j 意忑：9 泛忑至i ， n u l l p e r s 4 a 2 图3 3 模式s ，自动机a 和自动机s a 例如下面的查询语句 s e l e c tp t i t l e w h e r e= p r o j e c t = 枉 p a p e r = p i n d b g r o u p 对于查询语句中的路径表达式= p r o j e c t = = p a p e r ，构造自动 机a 如图3 3 中所示。根据图3 2 中d b g r o u p 的存储模式s ，构造自动 机s