袁中臣^1,2, 马宗民¹
1. 东北大学 软件学院，辽宁 沈阳 110169;
2. 沈阳工业大学 化工过程自动化学院，辽宁 辽阳 111003
收稿日期：2018-12-20
基金项目：国家自然科学基金资助项目(61370075, 61772269)。
作者简介：袁中臣(1978-), 男, 辽宁辽阳人, 东北大学博士研究生，沈阳工业大学讲师;
马宗民(1965-), 男, 山东金乡人, 东北大学教授, 博士生导师。

摘要：以软件重用为背景提出基于语义和结构的UML类图检索.构建了UML类图的重用模型，定义了存储UML类图的重用库结构.提出将本体的概念语义距离应用到UML类图的语义相似性度量和使用图表示UML类图的结构进行结构相似性度量.基于检索流程形式化检索需求，提出了UML类图的检索算法.基于提出的衡量标准，从语义、结构和混合三种检索类型对提出的算法进行了验证.实验结果表明，所提出的检索算法在检索质量和检索效率上要优于其他方法.
关键词：UML类图语义结构相似性度量检索
Retrieval of UML Class Diagrams Based on Semantics and Structure
YUAN Zhong-chen^1,2, MA Zong-min¹
1. School of Software, Northeastern University, Shenyang 110169, China;
2. School of Chemical Process Automation, Shenyang University of Technology, Liaoyang 111003, China
Corresponding author: YUAN Zhong-chen, E-mail: yuanzhongchen@163.com.

Abstract: The UML class diagram retrieval based on semantics and structure was proposed under the background of software reuse. The reuse model of UML class diagram was constructed and the reuse repository structure of UML class diagram was defined. The conceptual semantic distance of ontology was applied to the semantic similarity measure of UML class diagram and a graph was used to represent the structure of UML class diagram for the structural similarity measure. The retrieval requirements were formalized based on the retrieval procedure and the retrieval algorithm of UML class diagram was proposed. The proposed algorithm was validated from three retrieval types(semantics, structure and hybrids) according to the proposed criteria. The experimental results showed that the proposed algorithm is superior to other methods in terms of both retrieval quality and efficiency.
Key words: UML class diagramsemanticsstructuresimilarity measureretrieval
随着软件复杂性的日益增强，对于软件重用的需求在不断增加.重用的内容也不再仅限于代码，而是涉及到软件生命周期的各个阶段^[1].实际上，软件开发过程中产生的任意产品都在重用范围之内，这种重用被视为软件工程师的知识和经验的重用.因为软件设计对接下来的开发阶段将产生重要的影响，所以软件设计的重用受到了关注.作为建模工具，UML类图被广泛地应用于设计阶段，已成为软件设计事实上的标准^[2]，所以UML类图的重用成为研究热点^[3-4].
随着语义web的发展，大量的本体被开发.本体是共享概念的明确而详细的说明，概念通过特定的关系建立联系^[5].本体分为通用本体和领域本体.通用本体覆盖了若干领域的概念知识，如WordNet；领域本体是由来自单个领域的概念构成的，如基因组学领域的基因本体(gene ontology，GO)等.本体为概念之间的相似性度量提供了途径.例如，在WordNet中提供了基于路径和信息共享两种方法来衡量概念之间的相似性^[6].相似性度量被广泛应用于分类、聚类和检索等.在软件产品的重用过程中，检索是核心工作，检索是基于相似性.UML类图所呈现的信息包含语义和结构，类、属性和操作属于语义范畴；UML类图的结构通过类之间的关系来表达，类之间的关系包含不同的类型(关联、泛化、聚合、组合、依赖和实现).所以，UML类图的相似性度量既包含语义相似性也包括结构相似性.
现有的基于重用的类图检索可以归结为两种策略.第一种是基于语义的匹配^[7]，类图之间的相似性是通过语义相似性来衡量.其中，类图的关系被定义为向量R=[端点类1，关系类型，端点类2]，关系的相似性通过向量R的差异或距离来度量.第二种是基于模型查询语言^[8]，解析类图元素并基于模型查询语言重写类图，并提出模式匹配方法.
第一种策略仅仅考虑了语义，而没有考虑结构.即使考虑了概念之间关系，本质上也是语义匹配，在仅考虑类图的结构而不考虑语义的检索要求时，这种策略不能很好地工作.实际上，结构对于一个UML类图是非常重要的.在使用UML模型化一个系统时，首要考虑的是系统的结构而不是单个类.第二种策略虽然考虑了结构，但元素匹配是基于关键字而不是基于语义，没有考虑检索结果的非精确性.最后，两种方法都没有对检索条件给出一种形式化的定义.实际上，检索需求经常是复杂的，通常不仅仅是一个简单的类或类图，这就需要一个检索条件的明确表达.同时，每个检索元素在检索条件中的权重应该被考虑，因为类图中的不同元素在模型化一个系统时的重要程度不同.
本文正是基于语义和结构两个方面实现对类图的检索，定义了语义相似性和结构相似性度量方法.基于检索流程，形式化地定义了检索表达，并提出了检索算法.实验验证了所提算法的有效性.
1 UML类图及其重用模型1.1 UML类图UML类图是由类和类之间的关系两部分构成.图 1是类图的一个样例，表示类“Professor”继承类“Teacher”.
图 1(Fig. 1)

