小议基于语义的构件检索系统研究与实现

《小议基于语义的构件检索系统研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

基于语义的构件检索系统研究与实现学校代码:10246学号:052021118灌*大硕士学位论文(科学学位)基于语义的构件检索系统研究与实现专院系:信息科学与工程学院业:计算机软件与理论姓名:蔡怡峰指导老师:钱乐秋教授完成日期:2008年5月12日 基于语义的构件检索系统研究与实现指导小组成员名单钱乐秋(教授)赵文耘(教授)彭鑫(讲师)公、 基于语义的构件检索系统研究与实现目录【摘要】..............................……5第一章引言...........................……71.1研究意义.........................................................................……71.2相关工作.........................................................................……81.2.1关键字和字符串查找…“.…”.”.......……””.”二”……“”.”…”……“”…”.”.91.2.2型构匹配(signatureMatching)二”.……”.……”.........……””...……”.91.2.3行为匹配…”............……”...............……“............……”.”........……”…“.101.2.4基于刻面的分类和检索..……”二“..…”..……”“..…“..……”…”..……”“.101.2.5基于语义的构件描述和检索.”....……””.””…“...........……”“......……121.3本文的研究工作...........................................................……131.4本文的组织结构...........................................................……14第二章基于本体的构件描述框架与检索过程.…152.1本体(Ontology)........................................................……152.2本体描述语言0、VL.....................................................……162.3功能本体元模型...........................................................……202.4构件语义描述框架.......................................................……232.5构件检索过程...............................................................……24第三章概念映射......................……263.1概念映射算法...............................................................……283.2概念映射的相似度.....................................................……”.313.3算法复杂度分析............................................................……32第四章语义匹配......................……34勺) 基于语义的构件检索系统研究与实现4.1扩展构件查询................................................................……344.2计算匹配度...................................................................……364.2.1匹配算法…”.“““.”……“。“..…“....……“...........……“…“.…”......一”.”.364.2.2基于集合论观点的功能匹配算法二”二”.”...……””.”.””.”..…““”.”.…374.2.3基于属性距离的功能匹配算法…”“.”.“..……””.””.”.”.”..…”.…”.….394.2.4本文使用的功能匹配算法…””””.”””“.“..…””.”.””””.”.“.”.”“”.….41第五章优化构件查询..................……44第六章系统实现与实验数据分析........……476.1系统实现.......................................................................……476.2实验分析.......................................................................……57总结与展望...........................……63参考文献.............................……64致谢.............................……68忆 基于语义的构件检索系统研究与实现【摘要]基于构件的软件开发(CBSD)提出复用软件构件，而不是采用一切“从零开始”的方式，来组装特定领域的应用系统。CBSD可以充分利用已有的开发成果，减少重复劳动，提高软件的开发效率。同时，通过复用已测试过的高质量构件，避免了重新开发可能引入的错误，从而提高了软件质量。然而当存在大量构件时，在构件库中检索符合特定复用需求的构件变得十分困难。特别是在万维网(WWW)逐渐成为一个丰富的构件来源之后，这一问题变得更加突出。因此可复用构件的描述和检索一直是CBSD的一个研究重点。传统的基于关键字、型构(Signat盯e)或刻面的构件检索由于缺少特定领域语义信息，因此在查准率和查全率上存在不足。针对这些问题，许多学者提出对基于语义的构件检索方法进行研究。基于语义的构件检索在各个步骤都考虑到用户查询的语义以及相关领域的知识，因而具有较高的查准率和查全率。然而从当前一些研究工作看，基于语义的构件检索仍然存在一个突出的问题，即用户对问题域的理解以及所熟悉的自然语言表达方式与构件的规范语义描述之间存在差异。本文提出了一种基于语义构件检索的交互式查询方案生成方法，允许用户使用受限的自然语言进行检索。该方法首先通过概念映射将用户的自然语言查询转换为本体描述，在此基础上根据语义约束关系对原始查询方案进行扩展，并根据初步的返回结果进行优化，从而最终确定用户的查询方案。其中，概念映射充分利用了用户自然语言描述中的上下文(主要由谓语、宾语、状语和定语组成)信息以及领域本体中的语义上下文之间侧郎渡纂息，同时辅以交互式会话过程。而查询方案优化过程则根据初步的查询返回结果计算可能的优化方案，并通过交互会话引导用户进行确认。该方法可以充分挖掘潜在的用户查询语义，对于提高构件检索的查准率和查全率、减少查询努力具有十分重要的作用。本文对基于语义的构件检索的各个步骤进行了研究，并实现了整个构件检索系统。文章的最后对用户查询实例进行了演示，并且分析了检索系统的查准率、查全率和检索效率，以此验证了本文所提出方法。【关键词】软件复用，构件检索，语义，本体，概念映射，会话，交互【中图分类号】TP319 基于语义的构件检索系统研究与实现[Abstraet]Co帅onent一BasedSoftwareDevelopment(CBSD)teehnologypromotesassemblingaPPlieationsofeertaindomainbymeansofreusingsoftwareeomPonentsratherthandoingeverythingfromtheverybeginning.CBSDtakesadvantageofexistingassetstoredueeeffortsandraiseProduetivity.SoftwareeomPonentsarefullytested50thattheyhavehighquality.However，whenthereareagreatnumberofeomponentsinrePository，it’5hardtoretrieveeomPonentswhiehmeetthesPeeifiereuseneed.ThusthedeseriPtionandretrievalofreusableeomPonentsarealwayshotissuesinCBSD.Traditionalkeyword一based，signaturemethodorfaeet一basedeomPonentretrievalhavelowPreeisionandreeallduetothelaekofdomainknowledge.ManyresearehersProPosesemantie一basedeomPonentretrievalmethod.Semantie一basedretrievalmethodtakesthesemantieofuserqueryandtheknowledgeofeertaindomainintoaeeountduringeverystePofretrievalProeess，whiehresultsinhigherPreeisionandreeall.There’5onemajorProbleminsemantie一basedeomPonentretrievalProeess15thediscrePaneybetweennaturelanguagewhiehusersarefamiliarwithandformalsemantiedeseriPtionsofeomPonents.InthisPaPer，aninteraetivequerygenerationmethod15ProPosed，whiehallowseonsumerusenaturallanguage.ThemethoduseseoneePtidentifieationProeesstomaPusers’naturelanguagetoontologydeseriPtionsofeomPonents，thenextendsinitialqueriesbysemantieeonstraintsandrevisesqueriesaeeordingtoretrievedresults.ConeePtidentifieationmakesfulluseofuserqueryeontext(mainlyeomposedofpredieate，objeet，attribute，andadverbial).ConeeptidentifieationandqueryrevisionuseeonversationalProeesstointeraetwithusers.ThismethodextraetsimPlieitsemantiesinuserqueries50thatit，leadstoimProvereeallandPreeisionrates，redueeretrievaleffortineomPonentretrieval.ThisPaPerresearehesoneaehstePduringeomPonent一basedeomPonentretrieval，andimPlementsthewholeeomPonentretrievalsystem.WedemonstratearealqueryProeessandanalyzethePreeision，reeallandtimePerformaneeofthissysteminordertoverifyourtheory.【Ke”ords]softwarereuseeomPonentretrieval，semantie，ontology，eoneePtidentifieatiofl，eonversationinteraetion 基于语义的构件检索系统研究与实现佑—雀梦己l吉.刁7二F.J.口1.1研究意义软件需求的高速增长与软件生产率的持续低下，导致了软件工程研究的主流之一—软件复用技术的蓬勃发展。软件复用是指利用已有的软件资产开发和构建新的软件系统，而不再采用一切“从零开始”的开发模式。这使得应用系统的开发可以充分利用已有的开发成果，减少了包括需求分析、设计、编码、测试等活动的许多重复劳动，大大提高了软件的生产效率。同时，通过复用已经被充分测试了的软件资产，避免了重新设计或者开发可能引入的错误，从而提高了软件的质量【l]。借鉴计算机硬件组装的成功经验，软件工程界也提出了构件的概念，成为支持软件复用的核心技术之一。虽然软件构件还没有一个统一的定义，但2000年5月CMU/sEl的FelixBeehlnan等人在一份关于基于构件的软件工程的报告中给出了如下定义【2]:软件构件是①一个不透明的功能实现;②能够被第三方组装;③符合一个构件模型。软件构件改变了软件生产方式，将软件开发的重点从分析、设计、编码转移到了基于己有构件的组装，这被称为基于构件的开发(CBSD)。近年来，随着面向对象技术、Intemet和节几b技术的成熟、以及OLE和CORBA等工业标准的出现，大大刺激了构件技术的发展。另一方面，软件产业的竞争日益激烈，如何缩短软件的交付时间和提高软件质量已经成为决定企业生存的关键。正是因为对竞争的时间优势和质量优势的追求，造成了对可复用构件的需求。随着实践的深入和时间的积累，企业内部的构件库会保存大量自主开发或者从市场上购买的构件，万维网(ww，v)更是逐渐成为一个资源丰富的构件库[3]。如何在大规模的构件库中检索符合特定复用需求的构件变得十分困难，因此，可复用构件的描述和检索就成为了CBSD的一个研究重点〔4]【习。构件的复用包括构件检索、构件理解和适应性修改三个部分。而构件的复用成本就由这三部分组成:复用成本=检索成本+理解成本+修改成本。有效的构件描述和检索机制能够大大降低构件检索和理解的成本，同时提高构件的复用率，为构件的制作者带来回报。因此，一个有效的构件描述和检索机制应该包含以下特性:①较高的检索指标。一个好的构件描述和检索方法需要有足够的分辨度，能够区分出构件库中具有本质不同的构件。检索工作是使用软件构件的前提，它直 基于语义的构件检索系统研究与实现接影响到后续的构件使用、集成等步骤。对于一个复用者来说，如果他无法定位到满足需求的软件构件，那复用也就无从谈起。可以用查全率和查准率来定义检索效果:查全率=检索到的满足需求的构件个数/构件库中所有的满足需求的构件个数查准率=检索到的满足需求的构件个数/检索到的所有构件个数第一个指标保证了构件的复用率。举例来说，当用户在构件库中检索构件时，他可能得到了一个较小的结果集合，并且这些结果都不满足他的需求。然而，构件库中还有其他的相关构件能满足需求，但用户却无从知晓，这就降低了构件被复用的频率。第二个指标降低了用户的理解成本。如果用户需要在一大堆检索结果中，逐一理解并排除掉和需求无关的构件，那么即便构件库中确实存在着解决问题的高质量构件，用户也只会退而求其次来自己重新开发该功能，因为他们认识到查找和理解构件的时间和精力成本过于巨大【6]。②易于理解和使用。不同的构件库有不同的查询语法，用户在使用构件库并输入查询信息时，需要使用特定的语言或语法。如果这种查询语言或者语法难以学习，那么用户检索构件的效率就会降低，从而增加了检索成本。同时，晦涩的查询语言或语法也会限制用户灵活正确地表达出自己的需求，从而达不到好的检索效果。正是基于以上这些考虑，本文研究基于语义的构件描述和检索方法，以改进构件检索的性能。LZ相关工作基于构件的软件开发(CBSD)是近年来国内外软件界研究的热点之一。它能提高软件系统的可靠性和产品质量、提高开发的效率、缩短产品的开发周期和上市时间、降低开发人员的技术需求和开发成本【7]。大规模的软件复用要求有足够数量的构件支持，而对这些构件的管理所涉及到的构件描述和检索方法是实现软件复用的一项关键技术。目前已经有很多组织和研究机构对此作了大量的探索，并提出了许多构件描述和检索的方法，但每种方法都有其各自的长处，也都存在一定的不足。这些方法主要被分为如下5类【8]:简单的关键字和字符串查找、型构匹配、行为匹配、基于刻面的分类和检索、基于语义的构件描述和检索。 基于语义的构件检索系统研究与实现1.2.1关键字和字符串查找这是一种简单而且为人们所熟悉的方法，采用了基于关键字匹配的传统的图书馆及信息科学编目查询技术。在该方法中，软件构件以一组与之相关的关键词编目，这些关键字可能是由构件的提供者输入的，也可能是从软件构件的自然语言描述文本中自动抽取的。构件的查询者给出一组感兴趣的关键字来描述所需的构件。检索算法主要是计算查询关键字与构件描述关键字之间的匹配程度，来返回候选构件集。这种方法最大的好处就在于简单，不但便于检索者使用，同时也利于在具体的应用中实现。但基于关键字的方法只和字符串的形式有关，却忽略了字符串所代表的语义，使得构件的查询效率受到限制。例如，自然语言中与生俱来的多词同义与一词多义，就分别对查全率和查准率有着极大的影响。如果用户使用的关键字与构件描述的关键字虽然不同，但表示同一个语义，这个有效构件就会在检索时被遗漏;如果用户使用的关键字与构件描述的关键字相同，但分别表示了不同的语义，这个无效的构件就会被检索出来，增加了用户的理解成本。基于关键字方法的另一个弊端是忽略了用户查询的关键字的上下文语境以及关键字之间相互的逻辑联系。针对这个问题，Zaz。等人对信息检索领域进行了研究，提出把用户查询的关键字集合作为一个整体来考虑，使用相似性词典，在用户查询中补充进最相关的关键字集合来扩充原先的查询，以得到更为准确的检索结果【9]。这从很大程度上弥补了关键字之间缺乏逻辑联系的弊端。1.2.2型构匹配(signatureMatching)型构匹配关注构件所提供的接口的参数类型和参数数量，这是一种基于形式化规约的编码和检索方法。用户在查找构件时，提供所需功能的输入参数类型和数量，以及输出参数的类型，来找到提供该接口的候选构件集合。这种方法基于形式化的理论背景，排除了查询的二义性。同时，又比较符合构件用户使用构件的方式。但这种方法有诸多弊端。对于构件来说，接口的型构与其所提供的功能语义往往不具有一一对应的关系。两个方法有相同的型构，却未必提供相同的功能，例如Listsort(col1ectionc)对集合中的元素进行冒泡排序，排序结果是稳定的，而另一个相同型构的方法对集合中的元素进行快速排序，排序结果是不稳定的。反过来，两个方法也许有相同的功能，但它们的型构却未必 基于语义的构件检索系统研究与实现完全相同，可能在输入参数的数量或者前后顺序上并不一致。这直接导致了构件检索的查全率和查准率的下降。另外，这种方法大多采用精确匹配，较难计算部分匹配的匹配度。1.2.3行为匹配行为匹配是与构件检索的目的关联得最紧密的一种方法，因为它直接考虑了构件的执行行为。在这种方法中，用户在查询时提供输入向量以及预期的输出。所有在执行后得到的输出与预期输出相同的构件，被作为候选构件返回给用户。这种方法对用户来说非常直观，也具有比较高的查准度。这种方法需要用户首先提供一组测试用例才能使用，但这并不是一个弊端，因为如今基于测试的开发和极限编程己经越来越受到重视。行为匹配的弊端在于应用范围过窄，只对可单独运行的构件有效。但构件库中的构件并不全是可运行的代码，有时候还包括分析或者设计文档，这些同样也是可复用的软件资产。行为匹配的第二个弊端在于检索效率的低下。由于构件库中的每一个构件都要尝试运行测试用例，对于保存了大量构件的构件库来说，用户的检索成本会变得非常大。行为匹配的最后一个弊端是只适用于精确匹配，较难使用部分匹配算法，这导致了查全率的下降。1.2.4基于刻面的分类和检索基于刻面的分类描述和检索是目前在实践中应用最为广泛的一种方法[4]【5]。这种方法包括三个主要组成部分:①刻面分类方案;②每个刻面下的术语层次空间;③各个构件的刻面描述集合。图1一1是一个构件描述刻面树及术语空间的部分示例【101。 基于语义的构件检索系统研究与实现RRootNOdeeFFunetionalityyEllvifoflmenttAAetionnMediaaHardwareeSoftwareeDDBB酗口刻面〔〕术语图1一1构件描述刻面树及术语空间的部分示例刻面(Facet)反映了观察构件的不同视角，它们之间按照组成关系(part一of)构成一颗树。例如图1一1中，一个构件有两个刻面视角:功能与运行环境。这两个刻面又由各自的子刻面组合而成。所有的刻面综合在一起，可以全面地描述一个构件的本质特性。每个叶子刻面可以赋予一个术语仃七nn)，表示构件在这个叶子刻面上的取值。术语按照一般一特殊关系(subelass一of)构成一颗树，术语的层次空间同时也代表了对应的叶子刻面的取值空间。用户检索构件时，对感兴趣的叶子刻面进行赋值，构成一颗查询树，与构件库中构件的描述树进行匹配。于是，构件的检索就转化为树匹配的问题，这个问题的研究已有许多成果【川【12]。构件的刻面描述能够表达丰富的构件信息、方便管理和查询，因此被目前大多数企业的构件库采用「13]【14]。REB00T、NATo提出的构件分类方法都是基于刻面的，北京大学青鸟构件库也采用了以刻面分类为主，多种分类模式相结合的方法对构件进行分类描述【141。上海构件库也采用了基于刻面的构件库管理系统。刻面分类法主要的弊端在于:①建立和维护构件库中所有构件的刻面分类的代价十分高昂;②术语空间的一般一特殊关系可以支持构件检索的模糊匹配，但其表达能力仍然十分有限。术语之间的关系过于单一，导致匹配过程中无法运用语义进行推理;③刻面及术语方案往往只能满足构件一般的描述需要，而无法体 基于语义的构件检索系统研究与实现现特定领域及特定功能的描述内容，这也是刻面分类方法最大的缺点。举例来说，刻面方法中对于术语空间较为稳定的刻面，如使用环境、开发工具等，容易进行预先的分类和描述。这是由于这些刻面对于所有的构件含义相同的原因。但对于构件的功能，由于不同领域的构件具有的功能不同，因此功能刻面所对应的术语空间的共性较少。这导致对于构件检索来说最重要的功能刻面，构件的描述反而比较粗略，降低了构件检索的查准率和查全率。1.2.5基于语义的构件描述和检索以上四种方法由于缺少特定领域的语义信息，因此在查准率和查全率上存在不足。针对这些问题，许多学者提出对基于语义的构件检索方法进行研究。文献【3]对基于语义的构件描述和检索方法的总体框架进行了阐述，认为基于语义的构件描述和检索方法应该包含以下三方面的优势:①将软件构件视为领域本体基础上的语义描述体;②允许用户使用自然语言表达检索请求，然后将其自动转化为语义描述框架。由于构件描述和检索请求使用相同的语义描述框架，因此可以提高检索的查准率和查全率;③在领域本体基础上通过用户查询语义表示与构件语义描述之间的语义匹配来改进检索效果。这里提到的本体正是用来描述或表达某一领域知识的一组概念或术语。该框架虽然没有涉及其中每一步的细节技术，但是概括了基于语义的构件描述与检索的基本特征，为以后的工作指明了方向。文献【10]提出使用本体来扩展传统刻面方法中的术语空间，并通过术语之间丰富的关系，来支持匹配过程中的语义推理，得到更高的查全率。文献【15]在基于案例推理(case一BasedReasoning)方法的基础上，提出通过会话的方式来筛选前一次检索得到的候选构件集合，以减少用户的理解成本。但该方法假设用户十分了解领域本体的表示方式，能够遵从系统的要求输入初始的查询请求，这显然限制了检索系统的实际应用，加大了用户的检索成本。文献【16]根据用户已经使用的构件，对用户进行分类。并把相似用户使用过的其他构件主动推荐给用户，而不是等待用户来检索，以增加构件的复用度。该方法利用了构件间的关系作为语义，得到了不错的效果。但该方法需要积累动态的语义信息，不利于尚无历史信息的用户检索构件。 基于语义的构件检索系统研究与实现1.3本文的研究工作基于语义的构件检索需要考虑领域知识、用户查询信息的上下文以及构件之间的相互关系。前文提到的文献〔10]和文献【15〕考虑了领域知识;文献[161考虑了构件间的关系。本文结合领域知识和用户查询信息的上下文，对如何用本体来描述构件的功能语义，以及如何降低用户的检索成本、减少查询努力进行了研究。研究内容和成果包括以下几个方面:①给出了基于本体的构件描述框架。本体阐明了知识的结构并且支持知识共享，使得机器可以基于知识进行逻辑推理。对于一个领域来说，它的本体构成了该领域内任何知识表示系统的核心。本文给出了描述领域功能的本体元模型，在此基础上建立的领域本体模型可以被我们的构件描述框架利用，以表达丰富的领域知识。②给出了基于会话和语义的构件检索过程。基于语义的构件检索在各个步骤都考虑到用户查询的语义以及相关领域的知识，因而具有较高的查准率和查全率。会话式的用户查询方案生成则将用户的自然语言查询转换为本体描述，在此基础上根据语义约束关系对原始查询方案进行扩展并根据初步的返回结果进行优化，从而最终确定用户的查询方案。该检索过程减少了用户的检索成本，提高了实用性。③提出了概念映射方法。针对用户对问题域的理解以及所熟悉的自然语言表达方式与构件的规范语义描述之间存在差异，本文使用概念映射将用户的自然语言查询转换为本体描述，从而确定用户的查询方案。本文假设用户输入若干英语的自然语言动宾短语，描述所需构件的各个功能。概念映射充分利用了用户自然语言描述中的上下文(主要由谓语、宾语、状语和定语组成)信息以及领域本体中的语义上下文之间的相似度信息，同时辅以交互式会话过程，让用户不必了解构件的规范语义描述方式，直接使用自然语言即可准确刻画自己的检索请求。④综合了两种相似度匹配算法，提出了一个构件相似度算法。该算法适合本文的构件描述框架，用于用户查询与构件库中的构件的匹配。⑤本文实现了整个构件检索系统。不但给出了构件检索的实例，同时对该系统的查准率和查全率进行了实验，并把实验数据与传统的构件检索方法进行比较，来验证本文所提出方法的效果。另外本文实验了构件检索系统在大规模构件库中的检索效率，以验证本系统的可行性。 基于语义的构件检索系统研究与实现1.4本文的组织结构本文共由6章组成。第一章:引言。在这一章中介绍了本课题的研究背景，描述了现有的构件描述和检索方法的机制和优缺点，并简略介绍了本文的研究工作和成果。第二章:基于本体的构件描述框架与检索过程。在这一章里，我们介绍了本体的相关知识和背景，包括本体的定义、用途、以及本体描述语言等。其中我们着重介绍了W3C提出的OWL语言。接着我们给出了本文使用的领域本体元模型以及形式化的构件描述框架。本章的最后我们给出了整个构件检索过程的全局视图。第三章:概念映射。本章描述了构件检索过程中的第一步，把用户的自然语言查询转化为系统内部的形式化构件功能本体描述。该章不但介绍了概念映射的思想背景，而且给出了概念映射的完整算法和其中使用到的各种公式，最后还分析了该算法的时间复杂性。第四章:语义匹配。本章描述了构件检索过程中的第二第三步。第二步扩展用户的构件查询，对形式化了的用户查询进行语义推理，以得到其中的隐含知识;第三步计算用户查询信息与构件库中构件的相似度。该算法综合了两种已有的匹配算法，以适应本文提出的构件描述框架。第五章:优化构件查询。在实际的构件检索过程中，用户往往要经过多次查询才能获得满意的结果。针对这一问题，本文使用交互式的方法，在分析前一次查询结果的基础上通过提问与用户进行会话，引导用户逐步优化自己的构件查询。本章给出了优化构件查询的算法，并且讨论了会话过程中系统对于问题进行排列的顺序。第六章:系统实现与实验数据分析。本章给出了两个构件检索的实例与相应的系统界面，对系统的查准率和查全率进行了实验，并把实验数据与传统的构件检索方法进行比较，来验证本文所提出方法的效果。最后本章实验了构件检索系统在大规模构件库中的检索效率。 基于语义的构件检索系统研究与实现第二章基于本体的构件描述框架与检索过程2.1本体(Ontology)本体的概念最早来自于哲学，它是对所存在事物的性质的研究。在计算机科学领域，第一个被广泛接受的本体定义是:对概念化的显式的解释说明【17]。这里的概念化，是知识的形式化表达的基础，是对领域内的对象、概念和其他实体，以及它们之间的关系的研究。另一个更靠近计算机科学的本体定义是:对共享的概念化的形式化规约「18]。其中的形式化是指无二义的、机器可读的。而共享则表示本体所捕获的是已经达成共识的知识。本体对于计算机科学的重要性有两点[19]:①本体阐明了知识的结构，使得机器可以基于知识进行逻辑推理。对于一个领域来说，它的本体构成了该领域内任何知识表示系统的核心。②本体支持知识共享。本体捕获了领域的内在概念结构，这是通过对领域进行分析得到的。我们可以与在该领域同样需要捕获知识表示的人共享这个本体，以避免重复的知识分析过程。这个被共享的本体也因此成为了特定领域的知识基础，大大地增加了知识复用的可能性。图2一1是操作系统领域的本体示例。本体中的概念主要由类(Class)和关系(Property)组成。类定义了因共有某些属性而同属一组的实例(Instance)，例如图中Win95和Win98都是类V肖ngx的实例。多个类可以用一般一特殊关系(subClassof)组织为一个特定的层次结构。需要注意的是，多继承在本体中是允许的，例如Wingx既是一种桌面操作系统，也是一种V西ndows操作系统。类的语义不仅取决于自己的文字标签，更取决于它与其它类之间的关系，因此关系是本体中非常重要的概念。除了一般一特殊关系之外，本体还能定义其他任何关系，以表达丰富的领域知识。对比图2一1和第一章的图1一1可以发现，两者最大的区别就是图2一1定义了后续版本(following)关系。定义在类上的关系说明了类成员的一般事实，例如一个操作系统可能是另一个操作系统的后续版本。关系同样可以通过一般一特殊(subPropertyof)关系组织为一个特定的层次结构。定义在类实例上的关系实例说明了该类实例的具体事实，例如win98通过folfowing关系关联到Win95，表示Wi心8是Win95的后续版本这样一个具体事实。 基于语义的构件检索系统研究与实现OOPeratingSystemm一一一~一一一叫弓..WWindowssDesktoP055SServer055WWingXXNTFamilyy图例口类〔〕实例一一一卜一般一特殊关系一实例化一fouowing-争后续版本关系一following-，后续版本关系的实例图2一1操作系统领域的本体示例本体还可以在关系上定义规则，例如可以定义folfowing关系满足传递(肠阶sitive)规则，这意味着在following关系上成立如下公式:(afollowingb)八伪fonowingc)今(afolfowingc)。正是由于关系以及规则，使得机器可以自动推理并获得隐含的领域知识。如果用户的检索请求需要一个能在WinZ000上运行的构件，那么运行于Win98上的构件也是符合要求的，因为能够运行于Win98上的构件同样可以运行于V百nZ000上，这是由操作系统向下兼容的特性决定的。可以看到，本体正是通过对概念及其相互关系的规范化描述，勾画出了特定领域的基本知识体系。2.2本体描述语言0、VLOWL是2004年2月w3corg发布的w七b本体语言【20]【21〕，其目的就是为了让应用程序而不是人来处理领域中所包含的知识。OWL是逐步从RDF、RDFS、 基于语义的构件检索系统研究与实现DAML+OIL演化而来的，它也沿袭了RDF的基本事实陈述方式以及RDFS的类和属性分层结构〔22]。oWL提供了三种表达能力递增的子语言，来满足不同的应用需求，它们分别是OWLLite、OWLDL和OWLFull，如图2一2所示。OWL九!!OWLDLOWL翻teRDFSROF图2一ZOWL关系图OWLLite用于提供给那些只需要一个分类层次和简单约束的用户。例如，虽然OWLLite支持基数限制，但只允许基数为0或1。支持OWLLite的工具应该比支持其他表达能力更强的OWL子语言的工具更简单，并且从辞典(thesauri)和分类系统(taxonomy)转换到oWLLite更为迅速。相比oWLDL，oWLLite还具有更低的形式复杂度。OWLDL支持最强的表达能力，同时又能保持计算完备性(comPutatinnalcomPleteness，即所有的结论都能够确保被计算出来)和可判定性(decidability，即所有的计算都能在有限的时间内完成)。OwLDL包括了OWL语言的所有语言成分，但使用时必须符合一定的约束，例如，一个概念是类时，不能同时是另外一个类的实例。OWLDL这么命名是因为它对应于描述逻辑，这是一个研究一阶逻辑的一个特定可判定片断的领域。OWLDL旨在支持己有的描述逻辑商业处理(businesssegment)和具有良好计算性质的推理系统。OWLFun对应于一阶逻辑，用于支持那些不需要可计算性保证，但需要最强的表达能力和完全自由的RDF语法的用户。例如，在OWLFull中，一个概念可以被同时看为一个类以及一个实例。OWLFull允许一个本体增加预定义的(RDF、OWL)词汇的含义。这样，不太可能有推理软件能支持对OWLFull的所有成分的完全推理。在表达能力和推理能力上，每个子语言都是前面的语言的扩展，用户需要根据自己的应用程序来选择适合的子语言。这三种子语言之间有如下关系成立，但这些关系反过来并不成立: 基于语义的构件检索系统研究与实现每个合法的OWLLite本体都是一个合法的OWLDL本体;….每个合法的OWLDL本体都是一个合法的OWLFull本体;每个有效的OWLLite结论都是一个有效的OWLDL结论;每个有效的OWLDL结论都是一个有效的OWLFull结论。下面我们来看看OWL如何描述图2一1所示的操作系统领域本体:<记fs:subClassO卜<厅dfs:subClasso介叼rdfs:subClasso介<角wl:ClasS>叼rdfs:subClasso介<川fs:subClassO卜<厅d伪:subClassO介<沁wl:ClasS><沁wl:ClasS>叼rdfs:subClassO介叼rdfs:subClasso介刁。wI:肠明sitiveProperty>引一②--><八叭ngx><八叭ngx><加叉少amily><加叉少amily>代码2一1操作系统领域本体的OWL文件l9 基于语义的构件检索系统研究与实现上面owL语句的①处定义了满足传递(肠ansitive)规则的关系following，并于②处运用于个体实例上。为了表示丰富的语义，OWL预定义了若干种不依赖于领域的关系规则，传递规则就是其中的一种，其他常见的规则见表2一1。表2一1常见的OWL预定义规则OOWL预定义规则解释eequivalentClasss声明两个类是等价的，即它们拥有相同的实例eequivalentProPertyy声明两个关系是等价的，即它们出现的地方可以相互替换换SaSl)leASS声明两个实例是相同的ddifl贻ren1Fromm声明两个实例是不同的iniverseoff声明一个关系和另一个关系互逆肠肠助sitiveProPertyy声明一个关系是传递的SS势刀metrieProPertyy声明一个关系是对称的，即它的定义域和值域可以互换FFunctionalProPertyy声明一个关系不能取多个值2.3功能本体元模型在基于语义的构件描述和检索中，本体往往作为知识基础存在[3][7][231。本体是对特定领域的显式概念化，并提供了对该领域普遍和共享的知识理解[24]。对于语义构件检索来说，本体可以为构件以及查询的描述提供明确的语义词汇表，并且可以支持基于公理和语义规则的推理。此外，w3c所推荐的owL(weboniologyLanguage)[2习等本体描述语言也使得基于本体的构件描述和检索更加容易。本文的方法同样采用OWL作为领域模型和构件语义的描述基础，并在此基础上定义了相应的本体元模型(图2一3)。 基于语义的构件检索系统研究与实现OOPerationnobjeett薰薰黝赘豁曝纂纂薰薰瓢蘸馨罐罐鬓薰黝黝那那d:助oleann一公公一TTermm盆盆云d:Integerr缨缨缨赣蘸蘸owl:CI韶sowl:ProPertyrdf:datatyPeSubCI韶SOfrdfs:domainrdfs:range图2一3面向构件语义描述的领域本体元模型构件的描述信息由三方面组成，分别是构件的基本信息、构件的功能信息和构件的非功能信息(也被称为Qos，服务质量)。其中构件的功能信息是复用者了解并判断构件可复用性的首要依据【26]。用户往往在确定构件提供了所需功能的情况下，才会去关注构件的版本、提供商、使用的技术等基本信息，以及响应时间、安全性等Qos信息。另一方面，构件的基本信息和Qos信息都是不依赖于特定领域的，可以使用1.2.4小节介绍的基于刻面的分类方法进行描述。因此本文主要关注于构件的功能语义描述。我们在前期基于本体的构件语义描述工作[26〕基础上，定义了面向构件语义描述的领域本体元模型如图2一3所示，主要由构件的功能操作(OPeratinn)、操作对象(。句ect)、功能操作和操作对象的语义刻面(Facet)、刻面取值术语(T七nn)以及功能操作和操作对象之间的操作关系(Aoton)组成。钾eration和。句ect分别表示构件所提的功能操作和所操作的业务对象，被定义为OWL类(owl:Class)。Acton被定义为OWL关系(owl:Property)，其定义域(rdfs:dom抓n)和值域(rdfs:range)分别为OPeration和object。Facet用于精确描述OPeration和object某个方面的语义特征，其值域为术语(1七nn)或者普通数据类型(ulf:datatyPe)。关系hifer描述术语之间的隐含推理关系。图2一3中的三个owL 基于语义的构件检索系统研究与实现类Operation、。句ect和介nn都可以根据本体中的子类关系(subClassof)形成各自的类层次结构。在这个本体元模型的基础上，我们可以定义特定领域的本体模型。图2一4给出了多媒体处理领域本体模型的一个片断，其中处理(Proeess)操作有四个子功能操作，分别是读取(Read)、缩放(Resize)、旋转(Rotate)、剪辑(Edit);媒体(Media)对象有三个子操作对象，分别是图象(Image)，视频(Vidco)，音频(Andio)。Read操作在Image、vidco、Audin上，表示读取一个多媒体对象，同时还有一个语义刻面HasLocation，表示读取的位置，术语取值空间为{任意位置(切eation)，文件(Fil。)，统一资源定位符(URL)，扫描仪(scaner)}。Resize和Rotate操作在Irnage上，表示改变图象大小和旋转图象角度。Edit操作在vidco和Andi。上，表示剪辑视频和音频信息。Image有两个语义刻面，分别是图象格式(HasFormat)和图象类型(Has尸乃甲。)，前者的术语取值空间是{任意格式(Format)，BMP，TIFF，JPEG}，后者的术语取值空间是{任意类型(，巧pe)，点阵图(BitrnaP)，矢量图(vector)}，从扫描仪读入的图象隐含了该图象类型是点阵图的事实。劝dco有语义刻面HasFormat，术语取值空间是{任意格式(Format)，MPEqAvl，流媒体格式(streamingF~at)，RM，AsF}，从统一资源定位符读入的视频隐含了该视频格式是流媒体格式的事实。Andin有语义刻面HasFormat，术语取值空间是{任意格式(Format)，珊钱MP3}。RRotateReS泳图2一4多媒体处理领域的本体模型 基于语义的构件检索系统研究与实现本文的领域本体中所定义的语义刻面不同于传统的刻面描述方案(即为构件定义一套普遍适用的刻面方案)，而是将刻面定义在各个语义概念(功能操作和操作对象)上。在这种领域本体中，功能操作和操作对象按照子类关系分别构成层次结构，高层概念上定义的语义刻面都适用于其所有的子概念。每个概念上的刻面描述(包括Acton关系)都是对其父概念刻面取值的精化，同时还可以定义新的刻面，因为随着语义的精化可能产生新的语义特征【26]。例如图2一4中Process概念作用在(Acton)对象Media及其所有子概念上，而Proeess的子概念Read在Aeton关系上精化为Media的子概念集合{加age，叭deo，Andio}，并且定义了自己的刻面HasLocation来表示其特定的语义特征。2.4构件语义描述框架构件语义描述框架是构件语义的规范表示，同时也是用户构件查询方案的描述模板。在我们的方法中，查询用户不需要熟悉此描述框架以及所使用的领域本体，其查询方案将通过交互式会话进行启发并根据语义关系自动进行扩展和优化。本文所使用的构件语义描述框架以图2一3所定义的本体元模型为基础，以构件的功能语义作为主要的描述内容。下面首先定义本体关系表示法和概念约束集合，并在此基础上给出本文所使用的构件语义描述定义。定义2一1(本体关系表示法):三元组表示领域本体中subj和obj之间存在Prop关系，其中PropEowl:Property，subj任domain印roP)(prop的定义域)，objErange(proP)(Prop的值域)。定义2一2(概念约束集合):对于VconcePtEOPerationuobjeet，conc即t上的约束集合FTs(concePt)={}facetEFacet八facet、恤lueE飞’ennUxsd:sooleanUxsd:Integer八满足}。定义2一3(构件语义描述):构件语义描述csD=。其中operation任OPeration八。bjectE0bjeot八(日acton任Aeton，满足<叩eration，acton，Object>)。一个构件可以有多条构件语义描述，每条代表了一个功能。在构件语义描述中，定义在功能操作(OPeration)和操作对象(Object)上的语义刻面(Facet关系)构成了对相应概念的语义约束，同时也为这些功能操作概念提供了语义上下文。根据构件语义描述的定义，每个构件的语义描述体现一个语义功能，由操作行为(。peratinn)、业务对象(object)以及相应的概念约束( 基于语义的构件检索系统研究与实现二元组)集合组成。一个具体的构件语义描述的例子为CSD=}，Vidco，{}>，该语义功能表示从URL读入RM格式的视频。定义2一4(约束刻面集合):对丫esn，Facet(CSD.FTs(eone即t))={faeet}faeet任First(FTs(eone即t))}，其中eoneept=CsD.operationVeone即t=CDS.objeet，First表示FTs(concePt)包含的所有二元组的第一个元素组成的集合。定义2一5(约束术语集合):对丫CsD，介nn(CSD.FTs(eone叩t))={term}teneTennnseeond(F孔(eone叩t))}，其中eone叩t=esn.operationVconcePt=cDs.objeet，Seeond表示FTs(concePt)包含的所有二元组的第二个元素组成的集合。2.5构件检索过程基于语义的构件检索在各个步骤都考虑到用户查询的语义以及相关领域的知识，因而具有较高的查准率和查全率【7]。然而从当前一些研究工作看，基于语义的构件检索仍然存在一个突出的问题，即用户对问题域的理解以及所熟悉的自然语言表达方式与构件的规范语义描述之间存在差异。这一问题导致了如下三个主要困难:l)自然语言词汇的一词多义和多词同义造成了用户的自然语言查询向语义概念映射的困难;2)除了直接指定的查询条件，用户的查询请求中还包含着许多隐含的语义，这些隐含语义的缺乏可能影响语义匹配的效果;3)用户很难一次就准确表达出自己真正的检索需求，这与用户对自身需求的认识不够清晰以及对目标构件库中构件描述方式和潜在候选构件的了解不足都有关系。针对以上这三个困难，本文提出了一种面向语义构件检索的交互式查询方案生成方法。该方法首先通过概念映射将用户的自然语言查询转换为本体描述，在此基础上根据语义约束关系对原始查询方案进行扩展，并根据初步的返回结果进行优化，从而最终确定用户的查询方案。其中，概念映射充分利用了用户自然语言描述中的上下文(主要由谓语、宾语、状语和定语组成)信息以及领域本体中的语义上下文之间的相似度信息，同时辅以交互式会话过程。而查询方案优化过程则根据初步的查询返回结果计算可能的优化方案，并通过交互会话引导用户进行确认。该方法可以充分挖掘潜在的用户查询语义，对于提高构件检索的查准率和查全率、减少查询努力具有十分重要的作用。基于语义的会话式构件检索(图2一5)扩展了传统的构件检索过程，突出了用户查询方案的创建、扩展和优化过程。其中各个步骤的任务如下: 基于语义的构件检索系统研究与实现l)用户需求描述:用户使用自然语言描述构件需求。2)查询方案创建:首先，概念映射步骤把用户的自然语言词汇映射到领域本体中的概念。如果领域本体中的语义不足以推理得到全部的映射，则需要和用户进行会话来完成映射。然后，填写构件描述框架步骤把映射得到的概念填写到2.4小节定义的构件语义描述框架中，完成初始的构件查询方案的创建。3)查询方案扩展:用户的构件需求中除了显式的需求，还有一些隐式的需求可以通过推理得到。扩展构件查询步骤通过领域知识推理得到这些隐式的需求。4)匹配度计算:计算用户查询和构件库中的构件描述的匹配程度。5)候选构件陈列:按照匹配程度的高低排序，返回超过阂值的候选构件列表。6)查询方案优化:当用户认为候选构件过多时，通过与系统的交互，添加新的构件约束描述，来得到更精确的候选构件列表。22.2.二填二写写一一噪霖构构甲件甲描述框架架万万6一优化、.构.件查询候候55选.返构回件件霆摹聂肌巨口操作.圈基于语义的操作必甲基于语义和会话过程的操作一卜人机交互---扮数据流图2一5基于语义的会话式构件检索过程 基于语义的构件检索系统研究与实现第三章概念映射创建构件查询的第一个步骤是概念映射。Bailin等【23]认为用户的复用需求隐含着基于个人认知的领域本体，而揭示复用需求和构件描述的真实含义的过程是一个本体协商的过程，如图3一1所示。一竺巡竺Inte印retq应犯二二二应巫止十十成赫雨赢厂一，Confirmation七‘‘图3一1本体协商过程本体的协商有两种形式:①一方可以对另一方先前使用的术语进行理解，并请求另一方判断这个理解是否正确;或者②一方在无法理解对方使用的术语时，要求对方进行进一步的阐明。这里的阐明意味着用另外的术语来进行替换，比如同义词、逻辑定义、子概念、超概念或者是实例。他们在文献【23〕中提出了一个语义构件检索的理想场景，即通过语义推理和一系列问答式的会话过程，将一个本体中的概念映射到另一个本体中的概念，就如同构件用户和构件提供者直接面对面地进行探讨并达成共识那样。一次具体的会话可能像下面这样:User:I，mlookingforafilterthatsends廿iroughoulyhighqualitydata·SAA:”Highquality，，eanmeaneither”goodsignal，，or”relevantcontent，，.Whatdoyoumean?User:Goodsignal.SAA:TMC--NEAR一NN0315aneujralne七形。众basedfilterthatPassesthroughgoodsignal.User:15ittunable?SAA:W】latdoyoumeanby’，tunable，，?User:Canitlearn?SAA:TMC--NEAR少诩03wastrainedbyabackpropagationalgorithm.User:B讯eanitberetrainedas1useit? 基于语义的构件检索系统研究与实现SAA:TMC--NEAR-NN03eanberetrainedbychangingtheinPutoroutPutdata.User:Canitberetrainedasitruns?SAA:1don，tunderstandthisquestion.User:15thetrainingsoftwarePartoftheruntimePaekage?SAA:Thetrainingsoftware15available.User:Canthenetworkbechangedoneethefilter15running?SAA:1don，tknow.LetmePointyoutotherelevantPartofthedocumentation.其中User表示构件的检索者，而SAA代表了一个构件库管理系统。在这个示例中，检索者在寻找一个去除低质量卫星信号的过滤器，而系统让用户澄清了“低质量”代表的含义是“低的信噪比”还是“低相关度的内容”。在整个会话过程中，系统通过询问问题来揭示用户描述中的二义性或者不一致性，使得最终检索到的构件更加符合用户的要求。Baihn等在文章的最后说这只是一个伟大的预想，他们并没有真正实现这个构件库管理系统。正如他们所说，虽然这个预想中的构件库管理系统使用纯粹的自然语言接口，但稍微限制的接口才是更切合实际的。本文在概念映射这一步骤中正是通过用户与构件库系统之间的会话式过程完成这一本体协商任务。概念映射在本体和语义网领域中有着大量的研究工作，例如文献[271使用相似度计算，在两个机器系统之间自动完成本体概念的映射。而本文面向语义构件检索这一特定目标，而且在查询表达阶段有用户参与，因此可以使用交互式会话过程更准确地把用户词汇映射到领域本体概念。为了完成自然语言词汇到领域本体概念之间的转换，可以使用预先建立的概念词典[28]，如图3一2。在语义信息缺乏的情况下，概念词典只能实现词汇到本体概念的多对一映射，从而解决自然语言中的多词同义现象，例如将电脑和计算机都映射到本体概念Computer。而自然语义的一词多义问题就比较难解决了，例如Java一词可以同时表示Java编程语言(Progr~ingLanguage)和一种咖啡(Coffee)。概念映射的另一个困难是概念词典常常无法覆盖所有的用户词汇，用户可能会使用生僻的词汇来表示心目中的概念，由此可能产生无法被概念词典识别的“孤儿词汇”。 基于语义的构件检索系统研究与实现人口日~........-…lr-ee.~~~.，t忱浏滋邸二嘟麟邸概念忱nn概念t日nn概念概念鲍少~一啥;洲::~~~~~~，.t七口n愿形概念l扭图3一2概念词典因此，语义概念映射不仅取决于词形的匹配，还应该考虑自然语言上下文与本体语义上下文之间的关系。如果领域本体中包含足够的语义信息，那么这些困难可以借助语义上下文信息来解决。例如一词多义问题可以根据用户输入的句子中的所有词汇以及词汇之间的语法关系进行整体的概念映射来解决:当Java和Class、Object等词汇一同出现时，Java被映射为一种Java编程语言;而当Java和Drink、CuP等词汇一同出现时，Java被映射为一种咖啡。对于“孤儿词汇”问题，可以首先识别用户句子中的己知概念，然后根据“孤儿词汇”与已知概念间的关系，推测“孤儿概念”最有可能对应的概念。如果有多个候选取值，系统可以通过会话的方式，征询用户的意见，得到准确的映射。同时系统也可以根据反馈结果不断丰富概念词典。3.1概念映射算法本文假设用户输入若干英语的自然语言动宾短语，描述所需构件的各个功能。系统分析每一个动宾短语，把它们映射为构件的规范语义描述(2.4小节，定义2一3)，从而使构件库系统能够识别并与己有构件描述进行匹配。在映射过程中，用户句子中的动词和宾语将被映射为构件的功能操作概念和操作对象概念，而状语和定语则分别映射为功能操作和操作对象的语义刻面描述。例如用户输入构件查询“功putaJPEoimagefromscaner”，系统将其映射为esn=}，Ilnage，{}>。首先我们给出用户查询短句的结构定义，这种结构可以使用语法分析工具(例如MINIPAR【29])对用户输入句子进行切分得到。定义3一1(动宾短语):用户输入的英语动宾短语可以描述为四元组NL=，其中P是谓语，O是宾语，ADVs是状语(描述谓语)词汇集合，ATTs是定语(描述宾语)词汇集合。定义3一2(概念和词汇的词根集合):对丫eone即t任owl:ClassUowl:Property，R(concePt)表示conc印t名字标签的词根集合;对任何自然语言短语x，R(x)表示x包含的所有词汇的词根集合〔27]。定义3一3(刻面词汇集合):对丫eoneePtEOPerationUobjeet，Fwords(concePt)={x}xE甲R(faeeti)，其中faeeti是领域本体中第i个约束描述concePt的刻面概念}。定义3一(术语词汇集合)对丫eone叩t任OPerationUobjeet，Twords(eonCPet)={x}xE目R(termi)，其中termi是领域本体中第i个约束描述conc即t的术语概念}。定义3一5(约束词汇集合):对丫conc印tEOPerationU0bject，Fl’words(eone印t)=Fwords(con印et)UTwords(eon印et)O在此基础上我们给出构件查询方案概念映射算法如图3一3。 基于语义的构件检索系统研究与实现输入:四元组NL=输出:构件语义描述Quer又CSD=(l)根据相似度计算公式7(见3.2小节)计算与每一个的相似度sIM。其中operationEOperation八objeetEobjeet八(三actonE^cton，满足)。(2)把SIM超过闽值minSIM的所有作为候选集合。(3)如果候选集合不空，把候选集合根据相似度SIM排序。假设相似度最大的映射SIM=k，则取出所有相似度大于(k一maxDIFF)映射作为最佳映射集。(4)如果最佳映射集只有一个元素，则本四元组NL的映射完成，跳到(6)。(5)如果最佳映射集不止一个元素，则启动会话过程，把这些映射呈现给用户，由用户确定最佳映射。(6)假设找到的最佳映射为。(7)如果概念词典中没有P到叩erationi的映射，则把该映射加入。(8)如果概念词典中没有O到objeetj的映射，则把该映射加入。(9)对每一个状语词汇xEADvs(10)如果x任Twouls(operationi)，则在FTs(operationi)中加入概念约束二元组，其中facet任Facct且满足。(ll)如果xETwords(objectj)，则在FTs(objeetj)中加入概念约束二元组，其中facetEFacet且满足。(12)对每一个定语词汇xE户L1，rs(l3)如果xETwouls(objectj)，则在FTs(objectj)中加入概念约束二元组，其中facetEFacet且满足。(l4)创建Que以--CSD=<叩eratinni，FTs(oPerationi)，objectj，FTs(objeetj)>。(l5)返回Que乃乞仁SD，算法完成。图3一3构件查询语句概念映射算法本算法分两步完成，首先通过相似度计算和会话，把二元组映射到本体中有Acton属性关联的二元组，随后把用户输入的状语集和定语集映射到本体中约束描述操作行为和业务对象的刻面和术语。其中的第一步是本算法的重点，把用户的需求定位到一个被具体识别的功能。第二步则是挖掘 基于语义的构件检索系统研究与实现用户对功能的约束，减少被选出的构件数量。算法的第n步把状语词汇映射到本体中约束描述操作对象(objeet)的术语词汇，这种情况一般出现在方向状语包含的名词中。比如convertanimagefromBMPformattoJPEGformat，其中的fromBMPformattoJPEGformat在语法上属于状语(描述谓语)，但BMP和JPEG描述的却是宾语。3.2概念映射的相似度本文的概念映射主要是根据用户自然语言查询句子与领域本体中相关概念语义上下文的整体相似度来进行判断，包括用户输入的自然语言词汇与领域模型中的概念间的词汇相似度以及上下文信息之间的结构相似度。NL中的谓语P和领域模型中的某个操作行为叩eration的词汇相似度如下:孟弧人(尸峥operation)如果概念词典中丰护到operation的映射={.，(。。*(op一tio。.{.*(。。*(operatl’o。.否则类似地，NL中的宾语O和领域模型中的某个业务对象object的词汇相似度如下:人服七(口分口勿仑ct)如果概念词典中二散理肠bj’ec哟映射(2)={}*(。。*(口、。}{!*(。。*(口、。。}否则自然语言的上下文信息主要体现在状语和定语上。如果状语集合的词汇出现在约束描述某个功能操作概念的刻面或术语词汇集合中，则谓语P和该功能操作operatinn的结构相似度增加;如果定语集合的词汇出现在约束描述某个操作对象概念的刻面或术语词汇集合中，则宾语。和该操作对象objeet的结构相似度增加。另外，我们使用M取任城R【29]对CedeProject〔30]所提供构件的40多个功能进行语法分析后发现，定语集合的词汇出现在操作对象的标签词汇中同样会增加宾语O和该操作对象。bject的结构相似度。这是由自然语言的特性决定的。自然语言往往会把操作某个事物，说成操作某个事物的属性。比如Rescaleanimage表示放大缩小图片，用自然语言可能表达成Rescalethesizeofanimage，其中image成为size的定语。在计算相似度时，我们需要把sizeofanimage映射到 基于语义的构件检索系统研究与实现image。另外，基于和3.1小节算法第11步相同的考虑，状语集合的词汇出现在约束描述某个操作对象概念的刻面或术语词汇集合中，宾语O和该操作对象object的结构相似度也会增加。根据以上分析，宾语O和某个操作对象。bject的结构相似度、谓语P和某个功能操作operation的结构相似度分别如下:肚材c(O一>objeet)}{x}x0A77k门(尸厂沁orde(obj’ect)口R(objeet川+}{x{x。月刀Vs门尸r沁田汤(obj’ect)}}{{xlxoA了7云}卜}{x!x。月刀价门尸子沁口rde(obj’ect)}l如果分母为O，表示用户输入可能没有定语词汇，则SIMC(o今object)=N/A。}{xlx0AD价门尸罗沁口犷山(operation)}}人从了。(P一>operation)二}{xI‘任AD喝!一吧!{xI‘“ADVs门FTw口rds(object’川其中，日actonEActon，满足句peration，acton，objeetj>。如果分母为0，表示用户输入可能没有状语词汇，则SIMC(P令oPeration)=N/A。综合文字相似度和结构相似度，P和oPeration的相似度公式如下:人刀以(尸今operati口n)敌材七(尸”operation)SIM七(尸分operation)=N/A{(敌材云(尸分operation)+人甜七(尸”operation))/2SIM七(尸斗operation)笋N/Ao和objeet的相似度公式如下:人刀以(O一ob，’ect)敌材:(O峥object)SIMc(O峥Obj’eet)=N/A(欲材乙(O分object)+改刀以e(O”obj’ect))/251材c(O分obj’ect)笋N/A最后，二元组与有Aoton属性关联的<叩件以ion，obje少二元组的相似度如下:S从了(分<叩erarion，objeet>)=(义材(P峥叩eratton)+召刀以(O分object))/2(7)3.3算法复杂度分析一般来说概念映射算法需要反复迭代，因此是一个NP完全问题「27)。但构 基于语义的构件检索系统研究与实现件功能描述有确定的二元组结构，因而可以避免迭代的过程。3.1节算法的第1步计算与每一个被Acton属性关联的<叩eration，object>二元组的相似度。假设领域模型中共有n个oPeration概念，m个objeet概念，每个operation概念通过Aeton属性和ki(i二o，l，…，n一l)个objeet关联。当n和m都很大时，k*近似于常数。因此第l步计算的相似度总数约为kn个，具有线性的时间复杂度。 基于语义的构件检索系统研究与实现第四章语义匹配在将用户的自然语言查询转换为规范的构件语义描述之后，我们接下去的工作就是在构件库中查找匹配的构件集合。这包括了2.5小节图2一5的第3和第4步，前者通过推理得到用户查询中隐含的需求，以利于找到更符合用户要求的构件，后者在第3步的基础上，计算用户查询和构件库中每个构件的匹配度，并按照匹配度的高低按序返回候选构件列表。4.1扩展构件查询如果构件功能的某一个约束描述可以通过已知的约束描述推理得到，该约束描述就应当自动地被加入到构件描述的框架中。对于领域中非常明显的隐含知识，这一步显得更为重要，这是因为用户可能在描述构件需求时，就已经默认了这个知识，如果在查找时未考虑这些隐含知识，那么会降低整个构件查询的效率，也会让用户对构件检索系统产生怀疑。领域模型或者领域规则可以用来对隐含的约束描述进行推理，这在我们的元模型中体现为图4一1椭圆圈内的hifer关系，它代表了两个术语值之间的推断关系。Legend:目一Owl:CI朋S。wl饰:沐勺rdfdatatyperdfs:dom，inrd丘range图4一1支持知识推理的领域本体元模型 基于语义的构件检索系统研究与实现在此基础上，我们定义推理规则如下:规则4一1(隐含约束描述推理):在用户查询Que乃乞CsD中，对丫t~eT七nn(FTs(oPeration))UTenn(FTs(object))，如果(三inferEInfer八日ten，ETerm，满足)八(日faeetEFaeet八(」eone即卜Que乃乞CSD.operationV]eonc即卜Que乃乞CsD.objeet)，满足)八(term，任飞七nn(FTs(eoneept))，则在FTs(eone即t)中加入约束描述二元组。这个规则说明，如果当前的用户查询QUe以--CsD中存在一个术语值tenn，它隐含了另一个术语值t~’，并且term，约束描述的正是当前的Quer先CsD所关心的OPeration或者是objeet，而t~’又不在当前Que巧乞CSD中，则把t~’以及关联到t~，的刻面faeet加入到约束描述的概念中。对于多媒体处理领域的本体来说，图4一2椭圆圈所示的正是一处隐含语义。它表示当用户需要一个能从扫描仪读入图片的构件时，他需要的一定是读入点阵图片的构件，而不会是一个读入矢量图片的构件。即便用户并没有明确输入这个需求，构件检索系统也可以自动推理得到。PPfO沈ssRRotateeResizcc图4一2包含知识推理的多媒体处理领域本体 基于语义的构件检索系统研究与实现4.2计算匹配度计算匹配度是整个构件检索过程的核心步骤，对其他各个步骤的研究也是为了在计算匹配度时有更高的查准率和查全率。由于前面已经进行的各个步骤都充分考虑到了领域知识，实际上间接辅助了匹配度的计算。本节匹配度计算的场景是:用户的构件描述已经通过前三步转化为了规范语义描述(QU吹九CSD)，构件库中的构件都已经按照语义描述框架入库，我们的目标就是描述用户需求与已发布构件的匹配算法。一个已发布构件与用户需求匹配，是指该构件提供了一个功能，与用户需求充分相似。这取决于我们如何定义“充分相似”，在最严格的情况下，构件功能与用户需求“充分相似”表示它们是完全一致的。这显然过于苛刻了，而且没有考虑语义关系，导致查全率过低。为了允许“充分相似”更为宽松，我们需要匹配引擎执行更加灵活的匹配，也就是在本体支持的基础上计算发布构件与用户需求之间的相似度。4.2.1匹配算法在构件库中寻找与用户查询匹配的构件的主循环如图4一3，如果二个构件(advertiselnent)与用户查询(Query-夕SD)是匹配的(即匹配度大于0)，则它被记录下来并在结果列表中排序，以找到匹配度最大的构件。match(Query---CSD){matchedList=。叮Ptylistforeveryadyinadvertisements，do{sim=match(Qu《光CsD，ady)ifsim>0thenaddtomatchedList}retumsortedmatchedList图4一3匹配算法的主循环 基于语义的构件检索系统研究与实现对于一个构件来说，它可能包含若干功能，因此构件与用户查询的匹配度就取决于构件中与用户查询最匹配的功能的匹配度，具体的算法如图4一4。match(Quer)乞CSD，ady){sim二0.0foreveryFun-仁SDinady，do{iffunsim书atch(Query-CSD，Fun-CSD)andfunsim>simthen51们n=九nsimretumSlm图4一4用户查询与构件的匹配算法接下来我们需要计算的就是用户查询与每一个具体功能之间的匹配度了，这两者都符合2.4小节定义2一3的构件语义描述CsD=。由此可见，用户查询与构件功能之间的匹配度，取决于这两者的语义描述中所包含的概念之间的关联度。举例来说，如果用户查询需要的功能是剪辑ASF格式的视频文件，那么一个具有剪辑流媒体格式视频文件功能的构件就完全符合要求，这是因为在我们的多媒体处理领域本体中(2.3小节图2一4)，流媒体格式(streamingFormat)是AsF格式的父类，也就是说这个构件提供的功能包含了用户所需要查询的功能。下面首先给出两种不同类型的功能匹配度算法，然后结合本文所采用的本体元模型，给出我们所使用的功能匹配度算法。4.2.2基于集合论观点的功能匹配算法Pauhicci等人在文献[31]中认为构件功能的匹配取决于该功能的输入输出的匹配。用户查询的输入和构件功能的输入的匹配度算法如图4一5所示。 基于语义的构件检索系统研究与实现degreeofMatch(inQUery，i认dV){ifinQuer)阵InAdythenretumexactifinQuery15subelassofi叭dythenretumsubsumPtionifinAdy15subelassofinQuerythenretumPluglnothep刃iseretumfail图4一5基于集合论观点的功能匹配算法算法中的exact表示两者完全相等，具有最高的匹配度。当用户需要处理的输入(inQu叮)是构件功能所能处理的输入(i认dy)的子类时，表示构件的功能包含了用户查询的功能，返回匹配度subsumPtion。此处的匹配度之所以低于exact，是由于构件的功能超出了用户的预期，可能导致用户理解或修改成本的增加。当构件功能所处理的输入是用户需要处理的输入的子类时，表示构件只能提供用户查询的一部分功能，返回匹配度Plughi。然而这个构件仍然是部分有用的，当用户找到另外一些同样是plugln匹配度的构件功能，并把这些部分功能组合起来，就能得到用户预期的功能了。当inQuery和i认dy完全没有关联时，返回最低的匹配度fail。这个匹配度算法利用了概念之间的继承关系，因此它的本质是集合论的思想[32]，如图4一6所示。ExaetMateh:50，sA卜丫义，(sQ(x)<=>s^(x))2.SubsumPtionMateh:s场sA卜丫义，(s^(x)一>sQ(x))3.PluglnMateh:SQ，sA卜Vx，(sQ(x)一>s^(x)4.Fail:50，sA卜，日x，(50(x)八s^(X))图例:SQ娜InQue、包含的实例集合⑧InAdy所包含的实例集合图4一6匹配算法的集合表示这个匹配度算法所处理的情况部分适用于我们所定义的功能语义描述，例如 基于语义的构件检索系统研究与实现我们可以把CSD中的。bject作为功能的输入，采用该算法进行计算。事实上，CSD中的。peration也可以做同样的计算。但我们定义的CSD要比输入输出的情况复杂得多。举例来说，用户查询需要的功能可能是从文件中读入一幅图片，而不管这幅图片是矢量(Vector)图还是点阵(Bitmap)图。构件库中的某个构件提供的功能是从文件或者URL读入一幅点阵图。于是，该构件提供的读入方式包含(subsume)了用户查询，但它所能读入的图片类型只是用户查询的一部分(plugln)，用集合来表示如图4一7。文件URL扫描仪类片型图点阵图产甘吧工工p尽1)7冤月孰阵刀读入位置图4一7集合图示可以看到，用户查询需要的功能是①和④，而构件所提供的功能是①和②，两者之间并没有严格的包含的关系，它们相交于①，这在图4一5的算法中是无法处理的。产生这个情况的原因是，在我们所定义的csD中，叩件ation和object的刻面描述从多个维度划分了概念所对应的实例集合，图4一7正是一种2维的情况，这种多维的划分往往导致了用户查询与构件功能之间的相交关系。4.2.3基于属性距离的功能匹配算法上一小节的算法之所以无法应用于我们的情况，是因为它所定义的类并不包 基于语义的构件检索系统研究与实现含属性(也就是我们本体中的刻面)，因此类之间的关系是单一的。Lee等人在文献【33]中使用的相似度算法正是基于属性距离的。他们的本体定义了机器人在行动过程中会遇到的局面(situation)以及所有的解决策略(strategy)，并且在这些概念上定义了如几何、运动、动力等属性。为了找出哪种解决策略和当前的局面最匹配，他们计算了概念本身之间的语义距离以及每个属性取值之间的语义距离，如图4一8所示。SemDist(ri，rj夕=thesmallestnumberofed罗5betweenriandrjsomDist(伽，p、)=thesmallestnu一nberof“d罗5betw““npballd入ISR-semDist(rj)二wrxSemDist(ri，rj)+乙。，，、.，。)WkXSemDist(p‘，p匆)图4一8语义距离的计算公式上图中的第一个公式计算的是两个本体概念之间的语义距离，第二个公式计算了概念所具有的属性值之间的语义距离(Pk表示第k个属性，Pks和P芍分别表示该属性上的两个取值)，图4一9是该公式的示意图。最后一个公式是前两个公式的加权和。]l]，.ter、团，，，s!，er。‘*，}}。。。，，e。耐以归肠切..肠，肠卯rT愉n刀姗姗玉玉越越脚脚图4一9属性值的语义距离这种方法与我们的情况很相似，但有一处不同。它认为不具有父子关系的概念也是相容的，，比如兄弟关系等，这是人工智能领域所特有的模糊性。但我们的本体不同，当用户需要一个构件能够从文件读入图片时，返回一个能从扫描仪读入图片的构件显然是不符合要求的。我们下面的方法会综合前面介绍的两种方法，使它更符合构件检索的特定需求。 基于语义的构件检索系统研究与实现4.2.4本文使用的功能匹配算法本文综合了前两节的方法，来计算Que乃乞CsD与Fun-CSD之间的语义距离。该算法首先检查两者的oPeration与object是否都具有父子关系，如果成立，则继续下面的算法，否则，直接返回语义距离为无穷大(MAX取T)。对于具有父子关系的概念，可以认为它们的刻面集合是相同的。父概念的一个刻面facet，在子概念中总能找到相同的刻面，或者这个刻面的子刻面(该子刻面的术语取值空间是父刻面faeet的术语取值空间的真子集)。对于子概念中新定义的刻面，父概念虽然不具有这个刻面，但可以认为父概念在这个刻面上取最一般的术语值(术语层次空间的根节点)。另外，对于Que乃乞CSD和Fun‘CSD中没有显式取值的刻面，也认为它们在该刻面上取最一般的值(根节点)。比如用户需要的功能是旋转一幅图片，那么他往往指的是旋转任何格式的图片。而构件功能如果是剪辑音频，那很有可能该构件可以剪辑任何格式的音频。具体的算法如下: 基于语义的构件检索系统研究与实现match(Query-CSD，Fun-CSD){oP--dist二relation(Query-CSD.oPeraiton，Fun-CSD.oPeration)Xsim‘dlst(Quer)匕CSD.oPeratlon，Fun-CSD.oPeration)obj一ist=relation(Query-CSD.object，Fun‘CSD.objeet)Xslm‘dlst(Que乃l-CSD.objeet，Fun‘CSD.objeet)foreveryoPFaeetinFaeet(Quer)乞CSD.FTs(oPeratlon))UFacet(Fun-CSD.FTs(oPeration)){oPFaeet--dist=relation(QueryOPT’enn，FunOPTerm)Xsimesdist(QueryOPT七nn，FunOPTerm)}foreveryobjFaeetinFaeet(Que乃乞CSD.FTs(objeet))UFaeet(Full‘CSD.FTs(objcet)){objFacet-dist“relation(QueryobjT’enn，FunobjTerm)Xsim‘dlst(QueryobjT’enn，FunobjTenn)}，o，al一15，一oP-dist+obj一15，+艺opFacet-dis，+艺objFacet-dis‘retumxAtotaldist//0。(6)进入下一轮构件检索。图5一1优化构件查询的算法在算法的第3步，系统按照用户回答每个刻面取值所提供信息量的大小对这些问题进行排序。对于一个集合C，现通过某种方式将该集合划分成n个子集合，每个子集合的元素个数占c的元素个数的百分比为Pi(i二o，1，…，n-l)，则该划分包含的平均信息量公式如下〔34]:Ent八￥少=艺，一，‘1092，，(8)会话系统提供的每个刻面的取值选项都对检索结果集形成了一个划分，系统通过计算每个划分包含的平均信息量对问题进行排序，使得用户可以从最有用的问题开始阅读回答。举例来说，如果候选的构件功能有100个，并且有两个刻面是用户需求中没有描述的，分别是图片格式和图片类型。候选的构件功能中出现的图片格式有，’BMP”、t’JPEG”和，’TIFF”，而且整个集合被这三个取值划分为30、40、30。对于图片类型，候选的构件功能中出现的取值有“vector”和“Bitrnap”，并且整个集合被这两个取值划分为70和30。在这种情况下，这两个刻面所包含的平均信息量分别为:EntroPy(Image-F0rmat)二一0.3*10920.3一0.4*10920.4一0.3*10歇0.3=1.57 基于语义的构件检索系统研究与实现EntroPy(IInage‘卫中e)=一0.710920.7一0.310920.3=0.88可以看出，用户如果回答构件所处理的图片格式是什么，其包含的信息量要多于回答构件所处理的图片类型是什么。问题包含的信息量越多，说明这个问题的答案对于筛选精确的结果集更有帮助，因此系统会把平均信息量最多的问题放在首位。对问题的排序还需要考虑到问题之间的语义关联【151【35]，举例来说，如果问题B的答案可以从问题A中推理得到，或者问题A比问题B更容易回答，那么问题A就应该排在问题B之前。同时，问题的排列顺序还需要考虑到人们的认知习惯，人们总是希望以一种自然的方式来回答问题。这包括两个方面:①具有某些语义联系的问题应该被分在一组并同时显示。举例来说，如果问题之间具有依赖关系，那么它们就应该被分在同一组里。②在连续两轮的问题之间应该尽量避免语义的切换。举例来说，如果在前一轮中提出了一个上层抽象的问题，那么在下一轮中就应该询问一个更特殊具体的问题，而不是在它们之间插入另外的无关的问题。另外，在上面的讨论中只考虑到用户的查询内容较少，需要增量地优化用户查询的情况，而没有考虑到用户的查询约束过多，导致内部的语义冲突，需要减少查询条件的情况。冲突一般发生在用户查询的一个刻面下，取了两个不同的对应值。这可能是由于用户前后回答问题时的答案不一致，或者用户的答案隐含了与已有约束描述的冲突。举例来说，假设用户在初始的构件查询中指定需要读入矢量类型的图片，而在随后回答“从什么位置读入图片”这个问题的时候，回答了“从扫描仪读入图片”。由于“从扫描仪读入图片”隐含了“读入点阵类型的图片”这样一个事实，因此用户查询在读入的图片类型上发生了不一致。为了解决这个问题，我们把用户回答问题得到的约束描述，以及通过用户的答案进行推理得到的约束描述都定义为未确定的约束，如果构件查询的约束描述发生了冲突，则提出问题请求用户进行最终的确认，并通过该会话过程得到确定的约束描述。 基于语义的构件检索系统研究与实现第六章系统实现与实验数据分析本章介绍2.5小节图2一5所示的构件检索过程的第2步和第4步的实现，并给出了相应的实验结果。下面的6.1节着重描述系统的实现细节和运行结果，6.2节则给出了实验方法与数据分析。6.1系统实现本体在整个构件检索过程中起到知识库的作用，本文使用斯坦福大学开发的Prot电‘工具[36][37]构建2.3小节图2一展示的多媒体处理领域的本体模型，结果如图6一1所示。甲甲吧.卿卿州钾黯缺兴一一，.以和d，.州.d巨.内月助.俪，.功d.o!.众姗目匕1甲.介优“..〔山.R.“.R.由e.Rd山，.T丽V.^该.J口布日.州p3.价腆v，.如，J.t目n二尸.杏桩O.丫「「，.如，J””.日如即.丫目口口，.LOC目翻.限.5‘.门，盯.饰比甲.功比”于“m目.八明.目庵O，.，“耐闻少.币.....圈几s圈FF诬一二浦浦..痛痛图6一1Prot妙构建的多媒体处理领域本体 基于语义的构件检索系统研究与实现接着使用Prot‘96把构建的本体模型存储为owl文件，并在系统实现中使用Jena解11381进行操作，以推理得到程序中所需的语义知识。此外，系统还使用构件库来存储被规范描述了的构件集合。该构件库中属于多媒体处理领域的构件有12个，用xml文件表示如下:(eomPonents)(eomdese)rotateimageseomponents(/eomdese)(fUnetion)(onname)Rotate(/oPname)(objname)Image(/objname)(objterms)HaseeF0rmat，TIFF(/objterms)(/funetion)(/funetions)(z‘eomPonent)(e伽Ponentid二，，4，，name=，，ReadMediaFromFile，，)(eomdese)readmediafromfileeomponents(/eomdese)Has一Loeation，File(/opterms)(objterms)Has_Format，TIFF(/objterms)(/funetion)(funetion>(onname)ReadHas_Format，做V，MP3(/objterms>(/funetion)(eomPonentid二，，5，，name=，，EditAVI，，)(eomdese)EditAVIeomponents(/eomdese)(funeti即s)(ftinetioll)(oPn胡e)Edit丈/opname)(objname)Video(/funetion>(/funetions)(/eomPonent)(eomPonentid=，，6，，name=，，EditAudio，，)(eomdese)EditAudioeomponents(/eomdese)(funetions)(fllnetion)Audio(/objname)(opterms)(/onterms)(/eomPonent)(eomPonentid=，，7，，name=，，RotateVeetor，，)49 基于语义的构件检索系统研究与实现(e川dese)RotateVeetoreomPonents(/e绷dese)(funetions)(funetion)(oPname)RotateHas_Type，VeetorReadVideoeomponents(/eomdese>(fUnetionS>(funetion>(opname)Read(/opname)(objname)Video(/objname)(oPterms)(/opterms)(objterms)(/objterms)(/funetion)(/funetions)(/eomPonent)(eomPonentid=，，10，，name=，，ReadVideoFromURL，，)(funetions>(funetion>(opname>Read(opterms)Has_Loeation，URL(/onterms)(funetions)(funetion)(opname)Read(/oPname)(objname)Image(/objname)(oPterms)Has_Loeation，URL(/oPterms>(/funetions)(/eomponent)(eomPonentid=，，12，，name二，，RotateVideo，，)(eomdese)RotateVideoeomPonents(/eomdese)(funetions)(funetion)(opname)Rotate令))PP拍CeSSSRotateeResizeeReaddEdittImIagee0.550.550.550.633////oobjeettMediaa00/////////////，//VVidcoo00曰//沪沪////0.13300AAudioo00///洲///0.13300由于的相似度超过了其他所有二元组maxDIFF=0.1以上，因此被作为最佳映射。同时，映射Load今Read被加入到概念词典中，辅助以后的相似度计算。由于状语词汇scaner出现在Twouls(Read)中，FTs(Read)中加入约束描述;定语词汇TIFF出现在孙ords(Image)中，FTs(Image)中加入约束描述。因此，创建构件查询步骤生成的构件语义描述为:Que马乞CSD=}，加age，{}>。构件库中与该Que乃仁CsD匹配的结果如图6一3所示。可以看到，由于构件库中的构件”ReadlinageFromscaner’，比用户查询多出了图片类型的约束，因此相似度=0.8八3=0.51。 基于语义的构件检索系统研究与实现翻翻、tt，:z几。e。。:t:8080zco.p.ota.tr、。。，.、，‘。.teh.‘，。。毅毅’‘’矍矍领领域:班ulti二桩aProeessi飞飞您您输入的自然语言动宾短语:LoadaTI邓i二g。framsc二err生生成的构件查询::ddOOPeration:n:ReadSe即InerrHHa日--Loeation:eeSe即Ineroobjeet:Image即即HHasjarm掀:TI即脚.娜曰峨目归口口口口.曰印.国::目娜脚.哪曰麟攫娜.匹匹配的构件集合:字Readl喊eFro溺e~er相似度:0.511构构件工D:3构11件“字:Read工喊eFr。‘C一””:。·51{匹匹配的功能集合::dd，功功能相似度:0.51ann巴rroop盯ation:ReeadHHa$一oeation:SFeFann巴roobjeet:I帕geitmaPP班班韶Jor肪tll:TIFFHHasee乃，e:Bitmapp瓤暴巍篡羲蒙;…{;豪薰图6一3“LoadaTIFFimagefromsc~”的检索结果实例2:用户输入构件查询“Rescaleavectorimage’。54 基于语义的构件检索系统研究与实现嘿叭凰熏熏庶棘棘蘸画蘸逼愈奥…竺立鹭礴簿赡黝戮耀臀礁瀚鹭黝鬃鹭黝缨请选择构件领域，并输入动宾短语来表示需要的功能动宾短语:由动词和名词、以及修饰它们的定语或状语组成，例如“resizethei功age”就者“readajpegioagefro二file”领域:O班ultimediaProeessing动宾短语:RRe:ealeaveetori二ag目全逐匡」翻姜蕉:烈*孩杰袅焦痪点然然图6一4用户输入构件查询“Resealeavectorimage”该动宾短语经过MINIpAR分析后得到P=Rescale，O二Irnage，ADVs=叭尤门，S={、乞ctor}。概念映射的相似度计算结果见表6一2。表6一2实例2概念映射的相似度SSIM(P令OPeration))oPerationnPPfOCeSSSRotateeResiZeeReaddEdittPP=ReSCaleeSSIMeLeLN0/A0AN0/A0AN0/A0AN0/A0AN0/A0ASSIMM0000000000SSIM(O今object)objecttMMediaaIinagee巧deooAudiooOO=ImageeSSIMeLeL00ll0000SSIMM00ll000 基于语义的构件检索系统研究与实现SSIM(令))PP拍CeSSSRotateeResiZeeReadEdittIImagee0.550.550.550.55////oobjeettMediaa00///////尸/////，，VVideoo00/////，0000AAudioo00沪//////0000四个二元组，，，的相似度都超过了闭值而nSIM=0.5，但没有一个超过其他maxD正F=0.1以上。因此系统启用会话过程，将四个二元组呈现给用户，由用户选择最佳映射，如图6一5。因此，创建构件查询步骤生成的构件语义描述Que乃仁Csn=}>。构件库中与该QUe职--CSD匹配的结果如图6一6所示。可以看到，构件Resize、乞ctor完全符合用户的要求。翻翻，缪缪请请选择最匹配的动词和宾语::动动词:Rotate名词:工二铭ee黯动黯动词词:RReoatdate名毓词名:词I:二a工g二e、ee彝;彝黔黔哄黔嗯飘黔户户亡亡庶绮郭琪蒸薰蹂息扁扁翩翩赢篡蘸蘸…巍热瞧巍燕瘾蘸蕊鑫磊磊图6一5会话过程:用户选择最佳映射 基于语义的构件检索系统研究与实现ii-------一含……翌;::翼竺箕:i:，一……‘，‘、“”日“佰西‘”‘佰’“e’C“e‘vec‘。r‘’“ee生生成的构件查询::OOPeration:Resizeeoobjeet:I肪gee血血sJ冲e:Veetorr翩翩蜘印娜国娜娜妇嘛栩嘟翰幽澎娜彰匹匹配的构件集合::构构件ID:8构件名字:ResizeVeetor相似度:1.00匹匹配的功能集合::功功能相似度:1.。OOPeration:Resizeeoobjeet:ImageeHHas一抑e:Vectorr「「粤禅询JJ图6一6“Rescaieaveetorim铭e”的检索结果6.2实验分析本节对上文所述的构件检索系统的查准率和查全率进行了实验，并把实验数据与传统的构件检索方法进行比较，来验证本文所提出方法的效果。本节的最后 基于语义的构件检索系统研究与实现分析了构件检索系统在大规模构件库中的检索效率，以验证本系统的可行性。首先给出用户的查询，以及构件库中预期符合用户查询的构件集合，如表6一3。其中的构件ID正是6.1小节代码6一1的xml文件中给出的构件ID。表6一3用户查询以及预期的检索结果用用户查询符合条件的构件ID集合合①①DownloadastreamingvideofromwebURLL9，100②②OPenavidcofromfilee4，99..③Rescaleavectorimagee2，88④④Rotateabitm叩formatimageell⑤⑤ReadaTIFFformatpieturee3，44⑥⑥Rotateavectorpieturee77⑦⑦EditanAVIvideoo55使用本文的构件检索系统来运行这些用户查询，得到每个构件的相似度如下表所示。其中第一行代表7个用户查询，第一列代表12个构件。每一格表示该用户查询与构件的相似度，空白表示相似度为0。表6一4用户查询与构件的相似度①①②③④⑤⑥⑦ll1.00220.名名330.511440.5110.511551.0066771.00881.00990.6440.88ll000.5111110.44ll22为了计算本构件检索系统的查准率和查全率，需要设定一个闭值，来筛选出符合条件的构件。下面给出以闭值为横坐标，查准率/查全率为纵坐标的折线图。 基于语义的构件检索系统研究与实现闭值一查准率1.011--------------一_/__----------一0.99//0.98一一__一Z--------------一哥绝钡0.97//—查准率0.96-----------一/----------一___一0.950.940.93111!.11}II0.920.10.20.30.40.50.60.70.80.9闭值图6一7闭值一查准率折线图闭值一查全率1.2l0.8并训0.6钡—查全率0.40.200.10.20.30.40.50.60.70.80.9闽值图6一8闭值一查全率折线图59 基于语义的构件检索系统研究与实现通过上面两张图可以看出，检索系统取相似度的阂值为0.5的时候，查准率和查全率的综合数值最优。下面我们比较本文的构件检索系统与传统的构件检索方法的优劣。由于传统的构件检索方法并没有概念映射这个步骤，因此无法从用户输入中切分出类似于谓语、宾语、状语、定语等概念，也就无法捕获各个词汇之间的关系，只能单独处理每一个单词。本文在传统的构件检索方法中，把用户查询作为一系列关键字，去除其中平凡的关键字(例如冠词、介词等)，然后运用4.2.3小节的相似度计算方法计算每个关键字与各个构件的相似度(构件的功能描述也作为一系列关键字展开)，并把相似度的平均值作为该用户查询与构件的整体相似度。由于传统的构件检索方法缺少用户会话的过程，因此无法理解陌生的词汇，本文只是简单的把这些陌生词汇的相似度设置为O。表6一5是用户查询与每个构件的传统相似度。表6一5用户查询与构件的传统相似度①①②③④⑤⑥⑦ll0.3330.7550.333220.3330.255330.3330.550.755440.220.6770.3330.2550.7550.677550.220.3330.2550.2551.00660.2550.2550.333770.6770.550.677880.6770.2550.333990.220.3330.2550.333ll000.550.3330.2550.550.333lll0.220.3330.2550.25511220.220.3330.550.2550.3330.677可以看到，传统方法的缺点在于用户查询与每个构件都具有一定的相似度，显得辨别力不够。其中表现得最为明显的是，构件12(Rotate巧dco)原本是我们植入的一个错误定义的构件，在传统方法中竟也与用户查询具有一定的相似度。这使得传统方法在低阐值的情况下查准率较低。而传统方法对于真正匹配的构件，其相似度又不足够高，导致高闭值的情况下查全率较低。同样地，下面给出以阐值为横坐标，查准率/查全率为纵坐标的折线图。 基于语义的构件检索系统研究与实现闭闭值一查准率率11~~~~/-/~，~-~~~一1一一三二三二二二二二二石一户产一.厂-一一00.8卜-----------------------j------------一」一并并//苯派妥}茫茫00.6卜-----------一。----------------------一谁}丁二二一二法、，_，}钡钡.4卜1-----一了-/-/-----------------------一1}}—一“’l传的.y邵统查准方刀率法州州，，闭值__。//00.2卜--------------------------------{的查准率11111111!!OOL一一---‘一-一--‘~一一一00.110.220.330.440.550.660.770.80.99图6一9阐值一查准率折线图阐值一查全率1.2、、、--\·、\0.8‘‘“一‘~~训铃钡—本文方法的查全率0.6\一，·传统方法、、的查全率0.4、、0.2、、}}{I}111110.10.20.30.40.50.60.70.80.9闽值图6一10闭值一查全率折线图 基于语义的构件检索系统研究与实现可见传统方法无论在查准率还是查全率上均不如本文提出的方法。在本节的最后，我们将对构件检索系统的性能进行数据分析，以证实本系统的实际可行性。我们分别在构件库中存放入12个构件(6.1小节代码6一1的xml文件中给出的构件)、100个构件、500个构件、1000个构件、5000个构件、10000个构件，得到一次构件检索的时间如下:表6一6检索时间表构构件个数l22100050001000050000100000检检索时间(s))5.996.116.666.777.227.77一一一一一一一一一一一一一厂厂一一一一——检索时间间111.111图6一n构件个数一检索时间图可以看到，随着构件库中构件数量的急速增长(从100个到10000个，增加了100倍)，检索时间的增长却非常缓慢(从6.1秒到7.7秒，增加了0.26倍)。这是由于本文在相似度计算前，预先判断构件功能的QPeration与。句ect是否和用户查询具有上下位关系。对于不满足要求的构件，直接在构件库select的过程中过滤掉了。因此我们不用对构件库中的每个构件都执行相似度计算算法，而只要对其中的一小部分执行就够了，这保证了系统的检索时间几乎是一个常量。对于传统的检索方法来说，由于无法执行预筛选步骤，因此每个构件都要被取出构件库进行匹配，使得检索时间会随着构件库规模的增加而急速增长。 基于语义的构件检索系统研究与实现总结与展望基于语义的构件检索过程中存在的一个突出问题是用户对问题域的理解以及所熟悉的自然语言表达方式与构件的规范语义描述之间存在差异，从而导致用户很难准确刻画自己的检索请求。本文通过概念映射以及基于语义的交互式会话过程辅助用户生成符合用户复用需求以及构件库构件描述框架的构件查询方案，从而大大提高了构件库中构件的复用机会。本文提供的方法假定构件库中的构件在被用户查询之前，已经根据领域模型被精确描述了。虽然构件的开发者总是非常熟悉构件所处的领域，但对领域本体模型未必非常熟悉，所以难免无法精确地描述发布构件。本文的方法同样可以帮助构件开发者快速精确地描述构件:构件开发者首先使用自然语言输入的方式，找到自己构件所拥有的功能在领域本体中的位置，随后只需要了解局部的领域本体，补充未描述的约束信息即可。本文方法的限制是对知识工程的依赖，假定领域本体已经被完善定义，但这需要很大的工作量。然而，如今知识获取和建模领域的发展，例如本体工程，已经提供了系统的方法，使得这个限制得到了很大的缓解〔39]。我们已经根据自由代码网站CedeProjeet[301上多媒体领域的构件信息对本文的方法进行了实验(第六章)，结果表明本文的方法对于降低用户的检索难度以及提高查准率和查全率有着明显的作用。我们接下去的工作是在系统中加入4.1小节的扩展构件查询过程和第五章的优化构件查询过程，以得到更好的检索效果。在完成了基于语义的构件检索系统的实现之后，我们将对基于语义的构件描述进行研究，以实现构件提供者在描述和提交构件时的入库自动化。 基于语义的构件检索系统研究与实现参考文献[l]M.Griss.Softwarereuseathewlett一Paekard.In:Proeeedingsofthe1stIntemationalWbrkshoPonSoflwareReusability，Dortmund，Gennany，1991.[2]EBachtnan，L.Bass，C.Bu知man，etal.TechniealCone即tsofComPonent一BasedSoftwareEngineering.[CMU/SEI一2000一TR一008][Z]，2000.[3」YaoHaining，L.Etzkom.Towardsasernantie一basedapProachforsoftwarereusableeomPonentclassifieationandretrieval.In:Proeofthe42nd人阴ualsoutheastRegionalConferenee.NewYOrk:ACMPress，2004.11卜115.〔41王渊峰，张涌，任洪敏，等.基于刻面描述的构件检索.软件学报，2002，13(8):1546-1551.(硒陌ngYuanfeng，ZhangYong，RenHongllin，etal.RetrievingComPonentsBasedonFaeetedClassifieation.JournalofSoftware(inChinese)，2002，13(8):1546一1551.)【5]贾晓辉，陈德华，严梅，等.基于刻面描述的构件查询匹配模型及算法研究.计算机研究与发展，2004，41(10):1634-1635.(Jia兀aonui，ehenoehua，、乞nmei，ctal.ResearehonMatchingModelandAlgorit知rnforFaeeted一BasedSoftwareComPonentQuery;JoumalofComPuterResearchandDeveloPment(inChinese)，2004，41(10):1634一1638.)[6]EMcGarey，etal.ACaseStudyonReeonunendingReusableSoftwareComPonentsusingCollaborativeFiltering.In:ProeeedingsoftheMSRworkshoP，2004.【7]V.Su到Llnaran，VC.Storey.ASemantie一BasedAPProachtoComPonentRetrieval.TheDArABASEforAdvaneesinInformationSystems，2003，34(3):8一24.[8]H.Mili，P.、乞ltchev，A.Di一Seinllo，P.Gabrini.AntomatingthehidexingandRetrievalorReus汕lesoftwareeo哪onents.Porce记ingsorthe6th玩temation日从勺正shoPNLDB，2001:75一86.[9]A.EZazo，C.GFiguerela.J.L.ABerrocal，E.Rodriguez.Refonnulationofqueriesusingsimilaritythesauri.hiformationProeessionandManagement，2005，41(5):1163一1173.【10]彭鑫，赵文耘，肖君.基于本体的构件描述和检索.南京大学学报:自然科学版，2005，41(10):47小476.(pengXin，Zhao认/enyun，兀aoJun.R即resentingandRetrievingComPonentsBasedonOntology.JoumalofNanjingUniversity:Nan叮alscience(inChinese)，2005，41(10):470-476.)[川J·T.L.叭厄ng，B.A.Shapiro，D.Shasha，etal.Analgorithmforfindingthelargest 基于语义的构件检索系统研究与实现aPProximatelyeolnrnonsubstructuresoftwotrees.IEEETransactionsofPatemAnalysisandMachinehitelligenee，1998，20(8):889一895.[12]T.Schlieder.ApproXQL:designandimPlementationofanaPProximatePattemmatchinglanguageforXML.TeehniealRePort，Bol一01，FreieUniversitatBerlin，2001.【13]钱乐秋，朱三元，张涌，薛云皎，王渊峰.刻面分类构件的匹配模型.软件学报，2003，14(3):401一408.(QianLeqiu，ZhuSan界an，zhangYong，XueYunjiao，研值ngYuanfeng.AMatchingModelforSoflwareComPonentClassifiedinFaeetedSchelne·JoUmalofSoftware(inChinese)，2003，14(3):401~408.)[l4]杨芙清，梅宏，常继传，李克勤，郭立峰.青鸟系统中可复用软件构件的表示与查询.电子学报，2000，28(8):20一23.(物ngFuqing，MeiHong，ChangJiehuan，LiKeqin，GuoLifeng.RePresentingandRetrievingReusableSoftwareComPonentsinJB(Jadebired)System.ACI’AELECTRONICASINICA，2000，28(8):20一23.)[15]GuMingyang，KBo.ComPoneniRetrievalUsing枷owledge一IniensiveConversationalCBR.Proeeedingsofthe19thIniemationalConfereneeonIndustrial，EngineeringandOtherAPPlicationsofAPPliedIntelligentSystems(IE户以AIEZOO6)，Annecy，Franee，2006.【16]EMcGarey，etal.ACaseStodyonReeonunendingReusableSoftwareComPonentsusingCollaborativeFiltering.In:ProeeedingsoftheMSRworkshoP，2004.[17]T.R.Gruber.Ontolingua:ATranslationAPProachtoPotableOntologySpecification·众owledgeAequisition，1993，5(2):199一200.[18]W.N.Borst.ConstriJctionofEngineeringOntologiesforKnowledgeSharingandReuse.PhDThesis，Universityofl’Wente，Enschede，1997.[19]B.Chandrasekaran，J.JosePhson，andVBenjamins.WhatareontologiesandWhydoweneedthem?IEEEInielligentS”tems，14(l):20一26，1999.[20]D.L.MeGuinness，EvanHannelen.OWLW七bontologyLanguageOverview.httP:刀www.w3.or留1，R/2004瓜EC一wl一feal泊res一20040210/[21]M.K.Smith，C.W七lty，D.L.MeGuinness.OWL研/ebOntologyLanguageGuide.ht切:刀~.w3.org/TR/2004/REC一owl一guide一20040210/[22]F.Manola，E.Mill俄B.McBride.RDFPrimer.httP:刀叭乃刀w.w3.org/TR/2004/REC一rdf-Primer-20040210/[23]5.C.Bailin.SoftwareReuseasOntologyNegotiation.In:ProeeedingsofthesthIntemationalConfereneeonSoftwareReuse(ICSR2004)，2004:242一253. 基于语义的构件检索系统研究与实现[24]U.Reimer.TutorialonorganizationalMemoriesforCaPturing，SharingandUtilizingK五owledge.hitetnationalConferenceonEnterprisehiformationSystemS(ICEIS2001)，Setubal，PortUgal，2001.[25]5.Bechhofer，etal.Owl研/ebOntologyLanguageReferenee.httP:刀www.w3.org/TR/owl一re厂，2004一02一10.[26]彭鑫，赵文耘，钱乐秋.基于领域特征本体的构件语义描述和组装.电子学报，已录用(penXin，Zhao研/enyun，QianLeqiu.SemantieRepresentationandComPositionofBusinessComPonentsbasedonDomainFeatureOniology.AC口r入ELECTRONICAS创ICA(inChinese)，APProved.)[27]VErmolayev，N.Keberle，W.E.Mat欢e，V.Vladimirov.AStrategyforAutomatedMeaningNegotiationinDistributedInformationRetrieval.Proe4thIntSemantieM/ebConferenee(ISWC’05)，Galway，Ireland，2005.【28]李振东，费翔林.基于概念的信息检索模型研究.南京大学学报:自然科学版，2002，38(l):99一109.(LiZhendong，FeiXianglin.ResearchontheCone即t一basedInformationRetrievalModel.JoumalofNanjingUniversity:NatUralSeienee(inChinese)，2002，38(l):99一109.)[29]D.Lin.DePendeney-basedEvaluationofMINIPAR.ProeeedingsoftheW6rkshoPontheEvaluationofParsingSysterns，Granada，SPain，1998.[301httP:刀认氏叨胃.eodeProject.eoln/[31]M.Paolueei，T.Kaw田的ura，T.Payne，阴dK.Sycara:Sern即tiematchingofwebservieeseapabilities.ProeeedingsoftheFirsthitemationalSemantie认/ebConferenee，SPringer-Veriag，2002:333一347.[32]M.Stollberg，U.Keller，D.Fensel.P别rtnerandServieeDiseoveryforCollaborationEstablishmentwithSemantie叭/ebServiees.In:ProeeedingsoftheIEEEhitemationalConfereneeonw七bServiees(ICWS’05)，orlando，July2005.[33]HwayounLee，Ho一inChoi，hi一YoungKo.ASemantically-BasedSoftwareComPonentSelectionMech丽smforIntelligentServiceRobots.in:4thMexieanIntemationalConfereneeonArtifieialIntelligenee，2005.[34]J.R.Quanlan.hiduetionofdeeisiontrees.MaehineLearnlng，1986，l(l):81一106.[35]GuMingyang，A.Aamodt.Aknowledge一int切sivemethodforeonversationalCBR.In:ProeeedingsoftheFourthMexieanhitemationalConfereneeonArtificialInielligenee，2005.〔36]httP://Protege.stanford.ed侧 基于语义的构件检索系统研究与实现[37]M.Ho币dge，H.K五ublauch，A.Rector，R.Stevens，C.研厅。e.APractiealGuideToBuildingOWLOfltologiesUsingTheProt亡96一OWLPluginandCO一ODEToolsEdition1.0.httP:刀www.co一ode.o习resourees/tutorial好rotege0WLTutorial.Pdf，2004一08一27.[38]httP://jena.soureefo嗯e·ne灯[39]A.Aamodt.ModelingtheknowledgeeontentsofCBRsystems.proeeedingsofWbrkshoPProgramattheFourthIniemationalConfereneeonCase一BasedReasoning，、乞neouver，2001. 基于语义的构件检索系统研究与实现致谢感谢钱乐秋导师在论文的完成过程中对我的教导和帮助。钱老师对论文主题的确定进行了方向性上的指导，并对我的多次报告都提出了中肯的意见。在论文的撰写过程中，钱老师认真仔细地审阅了论文的每一个版本，并从语句表述到内容条理都给出了细致入微的修改和指正。正是由于钱老师严谨的治学态度，才使得我如此顺利地完成整篇论文。感谢彭鑫讲师对论文创新点的指导，使得我能够在科研过程中顺利找到突破口。同时也感谢彭鑫讲师在每一次讨论班中，对于我提出的问题和困惑的不厌其烦的讲解。感谢和我同在一个科研小组的杨涛博士和陈叶旺博士。正是由于你们的帮助，我才能如此迅速地实现论文的原型系统。同时也感谢你们在实验过程中给出的意见和付出的努力。