（计算机应用技术专业论文）基于树匹配和遗传算法的构件检索算法研究.pdf

摘要 论文题目：基于树匹配和遗传算法的构件检索算法研究 学科专业：计算机应用技术 研究生：丁新村 指导教师：姚全珠教授 摘要 签名： 签名： 基于构件的软件开发( c o m p o n e n tb a s e do ns o f t w a r ed e v e l o p m e n t ，c b s d ) 是软件复 用的最有效的途径，在基于可复用构件的软件开发过程中，构件库管理系统扮演了重要角 色。在构件库管理系统中，构件的分类模式及其检索机制是最基本的核心功能之一。而有 效的检索机制能大大降低复用成本，因此，如何对构件库中大量的可复用构件进行有效地 检索就成为基于构件的软件开发方法要研究的热点问题。 本文通过对构件分类模式和检索技术的背景、研究现状及相关理论的探讨，指出了基 于刻面分类模式的构件检索方法目前所存在的缺陷。针对刻面分类模式的特点，通过借鉴 树匹配模型，本文提出了一种新的基于x m l 的树匹配构件检索算法。这种算法能够兼顾构 件检索的查全率和查准率，并且具有较高的检索效率。同时，由于传统的基于刻面的构件 检索算法的局限性，鉴于人工智能中遗传算法的思想，本文提出了一种基于遗传算法的刻 面权重自学习构件检索模型，采用基于刻面权重自学习的遗传算法来动态地改变刻面权重 以提高查准率；采用基于构件采样的风险最小化算法来解决训练数据不充分问题。 最后，本文在n e t 环境下，实现了基于本文提出的检索方法的构件检索系统原型， 介绍了其中的核心功能模块的实现，并通过试验验证了该方法的可行性和有效性。 关键词：构件检索；树匹配模型；遗传算法 a b st r a c t t i t l e ：t h er e s e a r c ho fc o m p o n e n tr e t r i e v a la l g o r i t h m b a s e do nt r e e m a t c h i n ga n dg e n e t i ca l g o r i t h m m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：x i n c m rd i n g s u p e r v i s o r ：p r o f q u a n z h uy a o a b s t r a c t s i g n a t u r e ： s i g n a t u r e ： c o m p o n e n tb a s e do ns o f t w a r ed e v e l o p m e n t ( c b s d ) i st h em o s te f f e c t i v em e t h o df o r s o f t w a r er e u s e t h ec o m p o n e n tr e p o s i t o r ys y s t e mp l a y sa l li m p o r t a n tr o l ei nt h ep r o c e s so f r e u s a b l e c o m p o n e n tb a s e d o ns o f t w a r e d e v e l o p m e n t i n t h i s s y s t e m ，c o m p o n e n t c l a s s i f i c a t i o ns c h e m ea n dr e t r i e v a lm e c h a n i s mi so n eo ft h eb a s i ca n dk e r n e lf u n c t i o n s a n e f f e c t i v em e c h a n i s mo fc o m p o n e n tr e t r i e v a lc a nr e d u c et h ec o s to fs o f t w a r er e u s ee v i d e n t l y t h e r e f o r e ，h o wt or e t r i e v eam a s so fc o m p o n e n t se f f e c t i v e l yi nc b s db e c o m e sa ni m p o r t a n t p r o b l e m t h eb a c k g r o u n d ，c u r r e n tr e s e a r c hs t a t u sa n dt h e o r i e so fc o m p o n e n tc l a s s i f i c a t i o ns c h e m e a n dr e t r i e v a lt e c h n o l o g yi sd i s c u s s e di nt h i st h e s i s ，t h e nt h ed e f i c i e n c i e so fc o m p o n e n tr e t r i e v a l m e t h o db a s e df a c e tc l a s s i f i c a t i o ns c h e m aa r ep o i n t e do u ta tp r e s e n t i np o i n to ft h ef e a t u r e so f f a c e t e dc l a s s i f i c a t i o na n dw i t ht h er e f e r e n c eo ft h et r e em a t c h i n gm o d e l ，an e wm e t h o do f c o m p o n e n tr e t r i e v a lb a s e do nx m l a n dt r e em a t c h i n gm o d e li sp r o p o s e d t h i sm e t h o dc a n g i v ed u a la t t e n t i o nt ot h er e c a l la n dp r e c i s i o no fc o m p o n e n tr e t r i e v a la n dh a sh i g h e rr e t r i e v a l e f f i c i e n c y a tt h es a m et i m e ，b e c a u s eo fs o m es e v e r el i m i t a t i o n so ft r a d i t i o n a lc o m p o n e n t r e t r i e v a la l g o r i t h m sb a s e do nf a c e t ，o nt h eb a s i so fg e n e r i ca l g o r i t h mo fa r t i f i c i a li n t e l l i g e n c e ， a n i m p r o v e di n t e l l i g e n tc o m p o n e n t r e t r i e v a lm o d e lb a s e do ng e n e t i ca l g o r i t h mw i t h f a c e t - w e i g h ts e l f - l e a r n i n gi sp r o p o s e di n t h i sp a p e r g e n e t i ca l g o r i t h mb a s e df a c e tw e i g h t s e l f - l e a r n i n ga l g o r i t h mc a nc h a n g et h ef a c e tw e i g h td y n a m i c a l l yi no r d e rt oi m p r o v er e t r i e v a l a c c u r a c y , a n dr i s km i n i m i z a t i o n - b a s e dc o m p o n e n ts a m p l i n ga l g o r i t h mi su s e dt os o l v et h e i n s u f f i c i e n c yo ft r a i n i n gd a t a f i n a l l y , i nd o tn e te n v i r o n m e n t ，t h ep r o t o t y p eo fac o m p o n e n tr e t r i e v a ls y s t e mi sr e a l i z e d ， a n dk e r n e lf u n c t i o nm o d u l e sa r ei n t r o d u c e d t h ee f f i c i e n c ya n df e a s i b i l i t yi sp r o v e di nt h e e x p e r i m e n t k e y w o r d s ：c o m p o n e n tr e t r i e v a l ；t r e em a t c h i n gm o d e l ；g e n e t i ca l g o r i t h m 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我 个人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢 的地方外，论文中不包含其他人的研究成果。与我同工作的同志对本文所研究的工 作和成果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名： 学位论文使用授权声明 新年矽弓月巾 本人二葺剿在导师的指导下创作完成毕业论文。本人已通过论文的答辩， 并已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意 授权西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定 提交印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生 上交的学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为 教学和科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、 资料室等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 论文作者签名： 导师签名：锥喀圻年西月谚日 绪论 1 绪论 1 1 选题背景及意义 1 1 1 背景 软件复用n 2 1 是在软件开发中避免重复劳动的一种解决方案，其根本出发点是系统 的设计与开发不再采用一切“从零开始”的模式，而是以己有的工作为基础，充分利用过 去应用系统开发中积累的知识和经验，如需求分析结果、设计方案、源代码、测试计划及 测试用例等，从而将开发的重点集中于应用的特有构成成分。通过软件复用，在应用系统 开发中可以充分地利用已有的开发成果，消除了包括分析、设计、编码、测试等在内的许 多重复劳动，从而提高了软件开发的效率，同时，通过复用高质量的已有开发成果，避免 了重新开发可能引入的缺陷和错误，从而提高了软件的质量。 探究软件复用的发展历史，可以追溯到6 0 年代出现的软件危机。1 9 6 8 年n a t o 会议 首次提出可复用构件b 1 的概念。随着计算机应用领域的迅速扩大，软件规模及复杂度的 不断提高，提高软件生产率成为软件产业的当务之急。要解决这个问题，软件复用无疑是 一个非常有效且可行的办法。8 0 年代中期，软件复用已经在子程序库、报告生成器、编 译器等多方面取得进展。9 0 年代到现在，有关软件复用的概念不断完善，软件复用的技 术和方法也日益成熟。有些专业领域的可复用系统较为成功，通用领域的复用技术也有所 发展。 软件复用技术分为生成技术和组装技术两大类。生成技术是由程序生成器来达到复用 的目的，它是一种对软件模式的复用。然而，组装技术是利用组装方式来复用软件构件， 对已有构件不做或做较少的修改，将构件插装到一起，形成新的系统。因此，基于构件的 软件开发则是软件复用中，对组装技术的一个实践过程。 软件复用能有效地解决软件危机，提高软件开发的效率和质量，降低开发和维护成本。 从软件工程的角度看，软件的开发方法也经历了巨大的变化，从结构化的软件开发方法到 面向对象的软件开发方法，再到基于构件的软件开发方法。近年来，学术界兴起了基于构 件的软件开发方法研究热潮，软件产业界也探索基于构件的软件开发方法，并将其付诸实 践，即：采用类似工业化的生产方式，将适当的构件按照给定的架构，按照特定的相互关 系组装在一起，形成一个新的软件系统，从而避免一切从零开始的低效率开发方式，也就 是基于构件的软件开发方法1 ( c o m p o n e n t b a s e ds o f t w a r ed e v e l o p m e n t ，c b s d ) ，该方法 以软件架构为组装蓝图，以可复用的软件构件为组装模块，支持组装式软件的复用，大大 提高软件生产效率和软件质量，在逐渐被越来越多的开发组织所采用。 然而，与c b s d 相关的核心问题( 构件模型、构件获取、构件表示、构件检索及构 件的集成组装等等) 之一就是构件检索，它关系到如何去定位和识别最能满足用户需求构 件的过程。基于构件的软件开发方式是软件复用技术的一种实践活动。大致可将其分为构 件的生产，构件的存储、组织和检索，基于构件的系统组装三个主要过程。构件库在c b s d 中起到了重要的作用。围绕构件库，可以将软件开发活动划分为构件的生产、构件的管理 和构件的复用等三部分。相应地，每部分的软件开发人员就为构件生产者、构件管理者和 构件复用者。他们的开发实践与构件库都有着较为密切的联系，如图1 - 1 所示。 图1 - 1 基于构件的软件开发的关系图 f i g 1 1r e l a t i o no fs o f t w a r ed e v e l o p m e n tb a s e do nc o m p o n e n t 下面将基于构件的软件开发的关系图( 见图1 - 1 ) 中的构件生产者、构件管理者及构 件复用者的在基于构件的软件开发过程的各自所承担的角色和作用给予介绍： 1 ) 构件生产者 即构件的提供者，主要负责构件的生产、适应性修改和构件描述。构件生产：构件生 产一般通过三条途径来实现。第一，利用领域工程、逆向工程以及软件再工程等技术，从 应用领域的现有系统中抽取构件和构架；第二，对已经入库的可复用构件和构架进行再工 程，以进一步提高它们的可复用性；第三，根据应用的需求，直接开发所需构件。构件适 应性修改：根据构件使用者的反馈，对构件进行适应性修改，并将修改后的结果作为该构 件的一个新版本放入构件库中。构件描述：将生产出的构件以一种规范化、易于理解的方 式来全面、准确地描述，使得构件复用者能够准确地理解构件的功能以及其他非功能性指 标( 如性能、可靠性等) ，并由此来判断该构件是否完全符合他的要求；同时构件描述信息 应为构件组装提供支持。描述信息还是构件库管理构件的主要依据。只有经过规范化描述 的构件才可以存入构件库中保存。 2 ) 构件管理者 即构件库管理系统的管理员，负责对构件进行分类、存储和维护。构件分类：构件管 2 绪论 理者要根据构件生产者提供的构件描述信息，采用几种分类方式( 例如刻面、关键词等) 对 构件进行分类，以便构件复用者能够快速准确地找到所需的构件。构件管理者还要对构件 库进行日常管理和维护，包括修改、删除构件及其描述信息，以及增加、修改、删除构件 管理人员、构件复用者、构件提交者的使用权限、收集整理用户反馈信息等工作，以保证 构件库管理系统的正常且高效的运行。 3 ) 构件复用者 即构件库的用户，构件库是为构件复用者的组装工作提供服务的。构件复用者所做的 工作主要有构件检索、构件理解和适应性修改和构件组装。构件检索：根据构件库中的分 类信息，在构件库中查找符合特定条件的构件，然后再对找到的构件进行评估，找出最符 合要求的构件。构件理解和适应性修改：利用构件生产者的描述提供的信息来理解构件的 功能以及其他非功能性信息。如果所选择的构件不完全符合复用者的要求，那么复用者可 以对其进行适当的修改。但是，随着所需修改部分比例的增加。修改构件所花费的代价将 快速增长，因此，在合理的分工模式下，更为适合的方法是将信息反馈给构件的生产者， 由构件生产者来完成构件的适应性修改。构件组装：复用者的最终目标是通过组装现有构 件来开发软件系统。系统演化：通过快速替换系统中某些构件来对系统进行修改，如进行 错误更正、版本升级或适应不断变化的需求。 在上述的基于构件的软件开发过程中，构件管理对构件生产和构件复用的过程起到了 承上启下的作用。而构件的管理是由构件库管理系统实现的。因此，在基于构件的软件开 发中支持构件分类、组织、存储和检索的构件库管理系统是一个非常重要的角色。 1 1 2 意义 基于构件的软件开发是软件复用的重要手段，软件复用的成功与否在很大程度上取决 于构件库的体系结构、构件的分类模式、检索方式等。研究表明：如何检索和提取满足用 户需求说明的构件一直是构件库管理系统的核心问题巧1 。随着构件的增多，构件库的构 件数量的不断膨胀，为构件库的管理带来了诸多不便，在大型的软件构件库中检索符合用 户需求的构件变得越来越困难。目前，一种合理的构件库组织方式和高效的检索机制成为 软件学术界和产业界需要迫切解决的热点和难点问题。从构件自身特点出发，寻求一种能 支持构件自动组织分类的方法，采用多种构件检索机制相结合的方式，对目标构件进行量 化的匹配计算，这样在一定程度上解决了构件的检索问题。与单一的构件检索机制相比， 这种方法占有很大的优势，它不仅提高了构件查询的灵活性，为构件用户查询构件提供了 帮助，而且在保证查全率的基础上一定程度地提高了构件的查准率。因此在软件产业中对 构件库构件的检索匹配研究具有很高地学术意义和实用意义。 1 ) 学术意义 推动软件复用技术的研究和发展。软件复用是解决软件危机的一种有效途径。从 3 6 0 年代发展到今，对软件复用的概念和技术已获得了许多共识，软件复用已经融入软件 工程研究的主流。被视为是软件开发真正走向工程化和产业化道路的希望。复用的观念已 成为软件过程模型的思想之一。基于构件的软件开发是软件复用史上的又一次的飞跃。对 其的研究必定推动软件复用的空前绝后的发展和复用技术的变革。 推动基于构件的软件工程( c o m p o n e n t b a s e ds o f t w a r ee n g i n e e r i n g 简称c b s e ) 的 更进一步的深入研究。构件库的组织体系和检索是构件库的研究重点和难点，合理的构件 库的组织体系和高效准确的检索机制是目前构件及构件库的研究主流和方向，也是基于构 件的软件工程( c b s e ) 的主要环节之一。为构件的获取和利用，构件的开发提供技术保障。 研究构件表示、组织和检索的策略，提出一种可行的构件检索改进的技术，以提 高构件的检索效率。利用构件开发的目的之一就是降低开发成本，提高开发效率。构件复 用的成本包括：检索成本、理解成本和修改成本。只有提高检索效率，降低复用成本，才 能体现利用构件开发的优势。分类模式是检索的基础，常用的分类方法有：枚举分类、属 性值分类、正文检索、关键词分类、刻面分类等。 2 ) 实用意义 提高软件开发的生产率。传统产业的发展模式均是符合标准的零部件( 构件) 生产 以及基于标准构件的产品生产( 组装) ，其中，构件是核心和基础，“复用 是必需的手段。 实践表明，这种模式是产业工程化、工业化的必由之路。机械、建筑等传统行业的成功发 展均是基于这种模式并充分证明了这种模式的可行性和正确性。软件产业要发展并形成规 模经济，标准构件的生产和构件的复用是关键。 实现构件的产业化和推广应用。经过软件复用的研究和实践方面的努力，国内外 在构件开发方面已经取得一定的成果。当前，国外一些政府、军方或企业自己拥有构件库， 在某些领域，如科学计算，已有商用的构件存在。同时，存在大量独立于应用领域的计算 机特定的软件构件，如：程序设计语言的类库、函数库、v b x 、o c x 、用户界面构件等。 国内有国家“九五”科技攻关项目，国家8 6 3 高科技发展计划资助项目的北大青鸟构件库 管理系统等。但对大多数特定领域来说，可复用构件仍十分短缺，从而形成了一个巨大的 应用软件构件市场。 为开发商业的构件库管理系统提供参考模型。本课题在研究构件检索过程中，基 于n e t 平台，用c 静和x m l 语言实现一个支持该理论的构件库模型。该模型应能具 备如下的性能要求：支持构件低成本入库、提供构件描述语言体系、支持快速查询( 保证 查全率) 、对查询结果能进行定量的匹配度分析( 较高的查准率) 。本课题完成后，能够为 开发构件库产品提供良好的参考价值。 1 2 国内外研究现状 4 针对不同的构件描述形式，研究人员己提出了许多相应的检索方法。如：a n d y 绪论 p o d g u r s k i 等人针对构件的行为表示提出的基于构件行为采样的检索1 7 1 ；a m ym o o r m a n m 等人针对构件的形式化规格说明提出的基调匹配( 接1 ：3 规约) 和规约匹配( 功能规约) 1 1 0 1 。 针对传统的构件文献编目描述，许多研究学者还提出了将神经网络、模糊数学、关联传动 等方法应用于构件的检索。 目前，构件的刻面描述是一种正逐步得到重视与应用的描述方法隅1 ，r e b o o t 、n a t o 、 提出的构件分类方法都是基于刻面的。青鸟构件库的构件也是采用以刻面分类为主j 多种 分类模式相结合的方法对构件进行分类描述的。 在国外，对构件检索技术已取得丰硕的研究成果。 r e b o o t 【9 1 ( r e u s eb a s e do no b j e c t o r i e n t e dt e c h n o l o g y ) 是一个包括存储可复用构 件的数据库和一组生产、认证、插入、提取、评价和适配可复用构件的工具的环境。其中， 在对构件进行分类时采用了刻面的分类策略，这种分类策略主要针对面向对象的构件。 r e b o o t 定义了四个刻面：抽象、操作、操作于、依赖。使用这四个刻面描述与之合作 的其它构件，其术语空间与抽象刻面是基本一致的。从整体上看来，r e b o o t 的刻面分 类模式主要针对的是源代码级别的构件，而且不具备描述粒度较大、结构较复杂的构件 ( 如：模式、框架等) 的能力。 。 n a t o1 1 0 1 ( n o r t ha t l a n t i ct r e a t yo r g a n i z a t i o n ) 提出了一种刻面分类模式，其中的刻 面不必是彼此独立的，也不必适用于所有的构件。一组典型的刻面可能包括：对象、功能、 算法、类型、语言和环境。在对一个构件进行分类时，不一定所有的刻面多出现。刻面术 语具有同义词关系，一组同义词表达一个概念，术语空间由这些术语构成，术语之间没有 一般特殊关系，即术语空间是非结构化的。 近年来，国内对构件检索技术的研究也取得了一定的可喜成绩。 一 以我国北京大学的青鸟工程为构件检索技术研究工作的代表。青鸟工程在“九五 期 间开发了基于异构平台、具有多信息源接口的应用集成环境，即青鸟i i i 系统1 3 1 1 。在相应 构件模型的基础上，建立青鸟构件库数据模型，并与其它c a s e 工具相结合，支持对构 件的描述、分类、管理、存储、检索和复合，满足了基于“构件构架”复用的软件开发 过程的需要。 上述的各种方案，都是针对检索构件本身而言的。然而在实际的构件复用过程中，构 件的检索不仅应该能够高效检索出相关的构件集，关键是如何快速地在所检索到构件集中 找到自己真正的需求构件，这是一个复杂的决策过程，一般都依赖于复用者的复用经验以 及通过浏览构件描述信息对构件的理解和主观评判。 1 3 主要存在的问题 尽管软件复用思想早己为人们所接受，然而软件复用技术并没有在实践中得到广泛的 应用，特别是在大型、复杂的软件开发中，系统化地使用软件复用的情况并不多。阻碍软 5 件复用的因素很多，主要包括以下几个方面： 1 ) 可复用构件开发成本问题 大粒度构件复用产品的复用频率问题无疑是一个非常关键的问题，由小粒度可复用构 件组合而成的大粒度可复用构件，往往由于设计者对领域知识分析重视不够，导致它们只 适用于本系统，难以扩展到该领域内的其他系统中去，这将导致软件复用频率降低；由于 可复用软件要经过严格的测试、要具有通用型等要求，因此开发可复用软件的费用要比开 发一般模块的费用要昂贵，w t r a c z 认为开发可复用构件的费用比开发一般模块要超出 3 0 一2 0 0 。从收回在复用项目上的投资需要时间看，w t r a c z 发现，在一个构件上的投 资只有在第3 次被复用之后才能收回。 2 ) 软件复用产品的分类检索问题 近年来随着面向对象技术的发展，以及o l e 、c o r b a 、j 2 e e 等工业标准的出现，大 大刺激了构件技术的发展。随着软件复用实践的深入和时间的推移，企业内部积累的构件 将越来越多、企业外部对构件的需求也越来越多。这样，就面临着以下问题：一方面，企 业内构件库内有大量的构件，由于复用人员的限制，复用率不高，另一方面，众多的企业 外的软件工程技术人员希望也需要能从共享构件库中获取共享构件。同时，企业或组织也 希望能方便地在企业或行业组织间进行构件的共享和交流。随着i n t e m e t 和w e b 技术的成 熟，使得企业或组织的构件库实现基于i n t e m e t 的共享成为可能和必然。这样不仅可提高 构件的复用率，而且，众多的构件可以通过i n t e r n e t 提交到构件库，也势必增大构件资源 的范围，这样如何有效地管理和检索构件，成为研究的重点。 1 4 主要研究工作 1 ) 分析了构件表示与分类模式及检索技术的国内外的研究现状和其所存在的缺陷。 2 ) 本课题重点研究了基于刻面分类模式的构件表示，并探讨了使用x m l 作为构件 信息描述语言优越性及基本原则，给出了如何将x m l 文档转化为树结构，为树匹配奠定 了理论基础。 3 ) 针对构件检索的特点，结合模式分析中的树匹配思想，在基于x m l 的刻面描述 构件表示的基础上，本文提出了基于x m l 的树匹配构件检索算法，并研究了如何将树匹 配应用于构件匹配检索中，以实现保持构件查准率的前提下，有效提高构件的查全率。 4 ) 针对基于刻面的构件检索算法的局限性，鉴于人工智能中遗传算法的思想，本文 提出了基于遗传算法的刻面权重自学习构件检索算法，并研究了如何将遗传算法应用于构 件检索中，来动态地改变刻面权重以提高查准率。 5 ) 针对上述研究理论，利用m i c r o s o f t 的n e t 技术和x m l 技术，在m i c r o s o f t s t u d i o n e t 2 0 0 5 开发环境下，开发出一个构件检索工具原型，验证该构件检索理论的可 行性，为开发软件构件库相关产品提供参考。 6 绪论 1 5 本章小结 本章首先分析了论文的选题背景及意义，其次分析了国内外关于软件构件表示、构件 检索技术研究现状，并列出了国内外关于构件检索技术的研究成果，随后介绍了构件检索 技术所存在的问题，最后给出了本课题的主要研究工作。 7 构件及其检索理论 2 构件及其检索理论 2 1 构件的概念及特征 2 1 1 构件概念 构件3 1 来源于英文的“c o m p o n e n t ，在有些文献中也称其为组件，目前，对构件的 概念，软件产业界还未形成统一的认识。一般来说有广义和狭义之分，从广义上讲，构件 是指可以被明确标识的软件制品，它可以是需求分析、设计、代码、测试用例、文档或软 件开发过程中的其它产品。从狭义来说，软件构件是指可复用的、提供明确接口、完成特 定功能的程序代码块( 源程序、二进制代码或可执行代码) 。 构件的发展经历了以下三个阶段h 1 ： 第一阶段：2 0 世纪6 0 年代末到8 0 年代初，结构化的软件开发方法开始占主导地位， 该阶段构件指的就是一些定义良好的方法或者是功能模块。 第二阶段：8 0 年代起，面向对象的开发思想开始发展起来，该阶段构件指的就是类 库。此时的类，具备了一定的封装性、多态性和继承性，但是还依赖于具体的编程语言， 因此不能完全达到可移植性和互操作的要求。 第三阶段：9 0 年代后，构件的内涵开始得到加强，聚合性，独立性和复用性得到进 一步提高。此时的软件构件的定义得到完善。 在本文中，一般认为构件是具有相对独立功能和具有可复用价值的软件构成成分。 2 1 2 构件特征 一般来说，构件主要有以下特征： 独立性：构件可独立开发( 需求分析、设计、编码、测试) 、部署和发布。 定义良好的接口：构件通过一组接口对外完成其功能，接口可分为对外服务的接口和 请求服务的接口。 封装性：构件是一个高内聚的软件包，通过接口对外交互，屏蔽了内部实现细节，构 件可通过独立开发封装为符合业界认可的模型标准的二进制代码。构件封装采用的标准 1 2 1 有：c o m c o m + ；d c o m ：j a v a b e a n s e j b ；c o r b a 等。 可替换性：构件被组装到软件系统中后，可以用具有相同接口和相同标准的其它构件 将其替换下来，替换中无需任何编码工作，替换后该软件系统仍能运行。 可组装和调整性：构件可在定义良好的体系结构下方便的组装到软件系统中，也可与 9 西安理工大学硕士学位论文 其它构件组装成为粒度更大的构件。一般情况下，构件要有方便的可调整机制以便复用， 即提供了多个可变点有利于用户化。 2 2 构件库技术 软件构件库9 ( c o m p o n e n tr e p o s i t o r y ) 是一种组织、收集、访问与管理若干构件的 手段，它由构件库的数据和构件库管理系统组成。构件库的数据包括构件本身及其描述性 信息和组织性信息。这些信息总称为构件目录，其中描述性信息称为构件描述，组织信息 称为库信息模型。构件库管理系统由构件库框架和构件库管理工具组成。构件库包含了大 量信息，包括构件，构件描述信息，构件库数据模型和描述数据模型的模型。构件库可以 在d b m s 之上实现其目录，在一个形式化的配置管理系统中保存构件。 按照功能将一个具有普遍性构件库管理系统的分为三个层次，分别是构件库的入库系 统、构件库的维护系统、构件库的组装系统。构件库系统如图2 1 所示： 构 件 维 护 构 件 组 装 图2 - 1 构件库系统 f i g 2 - 1c o m p o n e n tr e p o s i t o r ys y s t e m 和数据库管理系统一样，构件库管理系统可以划分成若干层次清晰合理的功能模块， 这不仅可以帮助我们更清楚地认识构件库管理系统，更重要的是有助于对构件库管理系统 中关键技术进行分析。 如图2 - 1 所示，按照功能将一个具有普遍性构件库管理的系统分为三个层次，分别是 构件库的入库系统、构件库的维护系统、构件库的组装系统。 ( 1 ) 构件库的入库系统 构件制作完成后，通过对构件的分类和描述，以及合法性的检验，将构件存入构件库 中。其中，构件的存储功能解决构件在构件库管理系统中的具体存储方法和数据结构，是 1 0 构件及其检索理论 实现构件库管理系统的前提。构件的描述分类方式则决定了构件在构件库中组织形式和检 索方式、构件间的逻辑关系、构件的合法性规则。 ( 2 ) 构件库的维护系统 完成对构件库中的构件进行检索、修改、插入、删除、统计等功能，是构件库管理系 统运行的支撑系统。构件库的维护系统类似于数据库管理系统d b m s 对数据库管理功能， 其中构件的检索功能是构件库维护系统的基本功能，由于检索功能直接与用户进行交互， 因此检索的效率和功能就直接关系到是否能查全、查准用户所需要的构件，是否能够将检 索的过程控制在用户所能容忍的时间空间开销内。可以说，检索功能是整个构件库管理系 统的核心功能。 ( 3 ) 构件库的组装系统 将检索到的构件经过修改，插入等过程后，得到用户预期目标的或者接近于用户预期 目标的构件，并将这些构件按照用户所规定的序列进行构件组装，最后生成应用系统的过 程。 2 3 构件检索技术 好的分类模式是有效检索与理解的基础。w f r a k e s 和h m i l i 分别研究了现有的构件 的分类和检索方法。w f r a k e s 从构件的表示出发，将现有方法分为基于规约描述方法、 人工智能方法、超文本方法和信息科学方法4 类f 刀；因此可以将构件检索技术分为4 类： 即基于规约描述方法的构件检索技术、基于人工智能的构件检索技术、基于超文本浏览的 构件检索技术及基于信息科学的构件检索技术。而基于人工智能的构件检索技术又可以划 分为3 种：即基于构件行为采样的构件检索技术、基于知识的构件检索技术和基于神经元 网络的构件检索技术3 种。下面就各种构件检索技术概括介绍一下。 2 3 1 基于规约描述方法的构件检索技术 基于规约描述方法的构件检索技术根据规约描述的具体形式不同，主要可分为基调匹 配( s i g n a t u r em a t c h i n g ) 和行为i 龋( ( b e h a v i o r a lm a t c h i n g ) 两类。构件检索时，用户首先写 出需求规约，然后提交。构件检索的实际过程一般由证明器根据构件规约与需求规约间的 某一偏序关系进行检索，构件库中的构件一般按照构件规约间的偏序关系来组织。这样， 在构件检索时检索历程可以大大减少需求规约与构件规约比较的数目，从而提高检索效 率。 基于规约描述方法的构件检索技术注重软件构件的行为特征，而不是它的外观描述； 其优点是明显的，即能完整描述构件的计算语义、检索的准确率比非形式化方法高等，它 能够较好的满足用户对构件检索查准率和查全率的综合要求。但是，基于规约的检索也给 西安理工大学硕士学位论文 用户带来了书写规约的额外负担( 特别是在构件的功能比较复杂时) ；检索时间依赖于所用 的方法；并且，目前还没有什么实践上的成果可以从自然语言自动生成形式化规约。所以， 基于规约描述方法的构件检索技术的普及和推广还有待时日。 2 3 2 基于人工智能的构件检索技术 基于人工智能的构件描述方法又可以细分为基于行为采样的构件检索技术、基于知识 的构件检索技术和基于神经网络的构件检索技术3 种。 基于行为采样的构件检索技术 基于行为采样的构件检索技术的基本思想2 0 1 是，利用构件的执行能力来检索构件。 由构件的开发者对每一个构件选用一些典型的实际数据作为输入，然后得到该构件的输出 数据。用输入数据、输出数据及返回类型作为构件的一个采样。 但是，基于行为采样的构件匹配方法也具有它先天的不足，该方法只适用于代码级构 件，因为它的匹配算法的基础是构件的可执行性。而且，要实现该方法下的松弛匹配和复 杂构件的匹配，需要一个开放式行为采样脚本语言的实现平台，而这是一项艰巨、复杂的 工程，有时几乎是不可行或不可能的。 基于以上的特点，目前行为采样的构件检索技术主要还只是应用于数学函数、符号运 算函数和常用a d t ( a b s t r a c td a t at y p e 抽象数据类型) 库等这一类专业性比较强，并且行 为采样比较容易的构件库中。 基于知识的构件检索技术 这类检索技术所基于的构件描述方法是对软件构件的自然语言描述进行一些词法、句 法和语义的分析，并用一个知识库来存放应用领域以及自然语言本身的语义信息。因此， 基于知识的构件检索技术的基本原理是：构件检索时，根据用户提出的各种要求，生成系 统内部的提问形式，启动推理机求出结果，以用户易读的形式显示0 常用的有语义网和框 架描述形式，如m u r r a yw o o d 等人应用概念依赖模型，采用框架形式，描述和检索构件， 不过这种方法需要相当丰富的框架。b e r t r a n di b r a l l i m 等人开发的r o s a 系统，通过对软 件构件的自然语言描述进行语法、句法分析来确定软件构件的语义，再用同样方法处理的 用户请求信息进行匹配。 这种构件检索方法较之传统的基于关键词的检索方法准确、有效。但是，知识库的构 造通常是手工实现的。因此，这种方法的代价是很大的。 基于神经网络的构件检索技术 a g w o l f d i e t e rm e r k l 在他的博士论文中首次提出了将构件库中的所有构件在逻辑上组 织成一个自组织的神经网络的思想。该方法使用神经网络技术，依据软件构件的功能相似 度来构造构件库。例如，功能相似的构件被安置在相邻的位置。这样，构件之间的相似度 就变得清楚了，因为它受构件间的地理相近度决定。该方法检索过程如下：用户的查询术 1 2 构件及其检索理论 语集合通过系统首先转化为一个输入矢量，然后将该矢量输入进该神经网络，通过竞争后， 在网络的输出层得到一个优胜的节点( 该网络输出层的节点与构件库中的构件在逻辑上具 有对应关系) ，最后将该优胜节点以及其一定领域范围内的所有节点所对应的构件作为本 次检索所得到的结果反馈给用户。 神经元网络为依据用户的适当评价递增地改变概念距离权值提供了理想的框架。该方 法的技术关键在于网络的学习算法与竞争算法。该项技术最大的优点在于它可以通过竞争 学习，自组织的将构件按语义相关性进行逻辑上的组织，以方便构件的检索。它解决了组 合爆炸问题：在基于分类方法的检索系统中，相似度计算通常用一个概念距离图来实现， 该图建立了分类方法中限制词汇表中术语的相似度。当软件构件库很大的时候，对该图的 手工调整是不切实际的，因为在概念图上的关系数被认为是组合爆炸。 但是，目前神经网络在构件检索中的应用，要求输入矢量的维数是固定的。矢量的维 数一旦发生变化，那么原先的学习算法与竞争算法都需要重新设计。这个弱点决定了神经 网络技术不能作为那些描述经常发生变化的构件库的检索技术。因此，基于神经元网络的 构件检索技术依赖于神经元网络技术的发展而完善。 2 3 3 基于超文本浏览的构件检索技术 这种描述方法采用了超文本链接技术，信息依据不同的链接或关系被组织成网络上 的结点，或称为信息单元。用户依据存在的链接浏览信息网络，而与链接相关的语义可以 引导用户达到合适的结点。因此，基于超文本浏览的构件检索技术以线性检索为主要检索 机制。一些系统也采用了浏览方法作为辅助的检索机制，其浏览的起点是从用户的请求开 始的。 这种方法比较直观，但是需要用户操纵浏览过程，这对于大型的软件库是很困难的。 因此，这种方法一般只用于进行辅助的检索。 2 3 4 基于信息科学的构件检索技术 基于信息科学的构件检索技术是实际重用项目中，应用较为成功的途径。其中以枚举、 刻面、属性值、关键词和正文检索几种方法最为常用，又以关键词分类( k e y w o r d ) 和刻面 分类( f a c e t e d ) 两种应用最多t 2 6 1 0 下面先对各种分类方法的特点进行简单介绍： 枚举分类：通常将一个被关注的领域严格划分为不相交的子领域，依次构成层次结 构：该方法对领域知识进行清晰高度结构化的划分，易于理解和使用；但该方法过于严格， 使得分类模式难以伴随淋浴演变而改变，能够表示的关系也受到限制。 属性值分类：与刻面分类相似，所不同的是刻面对应的术语空间是有限的不定空间， 而属性的值域往往是无限的确定空间，刻面的选择也远远比属性要慎重。 1 3 西安理工大学硕士学位论文 关键词分类：简单而且普遍，每个构件以一组与之相关的关键词编目，一般认为关 键词的取值不受限制。由于关键词缺少上下文语境而不够精确，导致该方法所支持的查询 效率不高。 2 3 5 基于刻面的构件检索方法 本文所要研究的是基于刻面分类模式，因此有必要详细的介绍一下刻面分类模式。 刻面( f a c e t ) 这个术语最早使用是在5 0 年代，分别出现在r a n g a n a t h a n 的图书馆分 类系统中g u t t m a n 的一项社会调查中，但那时候，刻面的概念还比较模糊，刻面之间存在 着语义上的文选等诸多不合理的因素。 现代构件库管理系统的刻面分类检索方法是p r i e t o d i a z 和f r e e m a n 在1 9 8 7 年提出的， 这种方式通过反映构件本质特性的视角( 刻面) 对构件进行精确的分类。一个刻面分类模 式( f a c e t e ds c h e m e ) 由一组描述构件本质特征的刻面组成，每个刻面从不同的侧面对构 件库中的构件进行分类。每个刻面由一组术语( t e r m ) 构成，称为术语空间( t e r ms p a c e ) ， 描述子( d e s c r i p t o r ) 由不同的刻面中不同术语构成，用来描述构件库中的特定构件。通过 用户构造描述子形成查询条件，在构件库中查询符合条件的构件，这样对于用户来说可以 直观的从不同角度指明待检索的构件，有利于用户对构件的理解。 这种分类模式包括了3 个基本的元素：构件描述符、同义词词典以及概念距离图，如 图2 2 所示。构件描述符是一个有序n 元组，集合中的每一个元素对应一个刻面，每个刻 面从不同的角度来描述构件。同义词词典是把表示同概念的词放在同一组中，是用以消 除同义词对检索影响的工具。概念距离图描述了两个术语间的相似程度。在检索构件时， 用户根据查询需求从各个刻面中选择术语，组成合法的构件描述符。如果没有完全匹配的 构件，那么系统将根据同义词词典和概念距离图计算出术语的相似性，形成新的查询，找 出的构件将根据相似度程度排序。 1 4 嫩 艿构件接透特 。，：赢，t ，。， i 上上 f i tb ，r ， t nt 2 lb t zkt ) 2 - 图2 2 刻