图 1 UML类图样例Fig.1 A sample of UML class diagram

一系列工具能被用来编辑UML类图，如Rose和MyEclipse等.对象管理组织(object management group，OMG)为所有UML模型定义了文档类型定义(document type definition，DTD)标准^[9]，UML模型被描述为遵守DTD的基于XML元数据交换(XML-based metadata interchange，XMI)文档.
1.2 重用模型UML类图的重用模型被描述为一个过程，如图 2所示.这一过程包含4个阶段，分别是类图的检索、候选类图返回、候选类图调整并应用到新项目和新类图被抽取并加入到重用库.在这几个阶段中，检索是关键，决定着重用质量和效率.重用库存储大量的可重用类图，重用库的有效管理和组织对于提高检索效率也是非常重要的.重用库中的类图被分为“域”和“目录”两级，如图 3所示.
图 2(Fig. 2)

图 2 UML类图重用模型Fig.2 Reuse model of UML class diagrams

图 3(Fig. 3)

图 3 重用库结构Fig.3 Structure of reuse repository

建模不同领域项目的UML类图cd_i被分类到不同的域，如D₁, D₂, …, D_n.在一个域内，类图又被划分为多个结构目录，如在D₁中的C₁, C₂, …, C_m.结构相同或者相近的类图被分类到相同的目录.在每个域内定义一个特征概念集合，在每个目录中定义一个特征结构集合.特征概念和特征结构的选取是基于其所在域和目录的重用次数和出现频率.f_c(D_i)和f_s(C_jⁱ)分别标记域D_i的特征概念集合和域D_i中结构目录C_j的特征结构集合.
2 相似性度量2.1 语义相似性现有的语义相似性能被归结为同一类，就是基于本体来计算两个概念的语义相似性.本文选择被广泛使用的基于本体路径语义距离来计算UML类图概念之间的语义相似性.在本文中，除了类，属性和方法也被认为在语义范畴内，所以类图之间的语义相似性为
式中：cd₁和cd₂是两个类图；类C_i来自类图cd₁，A_i和O_i分别是类C_i的属性集合和操作集合；同理，类C_j来自类图cd₂；A_j和O_j分别是类C_j的属性集合和操作集合；C_i被匹配到C_j，A_i被匹配到A_j, Q_i被匹配到Q_j；SimC，SimA和SimO分别表示类相似性、属性相似性和操作相似性.在计算属性和操作相似性时，除了考虑概念语义还考虑到属性的类型和操作的返回值类型.类图之间的语义相似性实际上就是类图概念元素之间的相似性.这里仅计算平均相似性，|cd_i|表示类图cd_i中包含的类的数目；α，β和γ是权重因子，且α+β+γ=1.
2.2 结构相似性由于UML类图的半形式化，图和UML类图两种模型在结构上的相似性(类对应于顶点，关系对应于边)，本文提出采用图来表示UML类图的结构，目的是进行结构相似性度量.UML类图中的类被转换成图的顶点，UML类图中的关联、泛化、聚合、组合、依赖和实现等关系被转换成边，并分别被标记为e₁, e₂, e₃, e₄, e₅和e₆.这样类图之间的结构相似性就被转换成对应的两个图的相似性.两个图之间的结构相似性可以通过最大公共子图(maximum common subgraph，MCS)度量^[10].公式为
其中：N_MCS表示存在于MCS中的边的数目；|g_i|是表示图g_i中边的数目.
当然，这里求解最大公共子图是基于边，而不是顶点，并且边的匹配是基于上面所述的标记.求解最大公共子图的算法见算法1.
算法1 ??搜索图g₁和g₂之间的最大公共子图
输入：图g₁和g₂
输出:最大公共子图(MCS)
1.初始化状态空间S=NULL;
2. //在g₁中与S相连的下一条边e_k
while(nextEdge(g₁, S, e_k)) do
3. begin
4. //e_k是否使得g₁和g₂的公共子图尺寸增加
if(IsFeasible(g₁, g₂, S, e_k)) then
5. begin //更新公共子图
6. S=S+e_k; //更新状态
7. if(size(S)>z)then
8. z=size(S); //更新尺寸
9. end;
10. else //退回S的上一个状态
11. backState(S);
12. end;
13. return S;
算法执行了一个深度优先搜索.S是一个状态空间，用于存储图g₁和g₂之间的公共子图.S的尺寸会随着更多边的加入而变大直至最后形成最大公共子图.
3 类图检索3.1 检索流程UML类图的检索过程描述如图 4所示.用户首先输入检索需求，用户的输入可以是单个类(属性和操作)，也可以是类图结构.解析是从检索要求获取检索元素，任何基于SAX(simple API for XML)的工具能被用来解析XMI文档^[11].检索需求经常是复杂的，包含着用户的多种意愿，所以将检索需求转换成一个形式化表述，作为检索算法的输入.检索算法是核心，这里提到的检索应该是非精确的，目的是发现最贴近检索需求的候选类图序列.
图 4(Fig. 4)

