王雷，王文發(fā)，宋慧娜，張帥

（1.延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西延安 716000；2.陜西省能源大數(shù)據(jù)智能處理省市共建重點(diǎn)實(shí)驗(yàn)室，陜西延安 716000；3.延安大學(xué) 上海文思海輝聯(lián)合實(shí)驗(yàn)室（大數(shù)據(jù)應(yīng)用開(kāi)發(fā)方向），陜西 延安 716000）

0 概述

設(shè)計(jì)模式［1-3］是解決某個(gè)特定面向?qū)ο筌浖?wèn)題的特定方法，使人們更加簡(jiǎn)單方便地復(fù)用成功的設(shè)計(jì)和體系結(jié)構(gòu)?，F(xiàn)代軟件業(yè)廣泛采用設(shè)計(jì)模式來(lái)重用最佳實(shí)踐，以提高軟件系統(tǒng)的質(zhì)量。從源代碼或系統(tǒng)設(shè)計(jì)（例如統(tǒng)一建模語(yǔ)言（Unified Modeling Language，UML）模型）中自動(dòng)識(shí)別相應(yīng)的設(shè)計(jì)模式，可以為面向設(shè)計(jì)模式的軟件理解、維護(hù)和重構(gòu)等活動(dòng)提供自動(dòng)化支持［4-5］。自軟件設(shè)計(jì)模式提出以來(lái)，設(shè)計(jì)模式的識(shí)別成為逆向軟件工程領(lǐng)域中非常重要的研究課題。

在GoF 設(shè)計(jì)模式提出后不久，少數(shù)研究人員對(duì)設(shè)計(jì)模式的識(shí)別進(jìn)行研究。例如，KRAMER 等［6］提出一種自動(dòng)搜索面向?qū)ο筌浖慕Y(jié)構(gòu)設(shè)計(jì)模式方法。近年來(lái)，越來(lái)越多的研究人員致力于設(shè)計(jì)模式識(shí)別的研究。設(shè)計(jì)模式識(shí)別技術(shù)主要分為基于傳統(tǒng)技術(shù)和基于機(jī)器學(xué)習(xí)的設(shè)計(jì)模式識(shí)別方法?；趥鹘y(tǒng)技術(shù)的設(shè)計(jì)模式識(shí)別方法使用圖論算法、可擴(kuò)展標(biāo)記語(yǔ) 言（XML）、抽象語(yǔ)法樹(shù)（Abstract Syntax Tree，AST）等技術(shù)將系統(tǒng)和模板設(shè)計(jì)模式進(jìn)行匹配，以尋找系統(tǒng)中的模式實(shí)例。而基于機(jī)器學(xué)習(xí)的設(shè)計(jì)模式識(shí)別方法通過(guò)從實(shí)際應(yīng)用中實(shí)現(xiàn)的設(shè)計(jì)模式實(shí)例中學(xué)習(xí)規(guī)則，以預(yù)測(cè)未知系統(tǒng)中的模式識(shí)別。這些方法大多直接將原系統(tǒng)與設(shè)計(jì)模式進(jìn)行匹配，限制了其召回率或精確率。

為此，在前期研究［7-8］的基礎(chǔ)上，本文進(jìn)一步探索基于相似度評(píng)分和二級(jí)子系統(tǒng)的設(shè)計(jì)模式識(shí)別（SSDPD）方法。提出一種系統(tǒng)和設(shè)計(jì)模式的有向圖/矩陣表示方法。在此基礎(chǔ)上，對(duì)待考查系統(tǒng)劃分為若干個(gè)子系統(tǒng)，并將子系統(tǒng)進(jìn)一步拆分和重組為二級(jí)子系統(tǒng)。利用相似度評(píng)分算法判斷二級(jí)子系統(tǒng)是否為模式實(shí)例，并將判斷結(jié)果進(jìn)行合并做進(jìn)一步處理，以獲取最終的模式實(shí)例。

1 設(shè)計(jì)模式識(shí)別

1.1 基于傳統(tǒng)技術(shù)的設(shè)計(jì)模式識(shí)別方法

研究人員提出 很多基于邏輯推理［6，9］、圖論算法［10-12］、可擴(kuò)展標(biāo)記語(yǔ)言［13-15］、抽象語(yǔ)法樹(shù)［16-17］、本體技 術(shù)［15，18］、抽象語(yǔ)義圖［19］、形式化技術(shù)［20］、規(guī) 則［21-23］等傳統(tǒng)技術(shù)的設(shè)計(jì)模式識(shí)別方法。

基于傳統(tǒng)技術(shù)的設(shè)計(jì)模式識(shí)別方法的一般流程：首先，從源代碼和模式中提取相關(guān)特征值，例如類、屬性、操作以及類之間的不同關(guān)系；然后，將設(shè)計(jì)模式轉(zhuǎn)換為某種具有嚴(yán)格語(yǔ)義的形式，根據(jù)提取到的源代碼信息，將系統(tǒng)轉(zhuǎn)換為相應(yīng)的某種具有嚴(yán)格語(yǔ)義的形式；最后，將系統(tǒng)和設(shè)計(jì)模式轉(zhuǎn)換為某種具有嚴(yán)格語(yǔ)義的形式后，通過(guò)執(zhí)行模式匹配算法將子系統(tǒng)和模板設(shè)計(jì)模式進(jìn)行匹配，若匹配成功，則認(rèn)為子系統(tǒng)為模式（候選）實(shí)例，否則排除。

1.2 基于機(jī)器學(xué)習(xí)技術(shù)的設(shè)計(jì)模式檢測(cè)

