基于相似度计算的UML图匹配算法设计模式检测技术研究

魏金津 任女尔 蔡建军

摘要：现在软件项目越来越庞大，历史项目也因文档缺失，结构不清晰等原因很难被开发者理解。为了能让软件开发者深入了解系统结构，增强开发者软件重构、复用的能力，我们研发设计模式检测技术并作为插件集成进SonarQube，和代码质量检测、代码克隆检测、解耦检测等一起作为技术债务进行管理，对软件开发过程具有重要的工程意义与实践指导作用。

关键词：UML图 图论；设计模式检测；相似度算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）28-0165-03

1 概述

现在汽车行业软件系统越来越复杂庞大，识别系统所用到的设计模式对于软件设计者理解系统架构非常重要，为进一步改进系统结构，软件复用提供基础。普通的设计模式检测算法只能识别基本模式而不能识别基本模式上的改进模式，并且系统过于庞大时效率也不高，使用相似度算法可以识别改进模式并且提高效率。

软件行业内常将Sonar作为技术债务【1】管控的主流工具，Sonar插件式模式，方便自身被其他平台所引入，且有利于扩展第三方插件。我们可以开发插件对检测结果进行再加工处理，除了增强代码质量检测粒度，还可以在设计上对代码进行设计模式、解耦等检测。

自动检测系统设计模式的过程叫作设计模式检测，是从设计级别检测软件质量，实现基于Sonar的设计模式自动检测技术，有利于软件开发与设计人员理解系统设计，指导软件项目设计改进。

系统类之间的关系可以由UML类图表示，类图本质上是有向图，可以对应到邻接矩阵。我们基于相似度计算的UML图匹配算法研发设计模式检测技术，计算待检测系统和设计模式所表示矩阵的相似度，生成检测到的模式实例的列表。

我们将设计模式检测软件以插件的形式集成到SonarQube中，与其他技术债务一起进行扫描，并将实时测试结果反映给开发人员，从而提高系统设计的质量。

2 图论和UML图

图（Graph）可以定义为一组称为顶点（vertex）的对象，由称为边（edge）的鏈接所连接。图几乎可以用来表现所有类型的结构和系统，从交通、通信网络，社交、生物网络到计算机科学中都有广阔的用武之地。

图论（Graph Theory）【2】是数学的一个分支，主要研究图的属性，对图形属性的研究对于理解底层软件系统的特性在许多方面都很有价值。

面向对象系统使用类作为模块分析，设计和实现系统，其体系结构可以由一个或多个UML图所表示。

UML（Unified Model Language） 【3】，中文叫作统一建模语言，可以用来对面向对象系统进行可视化的说明、描述。包括用例图、类图、对象图、序列图、协作图等等，其中最常见的是类图，UML类图不仅可以对系统中所有类的属性和方法进行描述，最重要的是能描述类之间的关系，常见的有依赖、泛化、关联、聚合、组合、实现等关系。

UML类图可以完美地映射到图论的图，图的顶点（vertice）代表类，边（edge）可以对应到关联、泛化、组合等UML类图关系。

有向图G=（V， E）可以表示面向对象系统的类图，顶点集（V）对应于系统中的所有类集合，边集（E）对应于这些类之间关系的集合，比如有向边（p， q）∈E表示类p与q的关联关系方向是从p到q。类的所有关系（包括泛化、关联、组合）都可以表示成类图，下图是张简单的类图：

我们可以用矩阵来完全地描述任何有向图，这就是有向图的邻接矩阵，如下图：

3 设计模式检测

设计模式（Design Pattern）是特定情境下特定问题的一般解决方案。使用设计模式，可以建立一个结构良好、可维护和可重用的软件系统。现在汽车行业的软件系统架构非常复杂并且包含大量的组件，历史项目也因文档不齐以及结构不清晰等问题，很难理解这些系统的软件结构。设计模式检测【4】有益于理解这些系统的设计，并为进一步的改进提供基础。