图 4 UML类图检索流程Fig.4 Retrieval procedure of UML class diagrams

3.2 检索表达在输入检索需求时，经常会有如下几种情况：
1) 希望几个检索元素在候选类图中同时出现.可以被表达为
2) 希望在候选类图中某些元素部分出现或者同时出现.可以被表述为
3) 希望有些检索元素在候选类图中不要出现.可以被表述为
所以，综合上述几种情况，检索需求能被形式化地描述如下：
其中：e_i和e_i′为检索条件中的概念元素，它是类C_i，也包含类的属性A_ij或者操作O_ij；s_i和s′_i为结构元素；e″_p为不能出现在候选类图中的概念元素；s″_q为不能出现的结构元素.
3.3 检索算法一般情况下，在类图的检索中，候选类图不一定完全满足检索需求.这里设定一个阈值σ，当检索元素被匹配到重用库中的类图所取得的相似性值大于σ时，重用库中的类图即被列为候选类图.因为不同的元素(概念和结构)在模型化一个系统时具有不同的重要程度，所以不同的检索元素在检索条件中被分别赋予权重，W=[w₁, w₂, …, w_n].类图的检索算法被描述为算法2.
算法2 ??类图的检索算法
输入：检索表达UCD_QS，W和重用库L
输出：候选类图序列
1. //初始化目标类图所在域、目录和候选类图序列
2. //获取检索元素
classElements=getClass(UCD_QS); //概念元素
noClassElements=getNoClass(UCD_QS);
strucElements=getStructures(UCD_QS); //结构元素
noStrucElements=getNoStructures(UCD_QS);
3. //赋予权重
assignWeight(classElements, strucElements, W);
4. //候选类图所在的域
if(classElements!=NULL) then
5. for each D_i in L do
6. begin
7. FC_i=getFeatClass(D_i); //获取特征概念
8. SimD_i=SimCS(classElements，FC_i); //域相似性
9. end;
10. SimD_x=max(SimD);
11. d=D_x;
12. //候选类图所在的目录
if(strucElements!=NULL) then
13. for each C_i in d do
14. begin
15. FS_i=getFeatStrucs(C_i); //获取特征结构
16. SimC_i=SimSS(strucElements，FS_i); //目录相似性
17. end;
18. SimC_y=max(SimC);
19. c=C_y;
20. //计算类图相似性，并插入候选序列
for each cd_k in c do
21. if(μ*SimCS(classElements, cd_k)+(1-μ) *
SimSS(strucElements, cd_k)>σ) then
22. insertCD(cd_{k, l});
23. //删除不期望包含元素的类图
for each e_i from noClassElements and each s_i from noStrucElements do
24. for each cd_q in l do
25. if(e_i or s_i) in cd_q then
26. deleteCD(cd_q, l);
27. return l; //返回候选类图序列
在检索算法中，基于定义的特征概念和特征结构，通过相似性计算分别决定候选类图所在的域和目录，这样能过滤掉大量的类图，大大提高检索的效率.检索元素被匹配到已经确定目录内的每个目标类图并计算相似性，当相似性的值高于指定阈值σ，目标类图被插入候选序列.最后，从候选序列中删除不期望的元素所在类图.μ为相似性权重，在应用中可以根据检索需求进行调整.
4 实验使用Java语言实现了本文所提出的检索算法，并且在PC机(Win 10, Intel Core i7, RAM 8GB)上执行.实验中使用的类图来自3个领域，分别为教育、医疗和房地产，每个类图中类的数目在15~25之间.所有类图均来自公司已经开发的项目，每个领域的类图、目录、特征概念以及每个目录包含的特征结构数量如表 1所示.
表 1(Table 1)