近年來(lái)，機(jī)器學(xué)習(xí)技術(shù)開(kāi)始興起，為設(shè)計(jì)模式的識(shí)別提供了一個(gè)新的途徑。設(shè)計(jì)模式識(shí)別規(guī)則非常復(fù)雜和靈活，而機(jī)器學(xué)習(xí)算法可以從實(shí)際應(yīng)用中實(shí)現(xiàn)的設(shè)計(jì)模式實(shí)例中學(xué)習(xí)規(guī)則。研究人員將決策樹(shù)［24-25］、聚類［24-25］、支持向量機(jī)［26-27］、線性回歸［27］、人工神經(jīng)網(wǎng)絡(luò)［28-30］、關(guān)聯(lián)分析［31］、集成學(xué)習(xí)［32-34］等機(jī)器學(xué)習(xí)技術(shù)用于設(shè)計(jì)模式的識(shí)別。這些方法的一般流程：首先，從實(shí)際軟件系統(tǒng)中構(gòu)造正負(fù)樣本；然后，在得到正負(fù)樣本后，經(jīng)過(guò)特征提取、特征選擇及特征轉(zhuǎn)換，使用機(jī)器學(xué)習(xí)算法對(duì)特征向量進(jìn)行學(xué)習(xí)，以獲取設(shè)計(jì)模式分類器模型；最后，使用決策模型對(duì)未知系統(tǒng)進(jìn)行設(shè)計(jì)模式的檢測(cè)。

上述兩大類方法已經(jīng)取得了一定的效果。然而，這些方法大多直接將原系統(tǒng)與設(shè)計(jì)模式進(jìn)行匹配，以尋找系統(tǒng)中的模式實(shí)例。設(shè)計(jì)模式在實(shí)際的工程項(xiàng)目中通常會(huì)有各種各樣的模式變體，這些變體難以與模板設(shè)計(jì)模式完全匹配。此外，設(shè)計(jì)模式還存在模式實(shí)例中的多個(gè)類關(guān)聯(lián)同一個(gè)模式角色或一個(gè)子系統(tǒng)中包含同一種模式的多個(gè)實(shí)例的情況。因此，將原系統(tǒng)直接與模板設(shè)計(jì)模式相匹配會(huì)引入大量的假陰性或假陽(yáng)性實(shí)例，使得召回率或精確率下降。

2 基本流程

本文對(duì)前期研究［7-8］中的基于相似度評(píng)分系統(tǒng)與二級(jí)子系統(tǒng)的設(shè)計(jì)模式識(shí)別方法的基本流程進(jìn)行細(xì)化。本文方法的基本流程如圖1 所示。

3 系統(tǒng)信息的提取與有向圖/矩陣表示

3.1 系統(tǒng)信息的提取

從系統(tǒng)中設(shè)計(jì)模式的識(shí)別需要提取系統(tǒng)信息。本文對(duì)系統(tǒng)的UML 類圖的XML 文件進(jìn)行解析來(lái)獲取關(guān)聯(lián)、泛化、依賴、抽象類、子類對(duì)象創(chuàng)建、抽象方法調(diào)用等信息，并對(duì)這些信息進(jìn)行存儲(chǔ)。

對(duì)于缺乏UML 設(shè)計(jì)文檔而只有源代碼形式的系統(tǒng)，本文借助UML 建模工具的逆向工程功能將源代碼轉(zhuǎn)化為UML 類圖模型，然后再對(duì)轉(zhuǎn)化得到的UML 類圖進(jìn)行解析以獲取相關(guān)信息。

3.2 系統(tǒng)與設(shè)計(jì)模式的有向圖/矩陣表示

由于本文使用相似度評(píng)分算法計(jì)算系統(tǒng)和設(shè)計(jì)模式之間的相似度矩陣來(lái)尋找系統(tǒng)中存在的模式實(shí)例，因此提取到系統(tǒng)的關(guān)聯(lián)、泛化、依賴、抽象類、子類對(duì)象創(chuàng)建、抽象方法調(diào)用等信息后，根據(jù)這些信息將系統(tǒng)表示為有向圖/矩陣形式。此外，將設(shè)計(jì)模式也同樣表示為有向圖/矩陣形式并提前存儲(chǔ)。

在前期研究中［7-8］考慮關(guān)聯(lián)、泛化（包括接口與類之間的實(shí)現(xiàn)關(guān)系）、依賴、聚合、抽象類、對(duì)象創(chuàng)建、抽象方法調(diào)用、無(wú)子類8 個(gè)特征。本文去掉了無(wú)子類特征，其原因?yàn)闊o(wú)子類特征并不能用于區(qū)分模式角色和非模式角色。例如在狀態(tài)模式的結(jié)構(gòu)描述中，角色ConcreteState 無(wú)子類，但對(duì)應(yīng)角色ConcreteState 的類SelectionTool 卻有子類。去掉聚合特征的原因?yàn)榫酆鲜聦?shí)上是關(guān)聯(lián)的特例，因此，本文不再專門考慮聚合特征。此外，由于創(chuàng)建某個(gè)類的子類對(duì)象比某個(gè)類的對(duì)象更能標(biāo)識(shí)設(shè)計(jì)模式的存在，因此本文將文獻(xiàn)［7-8］的“對(duì)象創(chuàng)建”特征修改為“子類對(duì)象創(chuàng)建”特征。