在设计模式检测之前，我们需要对待检测系统和设计模式结构进行建模，因为类图是一种可以被完美映射到矩阵的有向图，并且对矩阵的操纵也很容易，所以我们选择矩阵对面向对象设计的类之间的关系进行建模。

GoF提出了23种经典的设计模式，如观察者模式，代理模式，单例模式，抽象工厂模式等等，这些基本设计模式都有其基本结构，但是在实际软件开发中，设计模式并不经常遵循于基本结构（有时还会定义自己的设计模式），可以称为改进型设计模式。所以我们引入基于相似度计算的UML图匹配算法（Graph Similarity Algorithm），将待检测系统和模式图作为输入以计算其邻接矩阵的相似度得分。这种方式的主要优势是不仅能检测基本设计模式还能检测在基本设计模式上改进过的设计模式。

要表示的系统实体的关系或属性取决于设计者想检测的模式的具体特征，我们想表示的有关联，泛化，抽象类，抽象方法调用，对象创建。然而相似度算法并不取决于所使用的特定类型的矩阵，只要能将系统或模式描述为矩阵设计者可以将输入参数设为任何类型。

我们使用Java语言开发了一个检测程序，使用前需要选择待检测系统的classes文件根路径和待检测的设计模式，便可自动化的使用上面提到的设计模式检测算法（下面会说明），生成检测到的模式实例的列表。该检测程序以Sonar插件形式开发并集成进SonarQube和代码质量、代码克隆等技术债务一起进行扫描检测。

4 计算两图之间的相似度算法

1）两个有向图GA和GB分别具有NA和NB顶点，GA描述设计模式，GB描述系统。定义相似度矩阵S为一个NB*NA矩阵。S的每个元素s（i，j）表示的是GB中顶点i和GA中顶点j的相似度。

2）计算S的算法公式如下：

（1） 设Z0为一个元素均为1的NB*NA矩阵。

（2） 迭代：[Ζk+1=BZkAT+BTZkA∥BZkAT+BTZkA∥1]

其中，有向图GA、GB的邻接矩阵表示为A、B；分母表示矩阵的1-范式（矩阵的1范数，即：矩阵的每一列上的元素绝对值先求和，再从中取个最大的，（列和最大））；迭代的终止条件是矩阵Z收敛。[knAnBeAnA+eBnB]

3）算法复杂度：ea、eb代表的是有向图的边的数量。

4）选择该算法的原因：在设计模式检测的情景下，这个图相似度计算算法，可以用来检测图GA和图GB的顶点之间的相似度。为了保证最后检测结果的准确性，最后将矩阵归一化来表示相似度（相似度取值范围[0，1]）。

5 图匹配算法

精确图匹配算法（Exact Graph Matching Algorithm）：该算法就是寻找同构图，即具有相同节点数，相关边缘也要一一对应的图。两个同构的图其邻接矩阵也相同。运用设计模式检测，就是检测系统图的所有和待检测模式具有相同数量顶点的子图。这是理想状态下的算法，在实际软件开发中，完全复制设计模式是不现实的，总要根据实际情况来进行修改适应，所以精确图匹配算法在设计模式检测领域并不适用。

非精确图匹配算法（Inexact Graph Matching Algorithm）：当无法找到两个图之间的同构时可以应用模糊匹配，即非精确图匹配算法。该算法通过图的编辑距离来计算图与图之间的相似程度。图的编辑距离，大致可以理解为对匹配图进行多少次点、边的操作可以与目标图一致。在设计模式匹配场景下，检测结果将不准确，如图4。

SS1明显是SS3设计模式的一种变种，但是编辑距离来讲，SS2更小。

