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

摘要

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

主权项

一种基于快速搜索序列的结构型设计模式实例挖掘方法，其特征在于该方法的具体步骤是：步骤(1).构建一个用于形式化定义设计模式的通用模型，其中包含5种描述设计模式基本特征的必备元素，分别为：1)pattern：表示设计模式形式化定义的根元素，描述设计模式的名称；2)role：表示设计模式中所涉及的各个角色，每个角色包含attribute和method两个子元素；3)attribute：表示角色包含的属性信息；4)method：表示角色包含的方法信息；5)relation：表示两个角色之间的关系，为泛化关系、聚合关系、关联关系或依赖关系；使用上述元素形式化定义每种结构型设计模式，并将其保存成XML文档；步骤(2).将结构型设计模式的形式化定义和待挖掘的软件源码转化为用三元组CRG＝<V,E,W>表示的类关系图，其中：V＝{v₁,v₂,...,v_n}为类关系图的顶点集合，每个顶点表示结构型设计模式的某个角色或待挖掘的软件源码中的某个类；为类关系图的边集合，每条边表示该边的两个顶点所表示角色之间或类之间的关系，分为泛化关系gen、聚合关系agg、关联关系ass和依赖关系dep；W表示为类关系图中顶点和边赋权重的函数，设顶点v_i所表示的角色或类包含α个属性和β个方法，该函数将权重2、3、5、7、11和13分别赋至角色或类所拥有的每一个属性、方法以及每条边所对应的泛化关系gen、聚合关系agg、关联关系ass和依赖关系dep，，每条边的权重即为该边所表示关系的权重，并将2^α、2^β与从该顶点v_i出发的所有边的权值的乘积作为顶点v_i的出度权重w_out(v_i)，将指向该顶点v_i的所有边的权值的乘积作为顶点v_i的入度权重w_in(v_i)；步骤(3).遍历每种结构型设计模式的类关系图CRG_d，构建其快速搜索序列，可表示为其中m_i表示快速搜索序列的一个结点，w_i表示结点m_i所对应的类关系图CRG_d中顶点v_k的权重信息，权重信息包括出度权重和入度权重，r_i,j表示结点m_i所表示顶点v_k到其他结点m_j所表示顶点v_k'之间的关系，“*”表示大于等于一个；快速搜索序列的构建过程分以下两个步骤：1)在CRG_d未被访问过的顶点中选择出度权重最大的顶点v，若存在多个具有最大出度权重的顶点，则选择其中入度权重最大的顶点，选择CRG_d剩余的边中从顶点v出发的权重最小的边e，将边e的两个顶点添加到已被访问的顶点集合V_T中，然后将顶点v作为快速搜索序列SEQ中的一个结点，即记录SEQ中的m_i和w_i，将边e的信息添加到该结点中，即记录SEQ中的r_i,j，并将边e从CRG_d中删除；2)找出CRG_d剩余的边中从V_T出发的所有边，若不存在，则返回步骤1)；否则从中选择权重最小的边集合F，针对边集合F的每条边，若边的末尾顶点属于V_T，则将该边的信息添加到相应的SEQ结点中，即记录SEQ中的r_i,j，并将其从F和CRG_d中删除；否则将该边的末尾顶点添加到V_T中，并为其创建一个SEQ结点，即记录SEQ中的m_i和w_i；重复步骤2)直至CRG_d中的所有顶点均被访问；步骤(4).在待挖掘的软件源码的类关系图CRG_s中找出某种结构型设计模式的快速搜索序列SEQ中第一个结点m₁的所有候选顶点，每个候选顶点的出度权重和入度权重必须能够分别整除m₁的出度权重和入度权重；然后针对m₁的每个候选顶点，寻找每个后续结点m_i的候选顶点，这些候选顶点的出度权重和入度权重必须能够分别整除对应结点的出度权重和入度权重，并且必须与其余结点的某个候选顶点之间存在对应的关系，即r_i,j中定义的结点m_i和m_j之间的关系；在每次遍历结束后，任取SEQ中每个结点的一个候选顶点所对应的类组合在一起即构成了一个设计模式实例，并将其添加到设计模式实例集合中；所有遍历结束后即可找出待挖掘的软件源码所包含的所有结构型设计模式实例。