文獻(xiàn)［7-8］提出一種系統(tǒng)和設(shè)計(jì)模式的有向圖/矩陣表示，分別定義了系統(tǒng)或設(shè)計(jì)模式的關(guān)聯(lián)關(guān)系有向圖/矩陣、泛化關(guān)系有向圖/矩陣、依賴關(guān)系有向圖/矩陣、聚合關(guān)系有向圖/矩陣、抽象類有向圖/矩陣、對(duì)象創(chuàng)建有向圖/矩陣、抽象方法調(diào)用有向圖/矩陣以及無(wú)子類有向圖/矩陣。本文所提的系統(tǒng)和設(shè)計(jì)模式的有向圖/矩陣表示在此基礎(chǔ)上去掉無(wú)子類有向圖/矩陣，并將對(duì)象創(chuàng)建有向圖/矩陣修改為子類對(duì)象創(chuàng)建有向圖/矩陣。關(guān)聯(lián)關(guān)系有向圖/矩陣、依賴關(guān)系有向圖/矩陣、聚合關(guān)系有向圖/矩陣、抽象類有向圖/矩陣、抽象方法調(diào)用有向圖/矩陣的定義請(qǐng)參見(jiàn)文獻(xiàn)［7-8］。本文給出子類對(duì)象創(chuàng)建有向圖/矩陣的定義。

定義1系統(tǒng)或設(shè)計(jì)模式的子類對(duì)象創(chuàng)建有向圖定義為有向圖GSubClCre=（V，E）。其中：1）V中的每個(gè)頂點(diǎn)對(duì)應(yīng)系統(tǒng)或模式中的一個(gè)類；2）E中的每條邊對(duì)應(yīng)一個(gè)子類創(chuàng)建關(guān)系，該條邊由創(chuàng)建實(shí)例的類指向被實(shí)例化的子類對(duì)象。

該有向圖的鄰接矩陣稱為子類對(duì)象創(chuàng)建矩陣，定義為：

本文以狀態(tài)模式來(lái)說(shuō)明設(shè)計(jì)模式的表示。對(duì)于設(shè)計(jì)模式結(jié)構(gòu)的描述主要參考文獻(xiàn)［3］，并做了如下改進(jìn)：

1）文獻(xiàn)［3］中模式的結(jié)構(gòu)是利用對(duì)象建模技術(shù)（Object Modeling Technique，OMT）進(jìn)行描述，本文在此基礎(chǔ)上用UML 進(jìn)行描述。

2）刪減特征完全相同的角色，以提升匹配的準(zhǔn)確率及時(shí)間效率。例如，文獻(xiàn)［3］中的角色ConcreteStateA、ConcreteStateB … 的特征完全相同，故只保留一個(gè)。

改進(jìn)的狀態(tài)模式結(jié)構(gòu)描述如圖2 所示。

圖2 改進(jìn)的狀態(tài)模式結(jié)構(gòu)描述Fig.2 Description of improved state pattern structure

記Context、State 和ConcreteState 分別為c1、c2和c3。根據(jù)上述定義，可得狀態(tài)模式的有向圖/矩陣表示，如圖3 所示。其他22 種設(shè)計(jì)模式的有向圖/矩陣表示參見(jiàn)文獻(xiàn)［7-8］。

圖3 狀態(tài)模式的有向圖/矩陣表示Fig.3 Directed graph/matrix representation for the state pattern

4 子系統(tǒng)的劃分與二級(jí)子系統(tǒng)的構(gòu)建

4.1 子系統(tǒng)的劃分

本文首先將待考查系統(tǒng)劃分為若干子系統(tǒng)。子系統(tǒng)的劃分方法請(qǐng)參見(jiàn)文獻(xiàn)［7-8］。

本文給出JHotDraw 5.1 的一個(gè)針對(duì)不包含繼承層或只包含一個(gè)繼承層的設(shè)計(jì)模式子系統(tǒng)，記為s1。子系統(tǒng)s1的UML 類圖如圖4 所示。該子系統(tǒng)共包含38 個(gè)類（接口）和一個(gè)繼承層。將圖4 中各個(gè)類（接口）從左至右、從上至下分別記為C1，C2，…，C38，可得子系統(tǒng)s1的有向圖/矩陣表示，圖5 所示為泛化關(guān)系有向圖/矩陣。

圖4 開(kāi)源項(xiàng)目JHotDraw 5.1 的子系統(tǒng)s1的UML 類圖Fig.4 UML class diagram of subsystem s1 of open source project JHotDraw 5.1

圖5 子系統(tǒng)s1的泛化有向圖/矩陣表示Fig.5 Generalization directed graph/matrix representation of subsystem s1

4.2 原系統(tǒng)直接匹配的問(wèn)題

現(xiàn)有設(shè)計(jì)模式識(shí)別方法大多直接將原系統(tǒng)與模式進(jìn)行匹配來(lái)識(shí)別模式實(shí)例。本文以文獻(xiàn)［10］為例，說(shuō)明將原系統(tǒng)直接與模式進(jìn)行匹配存在的問(wèn)題：

1）在通常情況下，子系統(tǒng)會(huì)包含一些不關(guān)聯(lián)任何模式角色的類，這些類會(huì)干擾匹配的精度。設(shè)有子系統(tǒng)s2，其UML 類圖如圖6 所示。

圖6 子系統(tǒng)s2的UML 類圖Fig.6 UML class diagram of subsystem s2

其中，類D不關(guān)聯(lián)任何模式角色，經(jīng)計(jì)算（詳細(xì)算法請(qǐng)參見(jiàn)第5 節(jié)，為方便說(shuō)明這里只考慮“泛化”特征和“關(guān)聯(lián)”特征），子系統(tǒng)s2與狀態(tài)模式之間的相似度矩陣為：