相似度算法（Similarity Scoring Algorithm）：以上两种算法都不适用，所以我们使用基于相似度计算的UML图匹配算法，该算法计算图的邻接矩阵的相似度。将UML图拆分为泛化图（Generalization Graph）和关联图（Association Graph），以下简称g图和a图。g图表示各类之间的继承关系，a图展示的是各类之间的聚集关系（如类A中有一个B类的实体，此时，a图中A指向B）。

首先将上面图3的UML按照a圖和g图拆分开来：

然后分别计算出他们的邻接矩阵：

之后将这个矩阵代入到1中的算法公式中，分别迭代获得两个片段的a/g图对于待测设计模式的a/g图的相似度：

[Genpattern，seg1=Similarity（Genpattern，Genseg1）=0.500.50.500.5]

[Assocpattern，seg1=Similarity（Assocpattern，Assocseg1）=100001]

[Genpattern，seg2=Similarity（Genpattern，Genseg2）=1001]

[Assocpattern，seg2=Similarity（Assocpattern，Assocseg2）=0000]

之后分别将每个片段的两个相似度矩阵进行相加，并且进行归一化，可以得到最终的相似度矩阵：

[NormScorespattern，seg2=Sumpattern，seg2?1k1001k2=1001?120012=0.5000.5]

[NormScorespattern，seg1=（Genpattern，seg1+Assocpattern，seg1）?1k1001k2=0.7500.250.2500.75]

之后我们可以看到，片段2中a，b两个类（结点）和待测设计模式中的两个类（结点）相似度均为0.5，在相对片段1中，A/C两类的相似性和待测设计模式的相似性为0.75，所以得出结论，片段1相比片段2与待测设计模式的相似度更高。

6 设计模式检测算法步骤

1）假设待检测系统有数量为n的类，需要将系统的每个特性（如前文提到的a/g图等等）都表示为一个独立的n * n特征描述矩阵。

2）检测继承结构。这里将每个继承结构抽象成一棵树，特别地，如果某个类有多个父节点，那么该类会同时出现在多棵树中，如下图所示的C，C1，C2既属于层次结构1，也属于层次结构2。

3）构建子系统矩阵。依据目标设计模式来划分子系统，如果目标设计模式有且仅有单。

独的继承树，那么步骤2中划分出来的每一棵继承树都被视为一个子系统。如果目标设计模式有多棵继承树组成，那么子系统将是步骤2中划分出来的继承树的组合数。如：某设计模式有2棵继承树，待测项目供有m棵继承树，那么子系统的数量就是m（m-1）/2。

4）相似度算法的计算。此处计算每个子系统矩阵与待测设计模式的相似度，大致计算过程在第4节有描述，不再赘述。

5）降序排序相似度计算结果。每一个待测设计模式都会得到一个列表，根据这个列表里得分最高的类来提取设计模式检测结果。

6）阈值选取问题。选取有一个假设：给定一个设计模式的实例，那么这个实例里，经过修改的特征不会超过一个。所以假设某设计模式有x个特征，阈值就为（x-1）/x。

7 检测结果

8 总结

基于相似度计算的UML图匹配算法比传统图匹配算法的设计模式检测效果更好，效率更高。使用该算法开发设计模式检测软件，可以作为插件集成进SonarQube，和其他技术债务一起扫描。开发者根据扫描结果识别到系统哪些地方运用了设计模式，可以更好地理解系统结构，并对系统进行优化和重构，提高汽车行业软件系统架构的质量。

参考文献：

[1] 刘亚珺，李兵，李增扬，等.吴闽泉软件集成开发环境的技术债务管理研究[J].计算机科学，2017，44（11）：15-21.

[2] 程彩凤，林德树.数据结构中图论算法动态智能演示的研究[J].现代电子技术，2017，40（18）：40-42.

[3] 傅明丽.UML建模技术在软件开发中的应用[J].科技展望，2015（18）.

[4] 肖卓宇，黎妍，何锫，等.基于矩阵积分评估的设计模式检测研究[J].小型微型计算机系统，2016（7）：1428-1433.

【通联编辑：朱宝贵】