1、厦门大学软件学院毕业设计（论文）开题报告 学生姓名 班级 学号 校内指导教师姓名 职称 所在单位 厦门大学软件学院 毕业设计（论文）题 目 基于子图发现的设计模式识别系统 子图发现算法的设计与实现 毕业设计（论文）的 目标： 设计一个系统使其能够 发现目标系统中基本 形式 的设计模式 和修改版本的设计模式，同时对变化的设计模式有一定预判的能力。系统有 人性化的用户界面 ，强大易用的数据处理 ， 跨平台（ Windows、 Linux 和 Unix） ，性能良好，结果精确（即整个目标系统中未 被挖掘出的设计模式和被误认为是设计模式的数量在可接受范围内）。 论文的研究目标包括子图发现算法和并行算法
2、的设计与实现。论文将从 搜索集初始化 、 子图扩展 和 子图集合并 等方面对子图发现算法进行描述，然后从 数据分解、线程并行、临界区设置等方面阐述并行算法的设计。 基于这个目的， 在 开源系统 JUnit3.8.2、 JHotdraw5.1、 JRefactory2.6.24 上 进行一系列的实验以评估该方法。 实现方法： 一、基本环境 开发工具： Eclipse 3.4 开发语言： Java jdk1.6.0 操作系统 ： Windows Vista Ultimate 处理器： Intel Core 2 CPU 1.86GHz 目标系统： JUnit3.8.2、 JHotdraw5.1、 J
3、Refactory2.6.24 二、基本原理 1.目标系统选择 为了 便于从源码中挖掘元素和进行评估，我们需要一个系统满足以下条件： 它的大小应该是合理的。 它的源码应该是开放的 它应该是面向对象的设计，因为目前主流软件均是面向对象设计 它应该被广泛使用 我们选择 JUnit3.8.2、 JHotdraw5.1、 JRefactory2.6.24 作为目标系统 原由有 三点：一、这些项目开发时，设计模式的思想已经成熟而且被广泛应用；二、JUnit、 JHotDraw、 JRefactory 都是开源项目，源码是公开的，方便对识别结果的验证，三个项目的 规模 逐步递增，可以更好地评估本文提出的
4、设计 模式识别方法；三、其他相关的设计模式发现研究采用了一个或多个这样的系统来评估他们的方法，所以选择上述 3 个项目能够比较和评价实验结果。 2.图表示 在 进行子图挖掘 之前，有必要为研究的系统和要挖掘的模式定义一种 图 表示方式，本文将使用 抽象语义图 (Abstract Semantic Graph, ASG)进行建模。 下 表定义了 ASG 所使 用的图形符号。 在表示系统源码和设计模式签名的 ASG 中 ， 图的顶点为抽象类、具体类、方法中的一种，图的边为表关联关系的一种 (如泛化 、聚合、返回类型依赖等 )。 表： 抽象语义图使用的图形符号 符号 含义 抽象类或接口 具体类 类或
5、接口中的方法 类或接口之间的一对一的属性关联 类或接口之间的一对多的属性关联 类或接口之间的泛化关系 目标方法是源类或接口的一个操作 源方法和目标类或接口之间的返回类型依赖 源方法接收目 标类或接口类型的参数 源方法调用目标方法 源方法重载目标方法 源方法中实例化了目标类，生成对象 3.子图挖掘 (1)图定义 ： 用无限制的 字符标签 来定义属性图是一种普遍的定义图的方式。 (2)图匹配分为精确的图匹配和容错的 图 匹配方法。 (3)频繁子图挖掘算法： 基于 Apriori 方法和 PatternGrowth 方法 (4)Subdue 算法： 作为一种无需监管的挖掘算法， Subdue 算法查
6、找输入图的一个最佳压缩子结构或者子图。 Subdue 在它的主搜索算法用的是集束搜索的一种变形方法，算法大致框架 如 下 图所示。 算法： SUBDUE。查找 最佳地压缩图集 子结构的算法。 输入：图数据集 Graph，束宽度 BeamWidth，最佳压缩图集的大小 MaxBest， 最大子结构数量 MaxSubSize，处理子结构的上限 Limit 输出：最佳压缩图集的子结构集合 BestList 1: ParentList = Null; 2: ChildList = Null; 3: BestList = Null; 4: ProcessedSubs = 0; 5: Create a s
7、ubstructure from each unique vertex label and its single-vertex instances; 6: Insert the resulting substructures in ParentList; 7: while ProcessedSubs Limit and ParentList not empty do 8: while ParentList is not empty do 9: Parent = RemoveHead(ParentList); 10: Extend each instance of Parent in all p
8、ossible ways; 11: Group the extended instances into Child substructures; 12: for each Child do 13: if SizeOf(Child) less than MaxSubSize then 14: Evaluate Child; 15: Insert Child in ChildList in order by value; 16: if BeamWidth Length(ChildList) then 17: Destroy substructure at end of ChildList; 18:
9、 Increment ProcessedSubs; 19: Insert Parent in BestList in order by value; 20: if MaxBest Length(BestList) then 21: Destroy substructure at end of BestList; 22: Switch ParentList and ChildList; 23: return BestList; 图： Subdue 算法 4.并行算法 (1)并行性识别： 在一个程序中，首先要识别出哪些部分可以并行地执行。也就是说，对于来自同一个串行程序的两个不同语句，在什么情况下
10、可以并行执行，且计算结果与串行程序执行结果一致。 (2)分解技术：将计算划分成许多小的计算，再把它们分配到不同处理器中以便并 行执行，这是并行算法设计中的两个关键步骤。目前有一些经常使用的分解技术，这些技术可概括分类为递归分解、数据分解、探测性分解以及推测性分解。递归分解和数据分解技术是比较通用的，因为它们能适用于大量的各种问题。探测性和推测性分解技术是专用性质的，因为它们只适用特定类型的问题。 (3)编程模型：人们已经开发了许多编程语言和程序库用于显式并行编程，这些编程语言及程序库的区别在于程序员可使用的地址空间，对并发活动的同步程度，以及程序的多重性。常用的编程模型有 共享存储编程模型和消
11、息传递编程模式。 (4)并行算法模型： 一 个算法模型就是通过选择一种分解和映射技术并用合适的策略最小化交互来构造并行算法的一种典型方法。并行算法模型包括数据并行模型，任务图模型，工作池模型，主从模型，流水线模型以及混合模型。 5.子图发现算法设计与实现： 本研究将从 搜索集初始化 、 子图扩展 、 子图集合并 等方面对子图发现算法进行设计，然后选择适当的分解技术和编程模型将原有算法设计成并行的算法，以大幅提高程序性能。 时间进度安排： 2008 年 11 月 17 日 -2008 年 1 月 16 日 理解毕业设计 的任务，阅读有关文献，熟悉开发工具。 征求导师的意见， 提交毕 业设计开题报
12、告。 2009 年 1 月 17 日 -2009 年 2 月 28 日 对必要技术及 子图挖掘算法 进一步了解学习，初步建立 Design Pattern 的数据模型。 建立子图发现算法的基本框架，了解目标系统源码中所使用的设计模式。 2009 年 3 月 1 日 -2009 年 3 月 20 日 完成串行子图发现算法的设计，在目标系统上进行实验， 提交毕业设计的中期检查报告。 2009 年 3 月 21 日 -2009 年 5 月 30 日 根据第一阶段的实验结果，将原算法设计成并行算法，重新在目标系统上进行测试，撰写论文。 2009 年 6 月 1 日 -2009 年 6 月 11 日 提
13、交毕业论文，准备毕业答辩。 指导教师审核意见： 校内指导教师签名： 2009 年 月 日 厦门大学软件学院毕业设计（论文） 中期检查 报告 学生姓名 班级 二班 学号 23020051 204442 校内指导教师姓名 职称 助理教授 所在单位 厦门大学软件学院 毕业设计（论文）题 目 基于子图发现的设计模式识别系统 子图发现算法的设计与实现 毕业设计（论文）的 目标和主要任务： 设计一个系统使其能 够 发现目标系统中基本 形式 的设计模式 和修改版本的设计模式，同时对变化的设计模式有一定预判的能力。系统有 人性化的用户界面 ，强大易用的数据处理 ， 跨平台（ Windows、 Linux 和
14、Unix） ，性能良好，结果精确（即整个目标系统中未被挖掘出的设计模式和被误认为是设计模式的数量在可接受范围内）。 论文的研究目标包括子图发现算法和并行算法的设计与实现。论文将从 搜索集初始化 、 子图扩展 和 子图集合并 等方面对子图发现算法进行描述，然后从 数据分解、线程并行、临界区设置等方面阐述并行算法的设计。 基于这个目的， 在 开源系统 JUnit3.8.2、 JHotdraw5.1、 JRefactory2.6.24 上 进行一系列的实验以评估该方法。 已经完成毕业设计（论文）任务的情况 ： 1.子图发现算法 的设计 为设计模式识别算法所设计的 子图发现 算法，与 Subdue 算
15、法类似，但是该算法与 Subdue 算法主要有两个不同之处：首先该算法没有采用启发式集束搜索方法，因为它会丢失设计模式。其次该算法使用了 DFA 来去除那些不可能作为模式候选集的子图。 子图发现 算法的大致 框架 如图 1 所示。 算法： SubgraphDiscovery。应用于设计模式识别的子图发现算法。 输 入：数据集 G， 最多处理的边数 procLimit， 模式指纹 确定有限自动机 DFA 输出：发现的子结构 resultList 1: searchList = Null; 2: candidateList = Null; 3: resultList = Null; 4: proc
16、essedEdges = 0; 5: Create substructures that are isomorphic to the initial states of DFA; 6: Find the isomorphic instances in G and put them into the substructures; 7: Insert the resulting substructures into the searchList; 8: while processedEdges procLimit and searchList is not empty do 9: for each
17、 st in searchList; 10: if st is one of the final states of DFA then 11: Add st to resultList; 12: else 13: Extend each instance of st conforming to DFA; 14: Group the extended instances into stList substructures; 15: for each candidateStucture in stList do 16: Merge candidateStucture into the candid
18、ateList ; 17: searchList = Null; 18: Copy candidateList to searchList; 19: candidateList = Null; 20: processedEdges+; 21: return resultList; 图 1： 子图发现 算法 (1) 初始化搜索集 搜索集的初始化是在图 G 中查找所有的单边子图，它们与 DFA 的初始态图是同构的。图 2 展示了初始化搜索集算法的细节。 算法： InitStructure。初始化搜 索集算法。 输入：数据集 G， 模式指纹 确定有限自动机 DFA 输出： 初始搜索集 initLis
19、t 1: initList = Null; 2: initStatesList Get the initial states of DFA; 3: for each edge in G do 4: Create a single-edge graph g; 5: for each state in initStatesList do 6: if g is isomorphic to state then 7: add g to corresponding node of initList; 8: return initList; 图 2： 初始化搜索集算法 (2) 扩展子图 在候选集生成过程中
20、，通过给定的 k 边图生成一系列 k+1 边图。通过 DFA 得到从此状态迁移到下一状态所需的信息，然后添加一条边将 k 边图扩展成 k+1边图。 DFA 中保存的迁移信息包括用于扩展的顶点，扩展边，边的另一个顶点。扩展子图的大致算法如图 3 所示 。 算法： ExtendIns。子图扩展算法。 输入：数据集 G，用于扩展的 实例 parentIns，对应 DFA 某 一 状态 的 图 structure，扩展信息 transaction 输出： 扩展子图集 extList 1: extList = Null; 2: Get isomorphism relation between paren
21、tIns and structure; 3: if corresponding extended vertex is found 4: if the extended edge is not link to a new vertex 5: touchingEdges Get all edges connect two corresponding vertices in G 6: for each edge in touchingEdges do 7: Confirm it is a new edge of same type then add the new edge to parentIns
22、; 8: Add the new instance to extList; 9: else 10: touchingEdges Get all edges touch corresponding extended vertex; 11: for each edge in touchingEdges do 12: Confirm another new vertex and a same edge then add the new edge to parentIns; 13: Add the new instance to extList; 14: return extList; 图 3： 扩展
23、子图算法 (3) 合并子图集 在子图发现算 法中需要用一种数据结构来保存候选子图集。 PatternList 是自定义的链表结构， PatternList 链表的结点由 PatterNode 组成， PatterNode结点包含了一个在 DFA 中定义的状态和在图 G 中的所有实例。 PatternList 设计如图 4 所示。 A r r ayL i s tP atte r n L i s t+ a dd(obj )+ a ddN ode (s t a t e Id, s ubs t ruc t ure , ne w Ins , c re a t e IfN ot E x i s t )+
24、a ddN ode (s t a t e Id, s ubs t ruc t ure , ne w Ins )+ a ddN ode (ne w P a t t e rnN ode : P a t t e rnN ode )+ a ddIns (i nde x , ne w Ins )P atte r n N od e+ na m e+ s ubs t ruc t rue+ dfa S i dD i r e c te d G r ap hi ns L i s t图 4： PatternList 设计类图 2.在 Junit 上实验结果 本算法在操作系统为 Windows Vista Ultim
25、ate，处理器为 Intel Core 2 CPU 1.86GHz， RAM 2GB 的计算机上进行实验，目标软件系统为 Junit3.8.2。 表 1 给出了识别出设计模式实例的个数。图 5 给出了识别各个设计模式所消耗的 CPU时间对比。 表 1： 基于子图发现的设计模式识别结果 单位 ： 个 JUnit v3.8.2 设计模式 TP FP Adapter 0 0 Bridge 7 0 Command 1 0 Composite 1 0 Decorator 1 0 Factory Method 1 0 Observer 2 0 Proxy 0 0 Singleton 0 0 State/S
26、trategy 3 0 Template Method 1 0 Visitor 0 0 图 5： 各个设计模式识别所消耗 CPU 时间对比 单位 ms 存在的问题和困难（包括需要学院协助解决的问题和困难）： 在子图发现算法的子图扩展部分 涉及到子图同构检验 ，这是一个 NP 完全问题，其计算复杂度相当高 。当程序 以独占 CPU 的方式串行执行时，子图同构后面的指令必须等待，使得 CPU 的利用率不高。 指导教师审核意见： 校外指导教师签名： 2009 年 月 日 校内指导教师签名： 2009 年 月 日 学院检查组意见： 学院检查组组长（签章）： 2009 年 月 日 毕业论文任务书 题 目
27、： 基于子图发现的设计模式识别系统 子图发现算法的设计与实现 目标要求： 设计一个系统使其能够 发现目标系统中基本 形式 的设计模式 和修改版本的设计模式，同时对变化的设计模式有一定预判的能力。系统有 人性化的用户界面 ，强大易用的数据处理 ， 跨平台（ Windows、 Linux 和 Unix） ，性能良好。 子图查找算法只需运行一次就能找到所有符合设计模式签名的实例，能够根据用户需求改变算法的并发性。 支持条件： 开发工具： Eclipse 3.4 开发语言： Java jdk1.6.0 操作系统 ： Windows Vista Ultimate 处理器： Intel Core 2 CPU 1.86GHz 目标系统： JUnit3.8.2、 JHotdraw5.1、 JRefactory2.6.24 校内 指导教师（签名） 职称 学生（签名）