在子系統(tǒng)中類C和狀態(tài)模式的角色c3（ConcreteState）的相似度分?jǐn)?shù)為1.000 0，根據(jù)文獻(xiàn)［10］所提的方法說(shuō)明存在狀態(tài)模式，且類C關(guān)聯(lián)c3（ConcreteState）。本文分別考察c1（Context）列和c2列的最大值，c1（Context）列的最大值為0.500 0，對(duì)應(yīng)類｛A，D｝，c2（State）列的最大值為0.750 0，對(duì)應(yīng)類B。組合可得兩個(gè)狀態(tài)模式實(shí)例：第1 個(gè)實(shí)例的類A、類B、類C分別關(guān)聯(lián)狀態(tài)模式的角色c1（Context）、c2（State）、c3（ConcreteState）；第2 個(gè)實(shí)例的類D、類B、類C分別關(guān)聯(lián)狀態(tài)模式的角色c1（Context）、c2（State）、c3（ConcreteState）。顯 然，第2 個(gè)實(shí)例是一個(gè)假陽(yáng)性實(shí)例。

2）文獻(xiàn)［10］所提的方法在根據(jù)相似度矩陣判斷是否存在模式實(shí)例時(shí)，只要有一列的某個(gè)元素值超過(guò)閾值就認(rèn)為存在模式實(shí)例，雖然某些類與角色關(guān)聯(lián)，但是相似度評(píng)分卻比較低。若一個(gè)模式角色關(guān)聯(lián)子系統(tǒng)中的多個(gè)類，這些類的相似度分?jǐn)?shù)通常比較低。設(shè)有子系統(tǒng)s3，其UML 類圖如圖7 所示。

圖7 子系統(tǒng)s3的UML 類圖Fig.7 UML class diagram of subsystem s3

狀態(tài)模式的角色c3（ConcreteState）和類C、c3（ConcreteState）和類D、c3（ConcreteState）和類E的相似度分?jǐn)?shù)均僅為0.333 3，為方便說(shuō)明，本文僅考慮泛化特征和關(guān)聯(lián)特征。只要有一列的某個(gè)元素值超過(guò)閾值就認(rèn)為存在模式實(shí)例，會(huì)引入大量的假陽(yáng)性實(shí)例，導(dǎo)致精確率下降。

3）某個(gè)子系統(tǒng)可以包含某種模式的多個(gè)實(shí)例，文獻(xiàn)［10］所提方法通過(guò)組合對(duì)應(yīng)于各個(gè)角色的類來(lái)構(gòu)建模式實(shí)例，這可能會(huì)引入假陽(yáng)性實(shí)例。設(shè)有子系統(tǒng)s4，其UML 類圖如圖8 所示。根據(jù)文獻(xiàn)［10］所提的方法，得到4 個(gè)狀態(tài)模式實(shí)例（只考慮泛化特征和關(guān)聯(lián)特征）：（B，A，C，E）、（D，C，E）、（B，C，E）、（D，A，C，E）。顯然，實(shí)例（B，C，E）和（D，A，C，E）為假陽(yáng)性實(shí)例。

圖8 子系統(tǒng)s4的UML 類圖Fig.8 UML class diagram of subsystem s4

4.3 二級(jí)子系統(tǒng)的構(gòu)建

本文通過(guò)對(duì)子系統(tǒng)中的類及其之間的關(guān)系進(jìn)行刪減和重組，將子系統(tǒng)進(jìn)一步劃分為若干個(gè)類個(gè)數(shù)與待識(shí)別模式中角色個(gè)數(shù)相等的二級(jí)子系統(tǒng)。本文對(duì)文獻(xiàn)［7-8］中二級(jí)子系統(tǒng)的構(gòu)建方法進(jìn)行修正，除泛化關(guān)系以外的其他關(guān)系，即關(guān)聯(lián)、依賴、抽象類、子類對(duì)象創(chuàng)建、抽象方法調(diào)用，將直接刪減從被刪減類出發(fā)的關(guān)系和指向被刪減類的關(guān)系，而不再進(jìn)行重組。修正后構(gòu)建某個(gè)子系統(tǒng)s的針對(duì)模式p二級(jí)子系統(tǒng)的算法如下：

步驟1置集合Class={C1,C2,…,Cn}為子系統(tǒng)s的所有類構(gòu)成的集合，其中n為子系統(tǒng)s中類的個(gè)數(shù)。

步驟2每次從集合Class中取出t個(gè)類構(gòu)成一個(gè)新的集合，其中t為模式p中角色的個(gè)數(shù)，可構(gòu)成個(gè)不同的子集合。

步驟3每個(gè)子集合對(duì)應(yīng)一個(gè)二級(jí)子系統(tǒng)，該二級(jí)子系統(tǒng)中的類為該子集合中的類，二級(jí)子系統(tǒng)中類的關(guān)系為原子系統(tǒng)中類的關(guān)系刪減與重組。對(duì)于某種關(guān)系（關(guān)聯(lián)、泛化、依賴、抽象類、子類對(duì)象創(chuàng)建、抽象方法調(diào)用），刪減與重組的規(guī)則如下：

1）對(duì)于關(guān)聯(lián)、依賴、抽象類、子類對(duì)象創(chuàng)建、抽象方法調(diào)用關(guān)系，直接刪減從被刪減類出發(fā)的關(guān)系和指向被刪減類的關(guān)系。

2）對(duì)于泛化關(guān)系，分以下3 種情況討論：（1）若被刪減類只存在指向該類的關(guān)系，則直接刪減這些關(guān)系；（2）若被刪減類只存在從該類出發(fā)的關(guān)系，則直接刪減這些關(guān)系；（3）若被刪減類既有從該類出發(fā)的關(guān)系，又有指向該類的關(guān)系，則刪減從該類出發(fā)的關(guān)系，而將指向該類的關(guān)系重新指向從該類出發(fā)的關(guān)系指向的類。

