一种基于快速搜索序列的结构型设计模式实例挖掘方法

摘要

本发明公开了一种基于快速搜索序列的结构型设计模式实例挖掘方法，该方法首先构建一个用于形式化定义设计模式的通用模型，然后将结构型设计模式的形式化定义和待挖掘的软件源码转化为用三元组表示的类关系图；再遍历结构型设计模式的类关系图CRGd，构建其快速搜索序列，最后找出待挖掘的软件源码所包含的所有结构型设计模式实例。本发明可以优先过滤大量不满足条件的子图，减少挖掘过程的搜索空间，从而提高挖掘过程的执行效率。

说明书

技术领域

本发明属于设计模式挖掘技术领域，具体涉及到一种基于快速搜索序列的结构型 设计模式实例挖掘方法。

背景技术

许多软件系统由于业务需要和技术更新等因素不再被使用、维护和更新，即变成 了所谓的遗留软件。这些遗留软件通常蕴含了许多领域相关的业务知识和设计思路，合理 利用这些遗留软件可以产生巨大的研究和经济价值。然而，在实际的软件设计和开发过程 中，由于开发周期紧张、开发过程不规范、用户需求频繁变更等各方面因素，许多遗留软件 缺少完整且详细的软件设计和开发文档，这严重阻碍了软件开发和维护人员对这些软件系 统的深入理解、升级和维护等工作的顺利进行。

所幸，许多遗留软件尤其是基于面向对象编程的软件系统在设计和开发过程中使 用了大量的设计模式以提高软件系统的质量。设计模式在软件源码中的使用信息(即设计 模式实例)能够在较大程度上反映软件系统的设计思路。其中结构型设计模式主要用于合 理有效地组合不同的类或对象，作为一类重要的设计模式，它被广泛用于软件代码的设计 之中。因此，准确地从软件源码中识别和挖掘结构型设计模式实例能够有效地帮助软件开 发和维护人员快速理解软件系统的原始设计和实现，从而为软件系统的维护、升级更新和 二次开发等工作提供便利。

现有的结构型设计模式实例挖掘方法通常将设计模式和软件源码转化为某种中 间表示形式，从而降低结构型设计模式实例的挖掘难度。其中，部分方法将结构型设计模式 和软件源码转化为某种图的形式，然后从表示软件源码的图中找出所有与表示结构型设计 模式的图相同构的子图，每个子图的顶点所表示的类即可组成一个候选结构型设计模式实 例。这些方法的实现相对简单，并且能够获得较好的实验结果，然而，由于挖掘同构子图问 题是一个NP完全问题，这些方法的执行效率普遍较低。

发明内容

本发明针对现有技术的不足，提供了一种基于快速搜索序列的结构型设计模式实 例挖掘方法。

本发明方法的具体步骤是：

步骤(1)构建一个用于形式化定义设计模式的通用模型，其中包含五种描述设计 模式基本特征的必备元素，分别为：1)pattern：表示设计模式形式化定义的根元素，描述设 计模式的名称；2)role：表示设计模式中所涉及的各个角色，每个角色包含attribute和 method两个子元素；3)attribute：表示角色包含的属性信息；4)method：表示角色包含的方 法信息；5)relation：表示两个角色之间的关系，为泛化关系、聚合关系、关联关系或依赖关 系；使用上述元素形式化定义每种结构型设计模式，并将其保存成XML文档；

步骤(2)将结构型设计模式的形式化定义和待挖掘的软件源码转化为用三元组 CRG＝<V,E,W>表示的类关系图，其中分别包含了结构型设计模式和软件源码的关键结构信 息，如设计模式的角色、软件源码中的类、属性、方法以及类与类之间的关系；

步骤(3)遍历结构型设计模式的类关系图CRG_d，构建其快速搜索序列，用于表示在后续 挖掘设计模式实例过程中能够显著减少搜索空间的搜索顺序，可表示为其中m_i表示快速搜索序列的一个结点，w_i表示结点m_i所对应的图中顶点v_k的权重信息(包括 出度权重和入度权重)，r_i,j表示结点m_i所表示顶点v_k到其他结点m_j所表示顶点v_k'之间的关 系；

步骤(4)在待挖掘的软件源码的类关系图CRG_s中找出某种结构型设计模式的快速 搜索序列SEQ中第一个结点m₁的所有候选顶点，每个候选顶点的出度权重和入度权重能够 分别整除m₁的出度权重和入度权重；然后针对m₁的每个候选顶点，寻找每个后续结点m_i的候 选顶点，这些候选顶点的出度权重和入度权重必须能够分别整除对应结点的出度权重和入 度权重，并且必须与其余结点的某个候选顶点之间存在对应的关系(即r_i,j中定义的结点m_i和m_j之间的关系)；在每次遍历结束后，任取SEQ中每个结点的一个候选顶点所对应的类组 合在一起即构成了一个设计模式实例，并将其添加到设计模式实例集合中；所有遍历结束 后即可找出待挖掘的软件源码所包含的所有结构型设计模式实例。

