基于快速搜索序列的结构型设计模式挖掘方法研究

摘要

设计模式能够在较大程度上反映软件系统的设计思路.准确地挖掘并理解软件源码中所使用的设计模式实例,能够帮助开发和维护人员理解软件系统的设计和实现,从而促进对软件系统的维护、升级、二次开发和文档化等工作.目前已存在多种挖掘结构型设计模式实例的方法,其中部分方法将软件系统源码和设计模式转化为图的形式,并通过寻找同构子图的方式挖掘设计模式实例.然而,由于挖掘同构子图是一个NP完全问题,这些方法的效率普遍不太理想.针对这一问题,本文提出一种高效的基于有向圈子图同构的结构型设计模式挖掘方法.该方法根据设计模式的图表示形式生成一个快速搜索序列,在挖掘同构有向子图(或设计模式实例)时根据该快速搜索序列可以大大减少搜索空间,从而显著提高挖掘过程的效率.本文通过对3个开源软件源码的实验分析验证了本文方法的有效性和效率.