（计算机软件与理论专业论文）基于刻面描述的构件检索算法研究.pdf

摘要 软件复用是解决软件危机，提高软件生产效率和质量的一条现实可行的途 径河复用软件构件库系统作为软件复用的基础设施，它的研究正得到专家学者 们越来越广泛与深入的关注。 构件的刻面表示方法是目前构件库系统中所主要采用的一种构件表示方法。 它具有较强的表示能力和灵活的扩展机制。但是目前，随着软件复用实践的深入 和推广，软件构件库的规模f 逐渐庞大，软件构件的刻面表示也变得只益复杂。 在这种趋势下，现有的刻面表示构件的检索方法f 逐渐成为构件库使用的一个瓶 颈，这主要表示在以下三个方面： l - 缺乏有效的手段在保证查全率的基础上提高构件的查准率； 2 查询用户需要了解构件库的刻面分类方案； 3 不能实现在不同刻面分类方案的构件库之阳j 进行构件检索； 为此片本文在对构件的刻面表示方法进行深入研究的基础上，结合模式分析 中的树匹彘思想，并根据构件刻面描述的特点，提出了一种基于树匹配的针对刻 面表示构件的新的检索方法。这种新的检索方法可以有效的解决原有检索方法的 以上不足。 本文首先借鉴树匹配中关于树包含的思想，并结合构件刻面描述方法的具体 特征，提出了一个包含四个层次的构件刻面匹配模型。其次，在该匹配模型的基 础上引入了树匹配中关于树编辑距离的有关概念，提出了计算匹配代价的思想。 最后，利用上述的匹配模型以及匹配代价计算的思想，提出了一个系统的构件检 索过程。 另外，由于对无序标签_ 时的编辑距离计算属于n p 难问题，所以在上述匹配 模型中根据构件检索的具体特征，加入了合适的限制条件，这使得匹配模型中各 层次匹配代价的计算基本都可以在多项式时间内得到解决。并且，在算法的具体 设计中，还应用到了动态规划、网络规划和模拟退火的等优化思想，进一步提r 商 了该检索方法的有效性与实用性。 这种新的构件检索方法，使得查洵用户可以通过匹配层次的选择以及匹配代 价的计算，在保证构件检索的查全率的情况下有效地提高构件检索的查准率。并 且，由于这种方法是建立在构件刻面表示的树形抽象基础上的，所以它向用户屏 蔽了构件库的刻面分类方案。因此利用这种检索方法也可以实现跨越不同刻面分 类方案的构件库问的构件查找，这将十分有利于可复用软件构件库面向网络的分 布式检索的实现。弋 最后，设计并实现了一个原型系统，实践了上述的检索方法，并通过在该 原型系统上的一些实验数据，进一步论证了该构件检索方法的可行性与有效性。 关键词： 软件复用? 可复用软件构件库? 刻面分类? 构件检索：树匹配 n a b s t r a c t s o f t w a r er e u s eo f f e r sas o l u t i o nt oi m p r o v ee f f i c i e n c ya n dq u a l i t yi nt h es o f t w a r e d e v e l o p m e n ta n d i sc o n s i d e r e da sap r a c t i c a la n df e a s i b l ea p p r o a c ht os o l v es o f t w a r e c r i s i s r e u s el i b r a r ys e l v e sa st h ef o u n d a t i o no fs o f t w a r er e u s e ，w h i c hg a i n s m o r ea n d m o r ea t t e n t i o nf r o mr e s e a r c h e r s f a c e t e dc l a s s i f i c a t i o ni so n eo fp r i m a r ym e t h o d st od e s c r i b er e u s a b l ec o m p o n e n t ， w h i c hh a ss t r o n gr e p r e s e n t a t i o na n df l e x i b l ee x t e n s i o n h o w e v e r , w i t ht h ed e e p e n i n g o fr e u s ep r a c t i c e s ，t h ei n c r e a s i n gs i z eo fr e u s el i b r a r i e sa n de n r i c h i n go ft h ef a c e t e d c l a s s i f i c a t i o n ，t h ec u r r e n tr e t r i e v a lm e t h o di sb e c o m i n gt h eb o t t l e n e c ko fs o f t w a r e r e u s i n gf o ri th a ss h o w e df o l l o w i n gd e f i c i e n c i e s ： 1 l a c k i n g o fe f f i c i e n tm e a n st oi n c r e a s ep r e c i s i o nw i t had e g r e er e c a l lh o l d i n g ； 2 r e q u i r i n gu s e r sh a v ek n o w l e d g ea b o u tf a c e t e dc l a s s i f i c a t i o ne m p l o y e db yr e u s e l i b r a r y ； 3 h a v i n gg r e a td i f f i c u l t y i nr e t r i e v a l s p a n n i n gm a n y ad i f f e r e n tf a c e t e d c 】a s s i f i c a t i o n a c c o r d i n g t o e x i s t i n g r e s e a r c ho nf a c e t e dc l a s s i f i c a t i o ns c h e m e ，t h i s p a p e r p r o p o s e s an e wm e t h o db a s e do nt r e ei n c l u s i o nt or e t r i e v er e u s a b l ec o m p o n e n t s c l a s s i f i e di nf a c e t e ds c h e m e ，w h i c hc o m b i n e st h et h e o r yo ft r e em a t c h i n ga n dt h e f e a t u r e so ff a c e t e dc l a s s i f i c a t i o ns c h e m e t h i sn e wm e t h o dc a nr e s o l v ea b o v et h r e e d e f i c i e n c i e se f f e c t i v e l y f i r s t ，af o u r l a y e rm a t c hm o d e lf o rc o m p o n e n tr e t r i e v a lw a sp u tf o r w a r d ，w h i c h c o m b i n e st h et h e o r yo ft r e ei n c l u s i o na n dt h ef e a t u r e so ff a c e t e dc l a s s i f i c a t i o ns c h e m e s e c o n d l y , t h ei d e ao fm a t c hc o s tw a sp u tf o r t h ，w h i c hw a si n s p i r e db ye d i t i n gd i s t a n c e b e t w e e nu n o r d e r e dl a b e l e dt r e e s t h i r d l y ，as y s t e m i cp r o c e s st or e t r i e v ec o m p o n e n t w a s g i v e n b a s e do na b o v em a t c hm o d e la n dm a t c hc o s t r e s e a r c hs h o w e dt h a tt h eu n o r d e r e dl a b e l e d t r e e m a t c h i n gp r o b l e m i sa n n p - c o m p l e t eo n e i nt h i sp a p e r , s o m ec o n s t r a i n sw e r ea d d e db a s e d o nt h ef e a t u r e so f c o m p o n e n tr e t r i e v a l ，w h i c hm a k e s i t p o s s i b l ef o rt h ec o m p u t a t i o no f m a t c hc o s tt ob e n i r e s o l v e di np o l y n o m i a lt i m e m o r e o v e li nd e s i g n i n ga l g o r i t h m ss o m eo p t i m i z a t i o ni s a p p l i e dt oi n c r e a s ee f f i c i e n c yo fa l g o r i t h m ss u c ha sd y n a m i cp r o g r a m m i n g 、n e t w o r k p r o g r a m m i n g a n ds i m u l a t e da n n e a l i n ge t c w i t ht h i sn e wm e t h o d ，u s e r sc a n a d j u s t r e c a l la n d p r e c i s i o n o fr e t r i e v a l b y c h o o s i n gt h el e v e lo fm a t c ho rc a l c u l a t i n gm a t c hc o s t o nt h eo t h e rh a n d ，i td o e sn o t r e q u i r eu s e r st ok n o wt h ef a c e t e dc l a s s i f i c a t i o n ，w h i c hc a nb eu s e dt o i m p l e m e n t r e t r i e v a lw h i c h s p a n sm a n y ad i f f e r e n tf a c e t e dc l a s s i f i c a t i o n i nc o n c l u s i o n ，ar c r s p r o t o t y p ew a sd e s i g n e db a s e do nt h i s n e wr e t r i e v a l m e t h o d s o m ec o m p l e x i t ya n a l y s i sa n de x p e r i m e n t so nt h er c r sp r o t o t y p eh a v e b e e nd o n et od e m o n s t r a t ei t sf e a s i b i l i t ya n de f f e c t i v e n e s s k e y w o r d s ：s o f t w a r er e u s e 、r e u s el i b r a r y 、f a c e t e dc l a s s i f i c a t i o n 、 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 g 指导小组成员名单： 朱三元教授，博士生导师 钱乐秋教授，博士生导师 夏宽理教授 本文中所经常使用的符号及其表示意义 l 州树t 的节点数目 f f 1树丁中编号为i 的节点 丌i 1树了 中以f 为根节点的子树 f i 1t i 1 中删除节点i 得到的森林 c “j节点i 的儿子节点集合 d ( i ) a i ) l a b e l ( i ) d o m a i n r r a n g e ( 7 ) s p e c t r u m ( 1 9 s p e c t r u m 0 9 臼 q d 节点i 的子孙节点集合 节点i 的前辈节点集合 节点i 的标签 映射，的定义域 映射，的值域 映射，的映射谱 映射，的广义映射谱 空节点或空标签 空树 查询树 构件的刻面描述树 v 生立兰竺 1 1 研究背景 第一章绪论 六十年代的软件危机导致了有关软件复用的研究。在1 9 6 8 年n a t o 软件工 程学术会议上，d m c i l r o y 在论文中首次提出了可复用软件构件库的思想以及形 式化软件复用的概念。 在其后的三十多年中，软件复用引起了学术界和工程界广泛的关注。人们进 行了许多探索性的、实践性的复用活动。从中人们认识到，软件复用技术能够有 效地提高软件生产率，降低软件丌发费用，增加软件的可靠性及可维护性，提高 软件的质量f 1 1 。但是从一些失败的或成效不显著的复用案例中，人们总结出了 以下的主要原n e 1 ： 1 缺乏对复用的管理支持； 2 没有对开发可复用软件及复用已有的软件构件的激励措施； 3 没有强调针对复用实践的规程或过程； 4 没有足够的可复用的资源： 5 没有良好的分类模式，使得构件的查找比较困难； 6 没有良好的构件库支持； 7 构件库中的构件没有良好的接口； 8 已有的构件不是为了复用而丌发的； 在七述的八点原因中，第一点到第四点主要是属于管理和组织方而的问题 它们的解决将等待复用实践活动的进一步的普及与深入。第七点和第八点问题的 解决则有待于构件接口标准，互连协议等有关标准、协议的制定与推广。然而这 一些都有赖于作为软件复用的基础设施之一的可复用软件构件库支持的完善和 成熟。而这也正是上述第五和第六点问题需解决的重点。 一个完善的、高效的构件库系统是使软件复用实践真讵系统化、工程化的蓖 要毡础设施之。很难没想，缺乏充足的可复用软什构件资源，没彳f 精确的、 ： 寓的构件检索手段，软件复用的实践将如何实施。 1 2 研究的内容与意义 在可复用软件构件库支持中值得研究的问题有很多，它们涉及到很多方丽， 例如法律、管理、经济、网络、信息检索等睹多领域。本文将针对叶1 的构件枪 索领域中的方法与技术进行一些探索性的研究与讨论。 蚺1 虹 笙二皇竺垒 讨沦沟件的检索必定离不丌讨论构件的表示方法。 虽然目前提出的构件表示方式有许多种，但这些表示方法追本溯源都可归结 为两个主要的构件描述模型：3 c 模型与r e b o o t 摸型【3 】。其中3 c 模型主要是 用于对构件的可复用信息进行描述【4 】，它主要用于解决1 1 节中的第七个问题 ( 当然，通过规约匹配的有关技术也可以利用它柬进行构件的检索【5 】) 。而 r e b o o t 模型f 6 1 ( 该模型是在r e b o o t 项目中提出的，它的许多机制是建立在 p r i e t o d i a z 的研究工作的基础上，它实质上是一个刻面分类模型。) 则是主要用 于对可复用构件进行分类及检索，相比之下，它与构件检索的关系更加密切。所 以，可复用构件的3 c 模型的描述主要是由构件的生产者提供，而可复用构件的 r e b o o t 模型的描述则主要是由构件库的管理者提供。 基于上述两个描述模型，目前提出的构件表示方法有很多种，具有代表性的 有：( 1 ) 规约描述方法：可细分为功能规约、接口规约两大类方法【4 】。( 2 ) 编目分 类方法：可细分为图书馆与信息科学方法，人工智能方法和超文本方法三大类方 法7 1 。其中对图书馆与信息科学方法的应用最为广泛，它的具体形式有：枚举 法，关键字法、属性值法等方法。 针对上述各种构件表示方法，相应的构件检索方法也一一提出：如a n d y p o d g u r s k i 等人针对构件的行为表示方法提出的基于构件行为采样的检索【8 】， a m ym o o r m a n n 等人针对构件的形式化规格说明提出的型构( s i g n a t u r e ) 匹配( 接 口舰约) 和规约匹配( 功能规约) 【9 ，1 0 ，1 1 1 。针对构件的文献编目表示方法，许 多研究学者【i 玉提出了将神经网络 1 2 】、模糊数学【1 3 、关联传动f 1 4 】等方法应用于 构件检索的思路。 1 9 8 7 年，r u b 6 np r i e t o d i a z 等人在i e e es o f t w a r e 发表了题为( ( c l a s s i f y i n g s o f t w a r ef o rr e u s a b i l i t y ) ) 论文【1 5 】，系统地提出了用刻面分类方法柬对可复用软 件构件进行分类与组织的思想，具有重大的意义。 构件的刻面表示方法属于图书馆与信息科学方法的范畴，与同类的构件表示 方法相比，它具有以下两个优点f 1 6 】：( 1 ) 对构件进行了多视角下的分类描述：( 2 ) 构件分类描述的术语空间易于修改与维护。所以自它诞l 三起就表现j n 较强的描述 能力干灵活的扩展机制，立刻得到了普遍的应拜1 与研究。例如：r e b o o t 项目f 6 1 和n a t o 组织fj 7 1 提出的构件表示方法都是采用了刻面表示方法。我国的菁鸟系 统中的构件采j 目的也是以刻面分类为主、多种分类模式相结合的构件表示方法 【1 8 】o 但是，对于基于刻面表示的构件检索技术的实现，目前，卸一直还在沿用传 统数据库检索技术，并同时结合利用同义同词典和刻面术浯问的一股特殊关系 来实现构件的匹配【6 ，1 7 ，1 8 ，1 9 ，2 0 】。在软件复用实践不断普及与深入的今天，这 种方法正面对越来越严峻的考验，它的不足性主要体现在以下几个方面： 第21 i 她一蒂绪| 仑 1 缺乏有效的手段在保证查全率的基础上提高构件的查准率 2 查询用户需要了解构件库的刻面分类方案； 3 不能实现在不同刻面分类方案的构件库之间进行构件检索 针对这种情况，本文在深入分析刻面分类方法的基础上，提出了将树匹配的 思想引入构件匹配的观点。由于求解无序树匹配问题在树匹配领域中已被证明为 n p 难问题f 2 1 1 。为了提高这种新方法的检索效率并满足构件检索的具体要求， 本文根据构件刻面表示方法的具体特征，对树匹配思想的引入进行了适当的改 造。在此基础上，提出了一个包含四个匹配层次的，赋有匹配代价计算的构件匹 配模型，并且提出了一个基于该匹配模型的构件检索过程。同时对每一层次的匹 配算法进行了深入的研究，提出了高效的算法设计。 这种新的构件检索方法，使得查询用户可以通过匹配层次的选择以及匹配代 价的计算等手段，在保证构件检索的查全率的情况下有效地提高构件检索的查准 率。并且，这种方法几乎没有给用户带来代价，它不象传统的刻面匹配方法那样 要求用户对构件库的刻面分类方案有所了解。利用它也可以实现跨越不同刻面分 类方案的构件库问的构件查找，这将十分有利于可复用软件构件库面向网络的分 布式的检索【5 8 】。 1 3 本文的篇章结构 在展丌阐述本文的方法之前，首先对目前比较有代表性的几种构件检索方法 进行一次系统的总结是必要的，它们可以使我们借鉴到有益的思考，明确研究的 重点与方向，并为提出更有效的方法奠定基础。 在第三章罩，安排了对树匹配领域中有关知识的一次小结，并适时插入了本 文为将其引入构件刻面匹配而定义的一些新概念。在第三章的最后，还给出了树 匹配领域中的几个重要的研究问题的定义与研究现：扶。 存第p q 章中，首先应用树匹配的思想，针对构件的刻而捕述提了一个包 含四个匹配层次的内涵乍富的匹配模型。阐述了这个匹配模型的设计思想，许给 i h 了匹配代价的计算定义，以及阐述了基于该匹配模型的构件检索过程。在第p q 章的最后，还给出了计算匹配代价的泛型方法。 在后续的第h 章到第八章，针对无损包容匹配、无约束包容匹配、弱约束包 容匹配、强约束包容匹配分别给出了其各自具体的匹配代价的计算方法。每一章 的闸述方式为先概念分析，再定理证明，最后足算法的导山与分析。为了尽可能 地提高算法的效率，其中应用到了动态舰划、模拟退火、网络舰划等各种算法优 化思想。 嘏3 j l 第一尊绪沦 第九章是全文的最后一章它对全文的工作进行了总结，并建议了下一步的 研究方向。 全文的谋篇布局，可以形象的阐述为下图： 第九章：结论与展望 第五章至第八章： 匹配模州中箨层匹配算法的研究 第四章 基丁树匹配思想的四层匹配模州 构 ，| ： 匹 第纂 二基 萃裹 章本 概 概 述 念 软件复用大背景 图1 - 1 ：全文的谍篇布局 第41 j i 銎二里塑! ：! ：! 塑! ! 尘堕 第二章构件检索技术概论 关于构件检索的方法，目f j i 种类繁多，在此选择具有代表性的工作做一综述。 所谓有代表性是指：第一，它是其所针对的构件表示的检索方法中比较经典的， 具有指导意义的方法；第二，它在进行构件匹配时，体现了很好的松弛匹配能力， 这也是构件检索与一般的文本检索以及数据库检索的重要区别之一；第三，方法 上有代表，它往往是一门学科或一个领域中的知识与构件检索相结合的代表之 作： 针对诸多的构件检索方法，本文作以下的分类阐述： ( 1 ) 针对构件二进制码表示的构件行为采样； ( 2 ) 针对构件形式化规约表示的构件规约匹配； ( 3 ) 针对构件编目表示的传统信息检索技术； 2 1 基于构件行为采样的构件检索技术 利用行为采样来进行构件检索的实质是：通过代码级构件的可执行特征来完 成构件问的匹配。 它的检索过程可以简述如下：首先，查询用户给出要查找构件的一系列输入 数据以及相应的所期望的构件输出数据( 即所谓的行为采样数据) ：然后针对构 件库中的每一个构件依次执行这些输入数据，如果执行得到的输出数据都与所期 单的输出数据相同，则认为该构件是当前用户所要查询的构件，将它记录下来。 最后将所有被记录下来的构件反馈给用户。 a n d yp o d g u r s k i 在文献 8 中应用概率论的知识在一定程度上证明了利用行 为采样方法进行构件检索的可行性。进一步，他指出当采样数据的规模( 即输入、 输出数据对的数目) n 2 2 时，该方法可以从理论上保证该检索方法具有很高的 查准率。并且，他还进行了大量的统计实验，从中得出了以下的实验结论：在一 般情况下8 3 的 j 件查询只需要n ：3 就可以准确地睑索到所要寻找的陶什。 但是，基i f 行为采样的构件匹配方法也具有它先天的不足，主要有以fj l 点： 1 该方法只适用于代码级构件，因为它的匹配算法的基础是构件的可执行性。 2 要实现该方法下的松弛匹配和复杂构件的匹配，需要一个丌放式行为采样脚 本语言的实现平台，而这是一项艰巨、复杂的工程，有时几乎是不可行或不 可能的。 基r 以上的特点，所以目6 u 行为采样的构件检索方法主要还只是应用于数学 函数、符号运算函数耵常用a d t ( a b s t r a c td a t at y p e 抽象数据类型) 库等这一 蚺一啦f f ! j 件伶索投忙慨沦 类专业性比较强，并且行为采样比较容易的构件库中。 2 2 基于规约的构件检索技术 构件的规约说明是对构件的行为特征的形式化说明，它排除了自然语言描述 的二义性和不准确性，并且还可以利用规约说明之间的偏序关系来组织构件库中 的构件存储以提高构件检索的效率。 利用规约匹配柬进行构件检索的过程可以简述为：首先，查询用户按照规约 的书写要求将他的查询需求表达成正确的规约形式( 记为q ) 。然后，将库中构 件的规约( 记为s ) 依次与q 进行匹配，并将符合匹配成功条件的构件记录下来。 最后将这些记录下来的构件作为检索的结果反馈给用户。 从上面的检索过程可以看出。s 与q 的匹配是其中一个重要的环节。根据舰 约表示的具体形式不同，规约匹配主要可以分为接口规约( i n t e r f a c es p e c i f i c a t i o n ) 匹配和功能规约( e x p r e s s i o ns p e c i f i c a t i o n ) 匹配两类。 接口规约匹配也称为型构匹配( s i g n a t u r em a t c h i n g ) 。a m z a r e m s k i 在文献 6 7 1 中提出了型构匹配的两个层次。在第一个层次中，验证两个舰约是匹配的， 必须要求它们两者的接口中参数的个数和参数的类型是完全一样的，这是最严格 的一种型构匹配层次。在第二个层次中，验证两个舰约是匹配的，则只要求它们 两者的接口中的参数的个数是一样的，而对其参数的类型只要求是相容的( 例如 长整型参数和短整型参数就认为是相容的) 。这一层次的接口规约匹配比上一层 次的匹配降低了对接口参数类型匹配的要求。 在实践应用中，型构匹配的查全率较高，但查准率较低。所以它一般被用作 构件检索中的前置过滤手段以达到对构件进行粗选的目的。在它的后端一般要进 行更复杂的功能规约匹配以进一步提高检索的查准率。 对于功能舰约匹配，a m z a r e m s k i 在文献f 2 3 】中做了较系统的阐述。文中提 出从两种视角来看待功能舰约，并阐述了在这两种视角下具体的功能规约匹配技 术。 文t 1 、提： ；的筇一个观角是将个功能规约分成i 请配条件和后置条件两个部 分。功能规约s 的6 u 置条件记为s p 。，后胃条件记为s 。用户查询的功能舰约 q 的前胃条件记为0 p 。，后置条件记为qp o s l 。如果满足：s p r e # q p r c s p 0 s 。一q p 【。， 那么就认为s 和q 是精确前后置条件匹配的。但是如果只是满足：s l , 。, s t q p 0 。 则可认为s 和q 是一种放宽条件下的前后馒条件匹配。 文中提出的第二个视角是将一个功能舰约s 看成一个s p r 。一s 谓词结构。 如果构件的功能舰约s 和用户查询的功能规约q 满足： ( s ，。一s ) 一( q 。一q ，。) 则认为是s 和q 是精确谓词匹配的。如果只是满 鹕1 二母陶f f f = 3 ：索救卡慨f e 足：( s 。一s 口。) j ( o q 州) 或者( s p 。s 州) # ( q ”一q 州) 则可认为s 和o 是一种放宽条件下的谓词匹配。 由于基于舰约匹配的构件检索能够提供层次丰富的规约匹配类型，所以能够 较好的满足用户对构件检索查准率和查全率的综合要求。但是，基于规约的检索 同时也给用户带来了书写舰约的额外负担( 特别是在构件的功能比较复杂时) 。 并且，目前还没有什么实践上的成果可以从自然语占自动生成形式化规约，所以， 基于规约匹配的构件检索技术的普及和推广还有待时只。 2 3 基于编目语言的构件检索技术 这类检索技术所基于的构件描述方法是传统的图书馆和信息科学中的编目 分类方法。一般是由一组关键词( 也叫术语) 来描述一个构件o ( 这些术语一 般是从构件a 的说明手册中抽取出来的) 。为了实现松弛匹配，每个关键词t j 都 有一个对应的描述权重w g j ，描述权重用来表示该关键词在当的构件库中描述该 构件的时所具有的重要性。 用户在进行构件检索时，一般先输入与要查找的构件有关的若干个关键词， 将其汜为q 。构件检索系统将q 与构件库中每一个构件的编目描述进行匹配， 每一次匹配返回一个数值，它表示两者之间的匹配程度，一般称为相似度。最后， 检索系统将匹配相似度大于一定值的所有构件，作为本次检索的结果集合反馈给 查询用户。 从上面的检索过程，可以看出对术语描述权重w k 。的赋值以及对相似度计算 的准确性将决定整个检索算法的有效性。 对于术语描述权重w k j 的赋值，目前还是沿用图书馆和信息科学中的定义方 法【2 4 】，定义： u ，l o g f 里j n j 表示构件库中陶件的总数； n j 表示构件库中使用术语“描述的构件的总数； 表示术语t j 在构件g 的晚明手册中的出现频数 f 表示构件库中所用到的构件描述术语的总数日： 对于十h 似度的计算方法，目前也已经提出了许多汁算相似度的方法。j 三要介 绍以下三种方法，它们分别应用到了传统1 r ( i n f o r m a t i o nr e t r i e v a l 信息检索) 第一常构件愉索 盘卡慨沦 方法、神经网络和模糊数学的思想： 首先介绍利用传统的图书馆和信息科学中的激活扩散思想来进行构件检索 的方法。该方法最先由s c o t th e n n i n g e r 在文献 2 6 】提出。它的思想可以通过以下 的检索示例来阐述： 设构件库中存在图2 - 1 中的四个构件( 用方框表示) ，每一个构件用与之相连 的术语( 用椭圆表示) 来编目描述，该术语对该构件的表示权重标示在两者相连 的直线上。例如构件v m q u i t 的描述术语有q u i t 和r e m o v e ，它们相应的描述权 重分别为：0 3 0 8 和0 4 9 9 。 假设用户输入的查询术语为d e l e t e ，那么沿着图中的连线，它将以一定的活 性值( 活性值的具体大小由对应的w k , ，经过一系列的计算得到) 束激活构件 v m d e l e t e m e s s a g e 、构件r e m a i l d e l e t e f o r w o r d 和构件g n u s k i l l 。 由于构件v m d e l e t e m e s s a g e 被激活，那么它将其活性值沿有关的连线继续传 递( 传递的过程中将根据连线上的w k ，对活性值进行修正) 下去，于是激活了术 语m e s s a g e 和r e m o v e 。 又由于术语r e m o v e 的激活，r e m o v e 又将其活性值继续地沿有关的连线传递 下去，于是又将构件v m q u i t 激活。如此循环往复，将活性值不断地传递丌去。 由于在传递过程中，对活性值的修f 是衰减式的，当一个构件( 或术语) 的 活性值小于一定值时，陔活性值将不再被传递下去。当所有的活性值都不再被传 递下去的时候，检索系统将所有被激活的构件作为本次查询的结果集合反馈给用 户。 f v m - q u i tv m - d e l e t e m e s s a g e r e m a i l - d e l e t e - f o r w o r dg i l u s k i t e n j ：q u i tn _ ：m e s s a g e t e r t n s ：d e l e t et e r m s ：d e l e t e d e l e t er e m m em p 2 e i 刳2 1 ：活性传动技术在构什检索中的麻川 上述介绍的激活扩散( s p r e a d i n g a c t i v a t i o n ) 的方法在一般的文本检索r 扣已 获得成功的应用，在构件检索中正在逐步尝试使用。但它的激活扩散对术语问的 关系考虑不够，这是陔方法在构件捡索时导致查准率较低的一个主要原因。 捕_ 二靠 j 件m 索披长慨论 其次要介绍的是将神经网络思想用于构件检索。m a g w o l f d i e t e r m e r k l 在他的 博士论文【2 5 1 中首次提出了将构件库中的所有构件在逻辑上组织成一个自组织 神经网络的思想。 用户的查询术语集合通过系统首先转化为一个输入矢量，然后将该矢量输入 进浚神经网络，通过竞争后，在网络的输出层得到一个优胜的节点( 该网络输出 层的节点与构件库中的构件在逻辑上具有对应关系) ，最后将该优胜节点以及其 一定领域范围内的所有节点所对应的构件作为本次检索所得到的结果反馈给用 户。 神经网络方法的技术关键在于网络的学习算法与竞争算法，它们的设计参见 文献f 2 5 1 。浚项技术最大的优点在于它可以通过竞争学习，自组织地将构件按语 义相关性进行逻辑上的组织，以方便构件的检索。 但是，目前神经网络在构件检索中的应用，要求输入矢量的维数是固定的。 矢量的维数一旦发生变化，那么原先的学习算法与竞争算法都需要重新设计。这 个弱点决定了神经网络技术不能作为那些描述经常发生变化的构件库的检索技 术。 最后要介绍的是模糊数学的思想在构件俭索中的应用。e d a m i a n i 在论文 2 5 1 中首次提出了应用模糊数学计算匹配相似度的方法。该方法要求用户在输入 检索术语的同时还提供该术语对本次检索的重要程度的信息( 模糊数学中称为隶 属度) 。检索的主要步骤为：首先将描述权重w k 4 理解为术语t j 对构件g 的模糊 隶属度，然后利用模糊数学中的计算公式求出用户输入的查询信息与构件描述之 间的模糊匹配值。并将所有与查询信息的模糊匹配值大于一定数值的构件作为检 索结果反馈给用户。文中还提出了根据用户的反馈信息对模糊匹配值的计算参数 进行自适应调节的方法，并给出了实验数据加以佐证。 模糊数学的思想很适合构件检索对匹配松弛能力的要求。但是它的有效性关 键在于计算模糊匹配值时公式参数的确定，目i j i 这些参数的确定方法还只有实验 卜的证实它还等待着胖论 = 的证明。 2 4 小结 通过对七述几种比较常用的构件检索方法概述，可以知道：第，何一种方 法都有它具体针对的构件表示形式。但是构件的刻面表示作为目i m 证广为使厢的 一种主要n 勺构件表示彤式，却还没有号门为它量身定裁的构件检索方法，它的捡 索方法基本e 还是沿刷r u b 6 np r i e t o d i a z 等人在他1 9 8 7 年的i 2 5 c 1 5 1 中提出的 以传统的数据库检索技术为主，结合同义词词典和刻面术语问的一般一特殊关系 弛一蒂蜘仆伶索披长溉论 束实现构件检索的方法。在软件复用实践不断普及与深入的今天，这种方法正在 面临越来越严峻的考验。第二，构件的检索方法要求很强的松弛匹配能力，在这 一点上，上述介绍的各种方法可谓竭思尽虑，引用了从传统i r 方法到形式化方 法、神经网络、模糊数学等各个领域的知i = ，并且在引用的过程中进行了缜密的 考虑与合适的修改。这提示我们，针对构件的刻面表示，要使得其检索方法具有 适于复用的松弛匹配能力，必须慎重考虑，不能简单的照搬套用。 在这篇论文中，我们将针对构件的刻面表示形式提出一种新的构件检索方 法，其中将用到树匹配领域中的有关的概念与知识。所以在下一章，将先介绍树 匹配领域中有关的基础知识。 一笙生苎坐唑 第三章基础知识 本章先介绍树匹配领域中有关的基本概念。其中编辑操作、映射和编辑代价 是最重要的三个概念。同时，本章还提出了两个重要的概念：亲和度和映射谱。 最后介绍了树匹配领域中几个重要的研究命题及其研究现状。 3 1 基本概念 树是图的一种特例，一殷用r 表示：丁= f v e r o o t ( t ) j ，有时电简记为7 1 = f 旺) 。 其中矿表示一个有限的节点集( 在不引起混淆的情况下，也可以用r 直接来表示 | ；c 的节点集、，r o o t ( t ) 表示树的根节点，e 表示边集，它是y 上的一个二元关系， 它满足反自反、反对称、可传递性。如果似一，则称“节点是v 节点的父节 点，记为u = p a r e n t ( v ) 或v = c h i l d ( u ) ，“节点的所有儿子节点组成的集合记为c “f j 。 一棵树必须满足以下三个条件。 1 根节点r o o f ( t ) 不存在父节点； 2 除根节点外，y 中其他节点都有且仅有一个父常点： 3 树中每一个非根节点v v ，存在fr o o t ( d 、v ) e + ，其中+ 是e 的传递闭包。 如果两个节点v ，也，有一，v 2 ) + ，则称v ，是垤的祖先节点，记为 v i = a n c e s t o r t v 2 ) 或f 2 = d e s c e n d a n t ( v ，) 。将所有“节点的祖先节点组成的节点集合 记为a n f j ，所有“节点的子孙节点组成的节点集合记为d f f f j 。设“v ，则7 中 以u 为根节点的子树记为t 【“】- ( y ：e ：“) ，有： v = f “，t _ j d ( u ，a n d e = e n f v v j 。 如果两个节点v 。v ，之间没有 且先后代关系，则用本文下面提出的亲和度的概 念束描述v ，f 2 之问的关系。为了引入亲和度的概念先介绍宗祖的概念。 定义3 1 ( 宗祖) ：r = r v 司，设v ，v ，y f v ，v ，j 隹+ r v 。v ，豇+ ，则定义集 合a ，为也的宗祖，a = 七i 口= a n c e s t o r ( v ，j d = a n c e s t o r ( v 2 ，j 。 山上面的定义知道，两个没有诅先后代关系的节点的宗甜l 足指这两个节点的 所仃共同祖先节点的集合。 定义3 2 ( 亲和度) ：7 1 = f v 毋，设v ，v ，yaf v f ，v ，j 隹e + ar v ，v ，j 硭+ ，则定 义r ( v ，也) 为v i ，也的亲和度：月( 1 2 h v 2 ) = i a 。，1 ，其中i 1 表示集合的势。 山 二面的定义知道，两个没有讯先后代关系的常点的亲和度是指这两个节点 的所仃共同祖先宵点的个数。 值得注意的是：亲和度只是两个无 且先后辈关系的肖点之间关系的一个简， 的度量，它的值只有在存在共同祖先节点时j 有意义，否则是无意义的。例如： 第l i 贝 堡三垦堡塑 如果r ( v ，比) r ( v ，) 时，可以认为v 2 与v ，的关系比v 3 与v l 的关系要近，但如 果r ( v h v 曲 r ( v 3 , v 4 ) 时，则不可以认为v 2 与v j 的关系比v 3 与的关系要近，因 为这时还要考虑节点的深度，单纯的依靠亲和度值是不能下结论的。 如果将树的每一个节点对应一个标签，这样的树称为标签树，用l a b e l ( v ) 表示 节点v 上的标签。如果树中兄弟节点的顺序是有意义的，这样的树称为有序树， 否则称为无序树，在后文中出现的树，如果不作说明，一律认为是无序的标签树。 3 1 1 编辑操作和编辑序列 对一棵无序标签树，允许以下三种编辑操作 6 8 j ： c h a n g e ：改变一个节点的标签。即将一个节点的标签改变为另一个标签。下图 给出了一个将节点a 的标签改变为节点b 的标签的c h a n g e 操作的图示，丁为编 辑操作f i 的树，r7 为编辑操作后的树： 四灭 雩定。| 霉笼 i 堇| 3 t ：改变标签编辑操作_ 例 d e l e t e ：删除一个节点，意味着从树中除去该节点，并使该节点的孩子节点成为 该节点的父亲节点的新的孩子节点。下图给出了一个删除节点a 的d e l e t e 操作 的幽不，丁为编辑操作自i 的树，7 7 为编辑操作后的树： 众，弧 i 芏i3 - 2 ：删除节点编 f 操作小洲 值得一提的是：如果删除的是根节点，那么将得到一个森林。 i n s e r t ：插入一个声点，陔操作可以通过下图来说明，图中表示了在节点, 的f 方插入节点v 的操作，这使得节点v 成为节点“的孩子节点，并将节点“的原有 的孩子节点的一部分移作新节点v 的孩子节点。这一部分孩子符点究竟是哪一 部分，是在执行i n s e r t 操作时由具体的上下文环境来决定的。 箱1 2 贞 骑= 节坫枷知i f , 弧，众 ? r l j 幽3 - 3 ：插八节点编j t i 操作爪 设表示所有标签的集合，a ，是中的一个特殊标签，表示空。可以 将上述三种编辑操作简单的统一表示为：d b 口，b ，口，b 不能同时为a 。 当一a ，b a 时表示将节点的标签从a 改变到b ，当a a ，b = a 时表示将当前这 个标签为a 的节点删除，当a = ，b a 时表示插入一个标签为b 的节点。 例如图3 - 1 中的编辑操作就可以表示为：l a b e l ( aj l a b e l ( bj 。如果上下文 不引起混淆，也可以简记为：a b 。 需要注意的是：这种表示方法只表示了参与编辑操作的节点标签，但没有表 示出编辑操作的具体位置，所以晚它只是一种简单的统一表示方法。但是，这种 表示方法已足够用来定义下文的编辑代价。 定义3 3 ( 编辑序列) ：一个编辑序列s 。 o p ，o p 二，o t 7 ，k 为正整数，其中 叩，代表一个编辑操作，有0 1 ) ，一6 i 口，6 ，一f a 九，js i 女。 如果对一棵树r 作用了一个编辑序列s 使之转化为树r ，浚转化过程可以简 |