表 1 重用库中 UML 类图Table 1 UML class diagrams in reuse repository 领域 类图 目录 特征概念 特征结构 教育 100 4 15 4, 5, 5, 4 医疗 100 5 18 4, 4, 4, 3, 3 房地产 100 4 16 5, 4, 3, 4

表 1 重用库中 UML 类图 Table 1 UML class diagrams in reuse repository

本文做三种检索类型(概念、结构和混合)操作，如表 2所示.每种检索类型操作基于不同领域元素被执行3次，检索条件的设定主要从检索元素数量和分布考虑.
表 2(Table 2)

表 2 检索条件设定Table 2 Retrieval conditions setting 检索类型 概念 结构 Q1 8(3) 0 Q2 0 5(2) Q3 6(2) 3(1) ??注：括号中数字表示不允许出现在候选列表中的概念或结构的数量.

表 2 检索条件设定 Table 2 Retrieval conditions setting

提出的检索算法和其他方法(语义检索^[6]和模型语言检索^[8])进行比较，本文提出的检索方法被称为二级检索，主要从检索质量和检索效率两个方面进行比较.参数设置α=0.5, β=0.25, γ=0.25, σ=0.5.在三种检索方法中，相似性计算权重μ分别被设定为1.0，0和0.5.检索元素权重设定为平均权重.
衡量检索质量可以从查准率P、查全率R和二者调和平均值F三个指标来度量^[12].这里设定A表示正确地出现在查询结果中候选类图的数量；B表示错误地出现在查询结果中候选类图的数量；C表示应该出现但没有出现在检索结果中的类图数量.P，R和F计算公式为
平均查准率P、查全率R和调和平均值F的对比分别如图 5，图 6和图 7所示.可以看出，三种检索方法查准率差别不大，如图 5所示.但查全率出现较大差别，特别是结构和混合检索，如图 6所示.综合来看，对于概念检索(Q₁)，三种检索方法呈现的结果差别不大；而对于结构检索(Q₂)，本文提出算法和模型语言检索得出的结果要明显优于语义检索；对于混合检索(Q₃)，本文提出的算法的检索结果要优于其他两种方法，如图 7所示.原因是本文的检索算法同时考虑了语义和结构，而其他两种方法存在片面性.
图 5(Fig. 5)