步驟4去除不包含泛化關(guān)系的二級(jí)子系統(tǒng)，以及存在沒(méi)有任何關(guān)系的兩個(gè)類（也沒(méi)有通過(guò)其他類產(chǎn)生關(guān)聯(lián)）的二級(jí)子系統(tǒng)，例如，子系統(tǒng)s由類C25（ActionTool）、C29（BorderTool）和C30（PolygonTool）構(gòu)成的二級(jí)子系統(tǒng)，其中，C29（BorderTool）和C30（PolygonTool）沒(méi)有關(guān)聯(lián)，其余二級(jí)子系統(tǒng)為最終的二級(jí)子系統(tǒng)。

單件模式只包含一個(gè)角色，則二級(jí)子系統(tǒng)只包含一個(gè)類。例如，子系統(tǒng)s2中類的個(gè)數(shù)為4，狀態(tài)模式中角色的個(gè)數(shù)為3，則從4 個(gè)類中選擇3 個(gè)類共有=20 種不同的選法。去除掉不包含泛化關(guān)系的1 種選法（二級(jí)子系統(tǒng)（D，A，B）和存在沒(méi)有關(guān)聯(lián)的兩個(gè)類的2 種選法，即二級(jí)子系統(tǒng)（D，A，C）和（D，B，C）），最終得到1 個(gè)二級(jí)子系統(tǒng)。

本文考慮圖4 所示的JHotDraw 5.1 的子系統(tǒng)s1的4 個(gè)二級(jí)子系統(tǒng)，分別記為其中二級(jí)子系統(tǒng)s′11由子系統(tǒng)s1中的類C1（AlignCommand）、C5（Tool）和C12（ConnectionTool）組 成，由類C8（DrawingView）、C5（Tool）和C12（ConnectionTool）組成，由類C5（Tool）、C16（SelectionTool）和C14（DragTracker）組 成，由類C5（Tool）、C16（SelectionTool）和C13（CreationTool）組成。二級(jí)子系統(tǒng)的有向圖/矩陣表示分別如圖9和圖10 所示。和的有向圖/矩陣表示類似。

圖9 二級(jí)子系統(tǒng) 的有向圖/矩陣表示Fig.9 Directed graph/matrix representation of secondary subsystem

圖10 二級(jí)子系統(tǒng) 的有向圖/矩陣表示Fig.10 Directed graph/matrix representation of secondary subsystem

5 相似度矩陣的計(jì)算

本文將系統(tǒng)劃分為二級(jí)子系統(tǒng)后，依次計(jì)算各二級(jí)子系統(tǒng)的有向圖/矩陣和設(shè)計(jì)模式的有向圖/矩陣之間的相似度矩陣。二級(jí)子系統(tǒng)s′和p 設(shè)計(jì)模式之間的關(guān)聯(lián)相似度矩陣等6 個(gè)相似度矩陣和總相似度矩陣的計(jì)算公式以及總相似度矩陣的歸一化公式請(qǐng)參見(jiàn)文獻(xiàn)［7-8］。本文以狀態(tài)模式和圖4 所示的JHotDraw 5.1 子系 統(tǒng)s1的二級(jí)子系 統(tǒng)為例，說(shuō)明相似度評(píng)分的計(jì)算過(guò)程。經(jīng)計(jì)算可得狀態(tài)模式和二級(jí)子系統(tǒng)之間的相似度矩陣為：

歸一化總相似度矩陣為：

某個(gè)二級(jí)子系統(tǒng)s′和某種設(shè)計(jì)模式p之間的相似度矩陣Similatirys′,p的計(jì)算流程如圖11 所示。

圖11 相似度矩陣算法的計(jì)算流程Fig.11 Calculation procedure of similarity matrix algorithm

6 二級(jí)子系統(tǒng)的判斷

相似度矩陣的元素表示二級(jí)子系統(tǒng)中的類和模式角色之間的相似度得分，因此可以根據(jù)相似度矩陣判斷二級(jí)子系統(tǒng)是否為模式實(shí)例。二級(jí)子系統(tǒng)是否為模式實(shí)例的判斷方法參考文獻(xiàn)［7-8］。

狀態(tài)模式中的角色c1（Context）、c2（State）和c3（ConcreteState）分別涉及3、4、2 個(gè)特征，取c1（Context）、c2（State）和c3（ConcreteState）的閾值分別為：=0.666 7，=0.750 0，=1.000 0。

并非所有列均有至少一個(gè)元素值大于等于該列對(duì)應(yīng)角色的閾值，則說(shuō)明二級(jí)子系統(tǒng)不是狀態(tài)模式的實(shí)例。

對(duì)于：

所有列均有至少一個(gè)元素的值大于等于該列對(duì)應(yīng)角色的匹配臨界值，則說(shuō)明二級(jí)子系統(tǒng)為狀態(tài)模式的實(shí)例。在c1（Context）對(duì)應(yīng)的列中，值最大的元素對(duì)應(yīng)C8（DrawingView）行，則說(shuō)明二級(jí)子系統(tǒng)中的類C8（DrawingView）關(guān)聯(lián)狀態(tài)模式的角色c1（Context）。類似地，可以得到二級(jí)子系統(tǒng)中的類C5（Tool）、C12（ConnectionTool）分別關(guān)聯(lián)狀態(tài)模式的角色c2（State）、c3（ConcreteState）。

同理，二級(jí)子系統(tǒng)為狀態(tài)模式的實(shí)例，且二級(jí)子系統(tǒng)中的類C16（SelectionTool）、C5（Tool）和C14（DragTracker）分別關(guān)聯(lián)狀態(tài)模式的角色c1（Context）、c2（State）、c3（ConcreteState），而二級(jí)子系統(tǒng)不是狀態(tài)模式的實(shí)例。