本发明所提供的基于快速搜索序列的结构型设计模式实例挖掘方法由一组功能 模块组成，它们包括：结构型设计模式形式化定义模块、类关系图构建模块、快速搜索序列 构建模块和结构型设计模式实例挖掘模块。

结构型设计模式形式化定义模块根据预先定义的通用模型中声明的5种描述设计 模式基本特征的元素形式化定义每一种结构型设计模式，将每种结构型设计模式的形式化 定义保存成一份XML文档。

类关系图构建模块输入结构型设计模式的形式化定义文档和待挖掘的软件源码， 为结构型设计模式和待挖掘的软件源码生成相应的类关系图，其中分别包含了结构型设计 模式和待挖掘的软件源码的关键信息，如类的声明信息、属性、方法以及类与类之间的关系 (如泛化关系、聚合关系、关联关系和依赖关系等)。

快速搜索序列构建模块采用某种特殊的深度优先方式遍历设计模式的类关系图， 从而构建一个快速搜索序列，用于指定一个在挖掘结构型设计模式实例过程中所遵循的搜 索设计模式中每个角色的顺序。

结构型设计模式实例挖掘模块输入结构型设计模式的快速搜索序列和软件源码 的类关系图，按照快速搜索序列中定义的搜索顺序从软件源码的类关系图中找出所有满足 快速搜索序列中所定义条件的子图，每个子图所对应的类即可组成一个结构型设计模式实 例。

本发明提出的方法采用基于子图同构和快速搜索序列的结构型设计模式实例挖 掘策略。与传统的基于子图同构的设计模式实例挖掘方法相比，本发明提出了一种更加通 用的模型定义设计模式，并在挖掘结构型设计模式实例过程中引入快速搜索序列以提高执 行效率。根据快速搜索序列的特征可知，优先寻找候选顶点的角色包含更多的约束条件，待 挖掘的软件源码的类关系图中满足其约束条件的候选顶点也越少，因此可以优先过滤大量 不满足条件的子图，减少挖掘过程的搜索空间，从而提高挖掘过程的执行效率。

附图说明

图1结构型设计模式实例挖掘流程图；

图2通用模型结构图；

图3-1装饰者模式的类图；

图3-2装饰者模式的类关系图。

具体实施方式

本发明所提供的基于快速搜索序列的结构型设计模式实例挖掘方法的具体实施 方式主要分4步(如图1所示)：

(1)形式化定义每种结构型设计模式；(2)将结构型设计模式的形式化定义和待挖 掘的软件源码分别转化类关系图，其中分别包含了结构型设计模式和待挖掘的软件源码的 关键特征；(3)遍历结构型设计模式的类关系图，创建结构型设计模式的快速搜索序列，用 于表示在挖掘过程中所遵循的搜索结构型设计模式中每个角色的顺序；(4)根据结构型设 计模式的快速搜索序列，从软件源码的类关系图中挖掘结构型设计模式实例。

为叙述方便，定义相关符号如下：

CRG_d：结构型设计模式的类关系图。

CRG_s：待挖掘的软件源码的类关系图。

SEQ：结构型设计模式的快速搜索序列。

n：结构型设计模式的角色个数或待挖掘的软件源码中类的个数。

α：表示一个类中包含的属性个数。

β：表示一个类中包含的方法个数。

CIS：候选设计模式实例集合。

(1)形式化定义结构型设计模式

为了更加准确地形式化定义结构型设计模式，为自动化地挖掘结构型设计模式实 例提供基础，本发明定义了一个用于形式化定义结构型设计模式的通用模型，具体结构如 图2所示，其中包含5种描述结构型设计模式基本特征的必备元素，分别为：1)pattern：表示 结构型设计模式形式化定义的根元素，描述结构型设计模式的名称；2)role：表示结构型设 计模式中所涉及的各个角色，每个角色包含attribute和method两个子元素；3)attribute： 表示角色包含的属性信息，如属性名称和属性类型等；4)method：表示角色包含的方法信 息，如方法名称、返回值和参数等；5)relation：表示两个角色之间的关系，可为泛化关系、 聚合关系、关联关系或依赖关系。使用上述元素形式化定义每种结构型设计模式，并将其保 存为XML文档。

(2)构建结构型设计模式和软件源码的类关系图

本发明将结构型设计模式和待挖掘的软件源码转化为类关系图的形式，从而降低 挖掘结构型设计模式实例的难度。类关系图是一种带权有向图，可用三元组CRG＝<V,E,W> 表示，其中V＝{v₁,v₂,...,v_n}为类关系图的顶点集合，每个顶点表示结构型设计模式的某 个角色或待挖掘的软件源码中的某个类；为类关系图的边集 合，每条边e_i,j表示表示该边两个顶点v_i和v_j所表示的角色或类之间的关系，其中包含泛化 关系、聚合关系、关联关系和依赖关系，分别用gen、agg、ass和dep表示；W表示为类关系图中 顶点和边赋权重的函数，设顶点v_i所表示的角色或类包含α个属性和β个方法，该函数将权 值2、3、5、7、11和13分别赋至角色(或类)所拥有的每一个属性、方法以及每条边所对应的泛 化关系(gen)、聚合关系(agg)、关联关系(ass)和依赖关系(dep)，每条边的权重即为该边所 表示关系的权重。例如，若存在边e_i,j＝gen，则该边的权重w(e_i,j)＝5。若顶点v_i和v_j之间不 存在边，即e_i,j＝null，则记为w(e_i,j)＝1；此外，该函数将2^α、2^β与从该顶点v_i出发的所有边 的权值的乘积作为顶点v_i的出度权重，可记为：将指向该 顶点v_i的所有边的权值的乘积作为顶点v_i的入度权重，可记为：装 饰者模式的类图和相对应的类关系图如图3-1和图3-2所示，其中顶点的权重以“出度权重/ 入度权重”的形式呈现在图中。

