基于子图发现的设计模式识别系统——子图发现算法的设计与实现---毕业论文.doc

《基于子图发现的设计模式识别系统——子图发现算法的设计与实现---毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科毕业论文基于子图发现的设计模式识别系统——子图发现算法的设计与实现DesignPatternDetectingSystembySubgraphDiscovery——TheDesignandImplementationofSubgraphDiscovery姓名：学号：学　　院：软件学院系：软件工程专业：软件工程年级：指导教师：年月摘　要现代软件业已经广泛应用设计模式来重用最佳实践和改善软件质量。然而受制于软件系统的规模和设计文档的缺失，开发人员无法直观地理解现有软件系统中应用的设计模式，从源码中发现设计模式实例对于提高软件可理解性和可维护性、软件设计重用以及软件重构具有重要意义。为了便于在实

2、际应用中理解、选择和实践设计模式，设计模式的特征通常以非形式化的方式描述，在进行设计模式识别时需要对其进行形式化的表示，已有的研究中采用不同的中间表示来描述设计模式和系统源码以及提出不同的算法来进行设计模式识别。本文在比较目前已有的设计模式发现方法的基础上，进一步提出了一种新的设计模式识别方法。本文提出了一种基于子图发现的设计模式识别方法，将抽象语义图作为系统源码和设计模式签名的中间表示，将在系统源码中发现设计模式实例的问题转化成在非连通图中发现同构子图的问题。设计模式签名描述了设计模式的结构和行为特征，并转换成确定有限自动机，有限自动机的终态代表着特定的设计模式。子图发现算法包括了搜索集初始

3、化、子图扩展和子图集合并等方面。该算法利用确定有限自动机来指导候选子图的生成，并且该算法只需运行一次就可以发现所有设计模式的实例。通过在三个开源项目进行实验，评估了该方法的精确性和以及效率。为了提高算法的性能，本文选择数据分解技术和基于线程的共享地址空间编程模型将原有算法设计成并行的算法。改进后的算法大幅提高了运行效率，运行时间减少了百分之三十。关键词：设计模式识别；子图发现；并行算法AbstractDesignpatternshavebeenwidelyadoptedbymodernsoftwareindustrytoreusethebestpracticesandimprovethequa

4、lityofsoftwaresystems.However,manysystemsarelegacyandthedesigndocumentsisoftenmissing,thisretardthecomprehensionofsystems’designandarchitectureduringmaintenanceactives.Designpatternsarenormallydescribedinformallytounderstandandusedthemeasilyinpractice;researchersneedtocharacterizedesignpatternsforma

5、llyduringdesignpatterndetection.Relatedworkusesseveralintermediaterepresentationsofsoftwaresystemsanddesignpatterns,andintroducesorproposessomealgorithmstodetectdesignpatterninstances.Thispaperpresentsanalgorithmbasedonsubgraphdiscoverytorecognizeinstancesofdesignpatternsinasoftwaresystem.Intheappro

6、ach,thesystemanddesignpatternsarebothdescribedwithAbstractSyntaxGraph(ASG),thereforefindingadesignpatternistomatchASGsub-structureswithpatternsignatures.DesignpatternsignaturesdescribethestructuralandbehaviorcharacteristicsofdesignpatternsandaretransformedintoDeterministicFiniteAutomaton(DFA).Subgra

7、phdiscoveryconsistsofsearchlistinitialization,subgraphextensionandsubgraphcombination.ThisapproachistouseDFAtoguidethecandidategenerationanditrecognizesallthepatterninstancesinonepass.Experimentaleval