類似地，可以判斷JHotDraw 5.1 的子系統(tǒng)s的其他二級(jí)子系統(tǒng)是否為模式實(shí)例。

7 判斷結(jié)果的進(jìn)一步處理

對(duì)于系統(tǒng)中的一個(gè)模式實(shí)例，通常存在多個(gè)類關(guān)聯(lián)同一個(gè)模式角色的情況。例如，在狀態(tài)模式中，角色ConcreteState 關(guān)聯(lián)多個(gè)代表具體狀態(tài)的類。此外，還存在著一個(gè)子系統(tǒng)中包含同一種模式的多個(gè)實(shí)例的情況。因此，本文需要對(duì)某種模式p實(shí)例中某個(gè)子系統(tǒng)s的二級(jí)子系統(tǒng)進(jìn)行進(jìn)一步處理，對(duì)文獻(xiàn)［7-8］中判斷為模式實(shí)例的二級(jí)子系統(tǒng)的進(jìn)一步處理算法進(jìn)行修正和細(xì)化，修正和細(xì)化后算法的步驟如下：

步驟1若所有二級(jí)子系統(tǒng)只有一個(gè)被判斷為模式p的實(shí)例，則說(shuō)明子系統(tǒng)s只包含該設(shè)計(jì)模式的一個(gè)實(shí)例，且每個(gè)模式角色關(guān)聯(lián)子系統(tǒng)中的一個(gè)類。否則轉(zhuǎn)到步驟2。

步驟2若被判斷為模式p的實(shí)例的l（l≥2）個(gè)二級(jí)子系統(tǒng)無(wú)公共類，則說(shuō)明子系統(tǒng)s包含該設(shè)計(jì)模式的l（l≥2）個(gè)實(shí)例，且每個(gè)模式實(shí)例的每個(gè)類關(guān)聯(lián)模式p的一個(gè)角色。否則轉(zhuǎn)到步驟3。

步驟3設(shè)被判斷為模式p的實(shí)例的l（l≥2）個(gè)二級(jí)子系統(tǒng)的集合為I={i1,i2,…,il}，對(duì)于集合I中存在公共類的任 意兩個(gè)二級(jí)子系統(tǒng)和，做如下處理：

1）若每個(gè)公共類分別關(guān)聯(lián)同一個(gè)模式角色，而兩個(gè)二級(jí)子系統(tǒng)中的非公共類共同關(guān)聯(lián)同一個(gè)角色，則為以下兩種情況：（1）非公共類共同關(guān)聯(lián)的角色是子類，則將這兩個(gè)實(shí)例合并為一個(gè)實(shí)例，然后將集合I中合并前的兩個(gè)實(shí)例刪除，將合并得到的新實(shí)例加入集合I中；（2）若非公共類共同關(guān)聯(lián)的角色不是子類，則不需要進(jìn)行合并。

2）若每個(gè)公共類分別關(guān)聯(lián)同一個(gè)模式角色，而和中的某個(gè)非公 共類各自關(guān)聯(lián)不同的角色，則不需進(jìn)行合并。

3）若存在某個(gè)公共類在兩個(gè)二級(jí)子系統(tǒng)中關(guān)聯(lián)不同的模式角色，則不需進(jìn)行合并。

重復(fù)以上過(guò)程直到集合I中不存在可以合并的兩個(gè)實(shí)例，此時(shí)集合I中的實(shí)例為最終的實(shí)例。

本文以圖4 所示的JHotDraw 5.1 的子系統(tǒng)s1和狀態(tài)模式為例，說(shuō)明如何對(duì)判斷為模式實(shí)例的二級(jí)子系統(tǒng)進(jìn)一步處理。子系統(tǒng)s1的二級(jí)子系統(tǒng)被判斷為狀態(tài)模式實(shí)例。將類C8（DrawingView）、C5（Tool）和C13（CreationTool）構(gòu)成的二級(jí)子系統(tǒng)記為，經(jīng)計(jì)算可知，也是狀態(tài)模式實(shí)例。二級(jí)子系統(tǒng)和有公共類C5（Tool）和C8（DrawingView），分別關(guān)聯(lián)角色c1（Context）和c2（State），非公共類C12（ConnectionTool）和C13（CreationTool）均關(guān)聯(lián)模式角色c3（ConcreteState），且角色c3（ConcreteState）為子類，則將二級(jí)子系 統(tǒng)和合并為一個(gè)實(shí) 例。類 似地，可以繼續(xù)與C8（DrawingView）、C5（Tool）、C14（DragTracker）等構(gòu)成的14 個(gè)二級(jí)子系統(tǒng)合并，最終得到的實(shí)例如圖12 所示，其中灰色填充的類為該實(shí)例的類，加粗邊框的16 個(gè)類共同關(guān)聯(lián)同一個(gè)模式角色c3（ConcreteState）。

圖12 子系統(tǒng)s1的一個(gè)狀態(tài)/策略模式實(shí)例Fig.12 A state/strategy pattern instance of subsystem s1

二級(jí)子系統(tǒng)也被判斷為狀態(tài)模式實(shí)例。二級(jí)子 系統(tǒng)和有公共 類C5（Tool），并關(guān)聯(lián)角色c2（State），非公共類C8（DrawingView）和C16（SelectionTool）均關(guān)聯(lián)角色c1（Context），但角色c1不是子類，因此不需要進(jìn)行合并。而可以和與C16（SelectionTool）、C5（Tool）和C15（HandleTracker）等構(gòu)成的2 個(gè)二級(jí)子系統(tǒng)合并，最終得到的實(shí)例如圖13 所示，其中灰色填充的類為該實(shí)例的類，加粗邊框的 3 個(gè)類共同關(guān)聯(lián)模式角色c3（ConcreteState）。