图 5 查准率比较Fig.5 Comparison of precision ratios

图 6(Fig. 6)

图 6 查全率比较Fig.6 Comparison of recalls

图 7(Fig. 7)

图 7 调和均值比较Fig.7 Comparison of harmonic means

检索效率是指执行检索的响应时间.三种检索方法分别在不同检索类型数据上执行检索所需的响应时间如图 8所示.
图 8(Fig. 8)

图 8 检索时间比较Fig.8 Comparison of retrieval time

可见，对于每种检索类型，本文算法的检索响应时间要少于其他两种方法.类图检索的响应时间主要取决检索元素和重用库中目标类图匹配的次数.本文提出的算法的匹配次数决定于重用库中域的数、候选类图所在域包含的结构目录数以及候选类图所在结构目录包含的类图数，所以匹配次数要远远少于其他两种方法.关于重用库中类图分类的这部分内容将会在接下来的工作中讨论.
所以，无论从检索质量还是从检索效率上，本文提出的算法都是可行的并且要优于其他两种方法.由于特征概念和特征结构的引入，算法对数据量越大的存储库检索表现越好.
5 结语本文基于软件重用从语义和结构两个方面提出对UML类图的检索.通过本体和图的引入，分别提出了类图之间语义相似性和结构相似性度量方法.基于检索流程，提出了类图的检索算法.实验结果表明，本文提出的算法在语义、结构和混合三种检索类型都获得较好的检索质量，特别是对结构和混合检索，与其他检索方法相比具有明显的优势.同时，本文提出的算法的检索效率也是可以接受的，并且优于其他两种方法.
参考文献

[1]	Frakes W B, Kang K. Software reuse research:status and future[J]. IEEE Transactions on Software Engineering, 2005, 31(7): 529-536. DOI:10.1109/TSE.2005.85
[2]	Medvidovic N, Rosenblum D S, Redmiles D F, et al. Modeling software architectures in the unified modeling language[J]. ACM Transactions on Software Engineering and Methodology(TOSEM), 2002, 11(1): 2-57. DOI:10.1145/504087.504088
[3]	Adamu A, Zainon W M N W. A review of UML model retrieval approaches[J]. Indian Journal of Science and Technology, 2016, 9(46): 1-8.
[4]	Salami H O, Ahmed M A. UML artifacts reuse:state of the art[J]. The International Journal of Soft Computing and Software Engineering(JSCSE), 2013, 3(3): 115-122.
[5]	Antoniou G, Van Harmelen F.Web ontology language: OWL[M]//Handbook on ontologies.Berlin: Springer, 2004: 67-92.
[6]	Meng L, Huang R, Gu J. A review of semantic similarity measures in wordnet[J]. International Journal of Hybrid Information Technology, 2013, 6(1): 1-12.
[7]	Robles K, Fraga A, Morato J, et al. Towards an ontology-based retrieval of UML class diagrams[J]. Information and Software Technology, 2012, 54(1): 72-86.
[8]	Zhang X, Chen H, Zhang T.An UML model query method based on structure pattern matching[C]//International Conference on Trustworthy Computing and Services.Berlin: Springer, 2012: 506-513. http://link.springer.com/chapter/10.1007/978-3-642-35795-4_64
[9]	Routledge N, Bird L, Goodchild A.UML and XML schema[C]//Australian Computer Science Communications.Melbourne: Australian Computer Society Inc, 2002: 157-166.
[10]	Raymond J W, Gardiner E J, Willett P. Rascal:calculation of graph similarity using maximum common edge subgraphs[J]. The Computer Journal, 2002, 45(6): 631-644. DOI:10.1093/comjnl/45.6.631
[11]	Grose T J, Doney G C, Brodsky S A. Mastering XMI:Java programming with XMI, XML and UML[M]. New York: John Wiley & Sons, 2002.
[12]	Yang Y. An evaluation of statistical approaches to text categorization[J]. Information Retrieval, 1999, 1(1/2): 69-90. DOI:10.1023/A:1009982220290