(3)构建结构型设计模式的快速搜索序列

该过程通过遍历结构型设计模式的类关系图CRG_d，为每种结构型设计模式确定一个唯 一的快速搜索序列，用于指定一个能够在挖掘结构型设计模式实例的过程中有效地减少搜索空 间的搜索顺序，具体可表示为$SEQ={\{m_i,w_i,r_{i,j}^{*}\}}^n=\{<v_k,p_k,l_k>,<w_{out}\left(v_k\right),w_{in}\left(v_k\right)>,<v_k,v_{k^{\prime }},l_{k,k^{\prime }}{>}^{*}\},$其中m_i＝<v_k,p_k,l_k>表示快速搜索序列的结点，v_k表示该结点所表示的图中的顶点，p_k表示 v_k的父顶点，l_k表示v_k的标签(即设计模式的角色名)；w_i＝<w_out(v_k),w_in(v_k)>记录了顶点v_k的出度权重和入度权重；r_i,j＝<v_k,v_k',l_k,k'>表示当前顶点v_k与其余顶点之间的关系，其中 l_k,k'＝{gen|agg|ass|dep}。

快速搜索序列的构建过程主要包含以下两个步骤：

1)在CRG_d剩余的顶点中选择出度权重最大的顶点v，若存在多个满足条件的顶点， 则在其中选择入度权重最大的顶点；选择CRG_d剩余的边中从顶点v出发且权重最小的边e， 将边e的两个顶点添加到已被访问的顶点集合V_T中，将顶点v作为快速搜索序列SEQ的一个 新结点，并将e的信息也添加到该结点中；接着将e从CRG_d中删除。

2)找出CRG_d剩余的边中从V_T出发的所有边，从不存在，则返回步骤1)；否则从中选 择权重最小的边集合F，针对其中的每条边，若边的末尾顶点属于V_T，则将该边的信息添加 到相应的SEQ结点中，并将其从F和CRG_d中删除，否则将该边的末尾顶点添加到V_T中，并为其 创建一个新的SEQ结点。重复执行步骤2)直至所有顶点均被访问，即|V(CRG_d)|＝|V_T|。

根据上述步骤，装饰者模式的快速搜索序列可表示为：

SEQ_Decorator＝{{m₁＝<v₃,null,Decorator>,w₁＝<210,5>,r₁₂＝<v₃,v₁,{gen,agg} >},

{m₂＝<v₁,v₃,Component>,w₂＝<3,175>,null>},

{m₃＝<v₄,null,ConcreteDecorator>,w₃＝<45,1>,r₃₁＝<v₄,v₃,gen>},

{m₄＝<v₂,null,ConcreteComponent>,w₄＝<15,1>,r₄₂＝<v₂,v₁,gen>}}

(4)挖掘结构型设计模式实例

该过程根据结构型设计模式快速搜索序列中定义的搜索顺序，从待挖掘的软件源 码的类关系图CRG_s中挖掘结构型设计模式实例，包含以下两个步骤：

1)寻找快速搜索序列SEQ中第一个结点m₁的候选顶点。遍历待挖掘的软件源码的 类关系图CRG_s，若当前顶点的出度权重和入度权重能够分别整除m₁的出度权重和入度权重， 则将其作为m₁的候选顶点，并将找出的所有候选顶点保存到候选顶点集合CVS(m₁)中。

2)分别从CVS(m₁)中的每个候选顶点出发寻找快速搜索序列SEQ中其余结点的候 选顶点。在每次遍历过程中，针对SEQ的某个结点m_i，其候选顶点与某个已知结点m_j的候选顶 点之间必须存在相应的关系(即SEQ的r_i,j定义的结点m_i和m_j之间的关系)，并且每个候选顶 点的出度权重和入度权重必须能够分别整除对应结点的出度权重和入度权重。在每次遍历 结束后，若SEQ中的每个结点都存在候选顶点，则任取SEQ中每个结点的一个候选顶点所对 应的类组合在一起即可构成一个结构型设计模式实例，并将其添加到设计模式实例集合 CIS中；所有遍历结束后即可找出所有的结构型设计模式实例。

本发明可用于挖掘遗留软件源码中所使用的结构型设计模式实例，以帮助软件开 发和维护人员快速理解软件系统的原始设计和实现。