圖13 子系統(tǒng)s1的另一個(gè)狀態(tài)/策略模式實(shí)例Fig.13 Another state/strategy pattern instance of subsystem s1

因?yàn)闋顟B(tài)模式和策略模式的有向圖/矩陣完全相同，所以上述兩個(gè)實(shí)例也可以認(rèn)為是策略模式的候選實(shí)例。

8 實(shí)驗(yàn)與結(jié)果分析

本文使用文獻(xiàn)［12］所提的方法、文獻(xiàn)［10］所提的方法、文獻(xiàn)［34］所提的方法和本文方法SSDPD 在三個(gè)開(kāi)源項(xiàng)目上進(jìn)行實(shí)驗(yàn)，并從精確率、召回率和CPU 時(shí)間花費(fèi)三個(gè)指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析和討論。

8.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

本文使用JavaWeb 技術(shù)，以Eclipse 工具作為開(kāi)發(fā)環(huán)境研發(fā)本文方法的支撐工具。該工具是本文在文獻(xiàn)［7-8］中的所研發(fā)設(shè)計(jì)模式識(shí)別工具的更新和升級(jí)版本，命名為EasyDetector 2.0。

實(shí)驗(yàn)的運(yùn)行環(huán)境：Windows 10 操作系統(tǒng)、Genuine Intel?CPU（核心數(shù)為4，線程數(shù)為8）、16 GB內(nèi)存、2.40 GHz 主頻、500 GB 硬盤(pán)。

開(kāi)源項(xiàng)目JHotDraw、JRefactory 和JUnit 包含大量的設(shè)計(jì)模式實(shí)例，這些項(xiàng)目的文檔較詳細(xì)地記錄了設(shè)計(jì)模式使用的信息，因此，被用于設(shè)計(jì)模式識(shí)別方法的驗(yàn)證。本文選用JHotDraw 5.1、JRefactory 2.6.24 和JUnit 3.7 作為實(shí)驗(yàn)數(shù)據(jù)。

8.2 評(píng)估指標(biāo)與結(jié)果分析

本文的準(zhǔn)確率評(píng)估指標(biāo)與文獻(xiàn)［7-8］相同，通過(guò)CPU 時(shí)間花費(fèi)來(lái)評(píng)估時(shí)間效率。

表1～表3 分別所示為文獻(xiàn)［10］方法、文獻(xiàn)［12］方法、文獻(xiàn)［34］方法和本文方法SSDPD 對(duì)三個(gè)開(kāi)源項(xiàng)目進(jìn)行設(shè)計(jì)模式識(shí)別的準(zhǔn)確率對(duì)比。

表1 不同方法對(duì)JHotDraw 5.1 的識(shí)別準(zhǔn)確率對(duì)比Table 1 Recognition accuracy comparison among different methods for JHotDraw 5.1 %

表2 不同方法對(duì)JRefactory 2.6.24 的識(shí)別準(zhǔn)確率對(duì)比Table 2 Recognition accuracy comparison among different methods for JRefactory 2.6.24 %

表3 不同方法對(duì)JUnit 3.7 的識(shí)別準(zhǔn)確率對(duì)比Table 3 Recognition accuracy comparison among different methods for JUnit 3.7 %

從表1～表3 可以看出：文獻(xiàn)［12］方法、文獻(xiàn)［10］方法、文獻(xiàn)［34］方法的JHotDraw 5.1 平均精確率/召回率分別為90.0%/80.6%、74.9%/96.2% 和89.6%/84.2%；JRefactory 2.6.24 平均精確率/召回率分別為83.6%/71.3%、79.4%/88.1%、88.9%/79.6%；JUnit 3.7 平均精確率/召回率分別為100.0%/95.8%、60%/100%、95.8%/91.7%。文獻(xiàn)［12］方法在三個(gè)項(xiàng)目上均取得了較高的精確率，但對(duì)JHotDraw 5.1 和JRefactory 2.6.24 識(shí)別的召回率較低。與文獻(xiàn)［12］方法相比，文獻(xiàn)［10］方法在三個(gè)項(xiàng)目上均取得了較高的召回率，但精確率都較低，尤其是JUnit 3.7 的精確率僅為60.0%。其原因?yàn)檫@兩種方法都直接將原系統(tǒng)與設(shè)計(jì)模式進(jìn)行匹配，引入大量的假陽(yáng)性或假陰性實(shí)例。匹配標(biāo)準(zhǔn)的提高會(huì)在一定程度上提高精確率，但導(dǎo)致召回率下降，而降低匹配的標(biāo)準(zhǔn)會(huì)提升召回率，導(dǎo)致精確率較低。文獻(xiàn)［34］方法保持了精確率和召回率的平衡，但除JUnit 3.7 以外，其他兩個(gè)項(xiàng)目的精確率和召回率均未達(dá)到90%。本文方法使用二級(jí)子系統(tǒng)進(jìn)行更精確地匹配，使得精確率和召回率較文獻(xiàn)［12］方法、文獻(xiàn)［10］方法和文獻(xiàn)［34］方法均有所提升。

表4～表6 分別所示為文獻(xiàn)［12］方法、文獻(xiàn)［10］方法、文獻(xiàn)［34］方法和本文方法SSDPD 對(duì)三個(gè)開(kāi)源項(xiàng)目進(jìn)行設(shè)計(jì)模式識(shí)別的CPU 時(shí)間花費(fèi)。其中文獻(xiàn)［34］方法的預(yù)處理主要是指分類模型的訓(xùn)練。

表4 不同方法的JHotDraw 5.1 CPU 時(shí)間花費(fèi)Table 4 JHotDraw 5.1 CPU time cost among different methods 單位：ms

表5 不同方法的JRefactory 2.6.24 CPU 時(shí)間花費(fèi)Table 5 JRefactory 2.6.24 CPU time cost among different methods 單位：ms

表6 不同方法的JUnit 3.7 CPU 時(shí)間花費(fèi)Table 6 JUnit 3.7 CPU time cost among different methods 單位：ms

從表4～表6 可以看出，對(duì)于JHotDraw 5.1，文獻(xiàn)［12］方法、文獻(xiàn)［10］方法、文獻(xiàn)［34］方法分別花費(fèi)9 167 ms、7 494 ms 和5 648 012 ms，而本文方法僅用5 408 ms。對(duì)于JRefactory 2.6.24，文獻(xiàn)［12］方法、文獻(xiàn)［10］方法、文獻(xiàn)［34］方法分別花費(fèi)33 189 ms、29 777 ms 和5 649 046 ms，而本文方法僅用22 280 ms。對(duì)于JUnit 3.7，文獻(xiàn)［12］方法、文獻(xiàn)［10］方法、文獻(xiàn)［34］方法分別花費(fèi)4 865ms、4 799 ms 和5 647 797 ms，而本文方法僅用3 284 ms。由于劃分二級(jí)子系統(tǒng)花費(fèi)額外的時(shí)間，因此本文方法在預(yù)處理階段的時(shí)間花費(fèi)相較于文獻(xiàn)［12］方法和文獻(xiàn)［10］方法更多。然而，通過(guò)二級(jí)子系統(tǒng)的劃分，大幅縮小了搜索空間，與文獻(xiàn)［10，12］方法相比，本文的設(shè)計(jì)模式識(shí)別階段節(jié)省了大量時(shí)間。本文方法將子系統(tǒng)進(jìn)一步劃分為若干個(gè)二級(jí)子系統(tǒng)，增加了矩陣運(yùn)算的次數(shù)，在一定程度上會(huì)影響時(shí)間效率。同時(shí)，二級(jí)子系統(tǒng)的劃分也使得參與運(yùn)算的矩陣維數(shù)變小，但時(shí)間效率仍然優(yōu)于直接將原系統(tǒng)與模式進(jìn)行匹配的方法。文獻(xiàn)［34］方法在JHotDraw 5.1、JRefactory 2.6.24 和JUnit 3.7 的識(shí)別階段分別花費(fèi)342 ms、1 376 ms 和127 ms，但模型訓(xùn)練階段（預(yù)處理階段）花費(fèi)了5 647 670 ms（三個(gè)項(xiàng)目只需訓(xùn)練模型一次），總的時(shí)間花費(fèi)遠(yuǎn)超于本文方法。

根據(jù)以上分析可知，本文方法在保持高召回率的基礎(chǔ)上，通過(guò)將子系統(tǒng)進(jìn)一步劃分為二級(jí)子系統(tǒng)進(jìn)行匹配，并將匹配結(jié)果進(jìn)行組合，進(jìn)一步提升了精確率。此外，二級(jí)子系統(tǒng)的劃分使得部分肯定不屬于模式實(shí)例的類在運(yùn)算前就被剔除，且參與運(yùn)算的矩陣維數(shù)變小，時(shí)間效率也有所提升。

9 結(jié)束語(yǔ)

本文在前期研究［7-8］的基礎(chǔ)上，通過(guò)刪減和修改所考慮的特征、修正二級(jí)子系統(tǒng)構(gòu)建算法、修正和細(xì)化判斷為模式實(shí)例的二級(jí)子系統(tǒng)等途徑，探索了基于相似度評(píng)分與二級(jí)子系統(tǒng)的設(shè)計(jì)模式識(shí)別方法。將原系統(tǒng)劃分為若干個(gè)子系統(tǒng)，并對(duì)子系統(tǒng)進(jìn)一步拆解和重組為二級(jí)子系統(tǒng)，利用二級(jí)子系統(tǒng)進(jìn)行匹配，將獲取到的實(shí)例進(jìn)行合并等進(jìn)一步處理。實(shí)驗(yàn)結(jié)果表明，本文方法在保持較高召回率的基礎(chǔ)上可有效提高精確率，此外，時(shí)間效率也優(yōu)于直接將原系統(tǒng)和模式進(jìn)行匹配的方法。

本文所考慮的6 個(gè)特征主要是結(jié)構(gòu)特征，而行為型模式主要根據(jù)行為特征來(lái)相互區(qū)分。下一步將通過(guò)形式化技術(shù)（例如模型檢測(cè)、有限自動(dòng)機(jī)）研究，基于行為特征過(guò)濾掉行為型模式候選實(shí)例中的假陽(yáng)性實(shí)例，并對(duì)具有相似結(jié)構(gòu)的模式實(shí)例進(jìn)行區(qū)分。此外，本文基于設(shè)計(jì)模式的理論描述將設(shè)計(jì)模式表示為有向圖/矩陣的形式，并使用圖論算法將二級(jí)子系統(tǒng)與設(shè)計(jì)模式進(jìn)行匹配。使用深度學(xué)習(xí)從實(shí)際應(yīng)用中實(shí)現(xiàn)的設(shè)計(jì)模式實(shí)例中學(xué)習(xí)規(guī)則構(gòu)建設(shè)計(jì)模式預(yù)測(cè)模型，并在本文劃分的子系統(tǒng)和二級(jí)子系統(tǒng)的基礎(chǔ)上識(shí)別系統(tǒng)中的模式實(shí)例也是下一步研究的重點(diǎn)。