基于相似度評分與二級子系統的設計模式識別

王雷，王文發，宋慧娜，張帥

（1.延安大學數學與計算機科學學院，陜西延安 716000；2.陜西省能源大數據智能處理省市共建重點實驗室，陜西延安 716000；3.延安大學 上海文思海輝聯合實驗室（大數據應用開發方向），陜西 延安 716000）

0 概述

設計模式［1-3］是解決某個特定面向對象軟件問題的特定方法，使人們更加簡單方便地復用成功的設計和體系結構。現代軟件業廣泛采用設計模式來重用最佳實踐，以提高軟件系統的質量。從源代碼或系統設計（例如統一建模語言（Unified Modeling Language，UML）模型）中自動識別相應的設計模式，可以為面向設計模式的軟件理解、維護和重構等活動提供自動化支持［4-5］。自軟件設計模式提出以來，設計模式的識別成為逆向軟件工程領域中非常重要的研究課題。

在GoF 設計模式提出后不久，少數研究人員對設計模式的識別進行研究。例如，KRAMER 等［6］提出一種自動搜索面向對象軟件的結構設計模式方法。近年來，越來越多的研究人員致力于設計模式識別的研究。設計模式識別技術主要分為基于傳統技術和基于機器學習的設計模式識別方法。基于傳統技術的設計模式識別方法使用圖論算法、可擴展標記語 言（XML）、抽象語法樹（Abstract Syntax Tree，AST）等技術將系統和模板設計模式進行匹配，以尋找系統中的模式實例。而基于機器學習的設計模式識別方法通過從實際應用中實現的設計模式實例中學習規則，以預測未知系統中的模式識別。這些方法大多直接將原系統與設計模式進行匹配，限制了其召回率或精確率。

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

1 設計模式識別

1.1 基于傳統技術的設計模式識別方法

研究人員提出 很多基于邏輯推理［6，9］、圖論算法［10-12］、可擴展標記語言［13-15］、抽象語法樹［16-17］、本體技 術［15，18］、抽象語義圖［19］、形式化技術［20］、規 則［21-23］等傳統技術的設計模式識別方法。

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

1.2 基于機器學習技術的設計模式檢測

近年來，機器學習技術開始興起，為設計模式的識別提供了一個新的途徑。設計模式識別規則非常復雜和靈活，而機器學習算法可以從實際應用中實現的設計模式實例中學習規則。研究人員將決策樹［24-25］、聚類［24-25］、支持向量機［26-27］、線性回歸［27］、人工神經網絡［28-30］、關聯分析［31］、集成學習［32-34］等機器學習技術用于設計模式的識別。這些方法的一般流程：首先，從實際軟件系統中構造正負樣本；然后，在得到正負樣本后，經過特征提取、特征選擇及特征轉換，使用機器學習算法對特征向量進行學習，以獲取設計模式分類器模型；最后，使用決策模型對未知系統進行設計模式的檢測。

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

2 基本流程

本文對前期研究［7-8］中的基于相似度評分系統與二級子系統的設計模式識別方法的基本流程進行細化。本文方法的基本流程如圖1 所示。

3 系統信息的提取與有向圖/矩陣表示

3.1 系統信息的提取

從系統中設計模式的識別需要提取系統信息。本文對系統的UML 類圖的XML 文件進行解析來獲取關聯、泛化、依賴、抽象類、子類對象創建、抽象方法調用等信息，并對這些信息進行存儲。

對于缺乏UML 設計文檔而只有源代碼形式的系統，本文借助UML 建模工具的逆向工程功能將源代碼轉化為UML 類圖模型，然后再對轉化得到的UML 類圖進行解析以獲取相關信息。

3.2 系統與設計模式的有向圖/矩陣表示

由于本文使用相似度評分算法計算系統和設計模式之間的相似度矩陣來尋找系統中存在的模式實例，因此提取到系統的關聯、泛化、依賴、抽象類、子類對象創建、抽象方法調用等信息后，根據這些信息將系統表示為有向圖/矩陣形式。此外，將設計模式也同樣表示為有向圖/矩陣形式并提前存儲。

在前期研究中［7-8］考慮關聯、泛化（包括接口與類之間的實現關系）、依賴、聚合、抽象類、對象創建、抽象方法調用、無子類8 個特征。本文去掉了無子類特征，其原因為無子類特征并不能用于區分模式角色和非模式角色。例如在狀態模式的結構描述中，角色ConcreteState 無子類，但對應角色ConcreteState 的類SelectionTool 卻有子類。去掉聚合特征的原因為聚合事實上是關聯的特例，因此，本文不再專門考慮聚合特征。此外，由于創建某個類的子類對象比某個類的對象更能標識設計模式的存在，因此本文將文獻［7-8］的“對象創建”特征修改為“子類對象創建”特征。

文獻［7-8］提出一種系統和設計模式的有向圖/矩陣表示，分別定義了系統或設計模式的關聯關系有向圖/矩陣、泛化關系有向圖/矩陣、依賴關系有向圖/矩陣、聚合關系有向圖/矩陣、抽象類有向圖/矩陣、對象創建有向圖/矩陣、抽象方法調用有向圖/矩陣以及無子類有向圖/矩陣。本文所提的系統和設計模式的有向圖/矩陣表示在此基礎上去掉無子類有向圖/矩陣，并將對象創建有向圖/矩陣修改為子類對象創建有向圖/矩陣。關聯關系有向圖/矩陣、依賴關系有向圖/矩陣、聚合關系有向圖/矩陣、抽象類有向圖/矩陣、抽象方法調用有向圖/矩陣的定義請參見文獻［7-8］。本文給出子類對象創建有向圖/矩陣的定義。

定義1系統或設計模式的子類對象創建有向圖定義為有向圖GSubClCre=（V，E）。其中：1）V中的每個頂點對應系統或模式中的一個類；2）E中的每條邊對應一個子類創建關系，該條邊由創建實例的類指向被實例化的子類對象。

該有向圖的鄰接矩陣稱為子類對象創建矩陣，定義為：

本文以狀態模式來說明設計模式的表示。對于設計模式結構的描述主要參考文獻［3］，并做了如下改進：

1）文獻［3］中模式的結構是利用對象建模技術（Object Modeling Technique，OMT）進行描述，本文在此基礎上用UML 進行描述。

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

改進的狀態模式結構描述如圖2 所示。

圖2 改進的狀態模式結構描述Fig.2 Description of improved state pattern structure

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

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

4 子系統的劃分與二級子系統的構建

4.1 子系統的劃分

本文首先將待考查系統劃分為若干子系統。子系統的劃分方法請參見文獻［7-8］。

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

圖4 開源項目JHotDraw 5.1 的子系統s1的UML 類圖Fig.4 UML class diagram of subsystem s1 of open source project JHotDraw 5.1

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

4.2 原系統直接匹配的問題

現有設計模式識別方法大多直接將原系統與模式進行匹配來識別模式實例。本文以文獻［10］為例，說明將原系統直接與模式進行匹配存在的問題：

1）在通常情況下，子系統會包含一些不關聯任何模式角色的類，這些類會干擾匹配的精度。設有子系統s2，其UML 類圖如圖6 所示。

圖6 子系統s2的UML 類圖Fig.6 UML class diagram of subsystem s2

其中，類D不關聯任何模式角色，經計算（詳細算法請參見第5 節，為方便說明這里只考慮“泛化”特征和“關聯”特征），子系統s2與狀態模式之間的相似度矩陣為：

在子系統中類C和狀態模式的角色c3（ConcreteState）的相似度分數為1.000 0，根據文獻［10］所提的方法說明存在狀態模式，且類C關聯c3（ConcreteState）。本文分別考察c1（Context）列和c2列的最大值，c1（Context）列的最大值為0.500 0，對應類｛A，D｝，c2（State）列的最大值為0.750 0，對應類B。組合可得兩個狀態模式實例：第1 個實例的類A、類B、類C分別關聯狀態模式的角色c1（Context）、c2（State）、c3（ConcreteState）；第2 個實例的類D、類B、類C分別關聯狀態模式的角色c1（Context）、c2（State）、c3（ConcreteState）。顯 然，第2 個實例是一個假陽性實例。

2）文獻［10］所提的方法在根據相似度矩陣判斷是否存在模式實例時，只要有一列的某個元素值超過閾值就認為存在模式實例，雖然某些類與角色關聯，但是相似度評分卻比較低。若一個模式角色關聯子系統中的多個類，這些類的相似度分數通常比較低。設有子系統s3，其UML 類圖如圖7 所示。

圖7 子系統s3的UML 類圖Fig.7 UML class diagram of subsystem s3

狀態模式的角色c3（ConcreteState）和類C、c3（ConcreteState）和類D、c3（ConcreteState）和類E的相似度分數均僅為0.333 3，為方便說明，本文僅考慮泛化特征和關聯特征。只要有一列的某個元素值超過閾值就認為存在模式實例，會引入大量的假陽性實例，導致精確率下降。

3）某個子系統可以包含某種模式的多個實例，文獻［10］所提方法通過組合對應于各個角色的類來構建模式實例，這可能會引入假陽性實例。設有子系統s4，其UML 類圖如圖8 所示。根據文獻［10］所提的方法，得到4 個狀態模式實例（只考慮泛化特征和關聯特征）：（B，A，C，E）、（D，C，E）、（B，C，E）、（D，A，C，E）。顯然，實例（B，C，E）和（D，A，C，E）為假陽性實例。

圖8 子系統s4的UML 類圖Fig.8 UML class diagram of subsystem s4

4.3 二級子系統的構建

本文通過對子系統中的類及其之間的關系進行刪減和重組，將子系統進一步劃分為若干個類個數與待識別模式中角色個數相等的二級子系統。本文對文獻［7-8］中二級子系統的構建方法進行修正，除泛化關系以外的其他關系，即關聯、依賴、抽象類、子類對象創建、抽象方法調用，將直接刪減從被刪減類出發的關系和指向被刪減類的關系，而不再進行重組。修正后構建某個子系統s的針對模式p二級子系統的算法如下：

步驟1置集合Class={C1,C2,…,Cn}為子系統s的所有類構成的集合，其中n為子系統s中類的個數。

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

步驟3每個子集合對應一個二級子系統，該二級子系統中的類為該子集合中的類，二級子系統中類的關系為原子系統中類的關系刪減與重組。對于某種關系（關聯、泛化、依賴、抽象類、子類對象創建、抽象方法調用），刪減與重組的規則如下：

1）對于關聯、依賴、抽象類、子類對象創建、抽象方法調用關系，直接刪減從被刪減類出發的關系和指向被刪減類的關系。

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

步驟4去除不包含泛化關系的二級子系統，以及存在沒有任何關系的兩個類（也沒有通過其他類產生關聯）的二級子系統，例如，子系統s由類C25（ActionTool）、C29（BorderTool）和C30（PolygonTool）構成的二級子系統，其中，C29（BorderTool）和C30（PolygonTool）沒有關聯，其余二級子系統為最終的二級子系統。

單件模式只包含一個角色，則二級子系統只包含一個類。例如，子系統s2中類的個數為4，狀態模式中角色的個數為3，則從4 個類中選擇3 個類共有=20 種不同的選法。去除掉不包含泛化關系的1 種選法（二級子系統（D，A，B）和存在沒有關聯的兩個類的2 種選法，即二級子系統（D，A，C）和（D，B，C）），最終得到1 個二級子系統。

本文考慮圖4 所示的JHotDraw 5.1 的子系統s1的4 個二級子系統，分別記為其中二級子系統s′11由子系統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）組成。二級子系統的有向圖/矩陣表示分別如圖9和圖10 所示。和的有向圖/矩陣表示類似。

圖9 二級子系統 的有向圖/矩陣表示Fig.9 Directed graph/matrix representation of secondary subsystem

圖10 二級子系統 的有向圖/矩陣表示Fig.10 Directed graph/matrix representation of secondary subsystem

5 相似度矩陣的計算

本文將系統劃分為二級子系統后，依次計算各二級子系統的有向圖/矩陣和設計模式的有向圖/矩陣之間的相似度矩陣。二級子系統s′和p 設計模式之間的關聯相似度矩陣等6 個相似度矩陣和總相似度矩陣的計算公式以及總相似度矩陣的歸一化公式請參見文獻［7-8］。本文以狀態模式和圖4 所示的JHotDraw 5.1 子系 統s1的二級子系 統為例，說明相似度評分的計算過程。經計算可得狀態模式和二級子系統之間的相似度矩陣為：

歸一化總相似度矩陣為：

某個二級子系統s′和某種設計模式p之間的相似度矩陣Similatirys′,p的計算流程如圖11 所示。

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

6 二級子系統的判斷

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

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

并非所有列均有至少一個元素值大于等于該列對應角色的閾值，則說明二級子系統不是狀態模式的實例。

對于：

所有列均有至少一個元素的值大于等于該列對應角色的匹配臨界值，則說明二級子系統為狀態模式的實例。在c1（Context）對應的列中，值最大的元素對應C8（DrawingView）行，則說明二級子系統中的類C8（DrawingView）關聯狀態模式的角色c1（Context）。類似地，可以得到二級子系統中的類C5（Tool）、C12（ConnectionTool）分別關聯狀態模式的角色c2（State）、c3（ConcreteState）。

同理，二級子系統為狀態模式的實例，且二級子系統中的類C16（SelectionTool）、C5（Tool）和C14（DragTracker）分別關聯狀態模式的角色c1（Context）、c2（State）、c3（ConcreteState），而二級子系統不是狀態模式的實例。

類似地，可以判斷JHotDraw 5.1 的子系統s的其他二級子系統是否為模式實例。

7 判斷結果的進一步處理

對于系統中的一個模式實例，通常存在多個類關聯同一個模式角色的情況。例如，在狀態模式中，角色ConcreteState 關聯多個代表具體狀態的類。此外，還存在著一個子系統中包含同一種模式的多個實例的情況。因此，本文需要對某種模式p實例中某個子系統s的二級子系統進行進一步處理，對文獻［7-8］中判斷為模式實例的二級子系統的進一步處理算法進行修正和細化，修正和細化后算法的步驟如下：

步驟1若所有二級子系統只有一個被判斷為模式p的實例，則說明子系統s只包含該設計模式的一個實例，且每個模式角色關聯子系統中的一個類。否則轉到步驟2。

步驟2若被判斷為模式p的實例的l（l≥2）個二級子系統無公共類，則說明子系統s包含該設計模式的l（l≥2）個實例，且每個模式實例的每個類關聯模式p的一個角色。否則轉到步驟3。

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

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

2）若每個公共類分別關聯同一個模式角色，而和中的某個非公 共類各自關聯不同的角色，則不需進行合并。

3）若存在某個公共類在兩個二級子系統中關聯不同的模式角色，則不需進行合并。

重復以上過程直到集合I中不存在可以合并的兩個實例，此時集合I中的實例為最終的實例。

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

圖12 子系統s1的一個狀態/策略模式實例Fig.12 A state/strategy pattern instance of subsystem s1

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

圖13 子系統s1的另一個狀態/策略模式實例Fig.13 Another state/strategy pattern instance of subsystem s1

因為狀態模式和策略模式的有向圖/矩陣完全相同，所以上述兩個實例也可以認為是策略模式的候選實例。

8 實驗與結果分析

本文使用文獻［12］所提的方法、文獻［10］所提的方法、文獻［34］所提的方法和本文方法SSDPD 在三個開源項目上進行實驗，并從精確率、召回率和CPU 時間花費三個指標對實驗結果進行分析和討論。

8.1 實驗環境與實驗數據

本文使用JavaWeb 技術，以Eclipse 工具作為開發環境研發本文方法的支撐工具。該工具是本文在文獻［7-8］中的所研發設計模式識別工具的更新和升級版本，命名為EasyDetector 2.0。

實驗的運行環境：Windows 10 操作系統、Genuine Intel?CPU（核心數為4，線程數為8）、16 GB內存、2.40 GHz 主頻、500 GB 硬盤。

開源項目JHotDraw、JRefactory 和JUnit 包含大量的設計模式實例，這些項目的文檔較詳細地記錄了設計模式使用的信息，因此，被用于設計模式識別方法的驗證。本文選用JHotDraw 5.1、JRefactory 2.6.24 和JUnit 3.7 作為實驗數據。

8.2 評估指標與結果分析

本文的準確率評估指標與文獻［7-8］相同，通過CPU 時間花費來評估時間效率。

表1～表3 分別所示為文獻［10］方法、文獻［12］方法、文獻［34］方法和本文方法SSDPD 對三個開源項目進行設計模式識別的準確率對比。

表1 不同方法對JHotDraw 5.1 的識別準確率對比Table 1 Recognition accuracy comparison among different methods for JHotDraw 5.1 %

表2 不同方法對JRefactory 2.6.24 的識別準確率對比Table 2 Recognition accuracy comparison among different methods for JRefactory 2.6.24 %

表3 不同方法對JUnit 3.7 的識別準確率對比Table 3 Recognition accuracy comparison among different methods for JUnit 3.7 %

從表1～表3 可以看出：文獻［12］方法、文獻［10］方法、文獻［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%。文獻［12］方法在三個項目上均取得了較高的精確率，但對JHotDraw 5.1 和JRefactory 2.6.24 識別的召回率較低。與文獻［12］方法相比，文獻［10］方法在三個項目上均取得了較高的召回率，但精確率都較低，尤其是JUnit 3.7 的精確率僅為60.0%。其原因為這兩種方法都直接將原系統與設計模式進行匹配，引入大量的假陽性或假陰性實例。匹配標準的提高會在一定程度上提高精確率，但導致召回率下降，而降低匹配的標準會提升召回率，導致精確率較低。文獻［34］方法保持了精確率和召回率的平衡，但除JUnit 3.7 以外，其他兩個項目的精確率和召回率均未達到90%。本文方法使用二級子系統進行更精確地匹配，使得精確率和召回率較文獻［12］方法、文獻［10］方法和文獻［34］方法均有所提升。

表4～表6 分別所示為文獻［12］方法、文獻［10］方法、文獻［34］方法和本文方法SSDPD 對三個開源項目進行設計模式識別的CPU 時間花費。其中文獻［34］方法的預處理主要是指分類模型的訓練。

表4 不同方法的JHotDraw 5.1 CPU 時間花費Table 4 JHotDraw 5.1 CPU time cost among different methods 單位：ms

表5 不同方法的JRefactory 2.6.24 CPU 時間花費Table 5 JRefactory 2.6.24 CPU time cost among different methods 單位：ms

表6 不同方法的JUnit 3.7 CPU 時間花費Table 6 JUnit 3.7 CPU time cost among different methods 單位：ms

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

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

9 結束語

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

本文所考慮的6 個特征主要是結構特征，而行為型模式主要根據行為特征來相互區分。下一步將通過形式化技術（例如模型檢測、有限自動機）研究，基于行為特征過濾掉行為型模式候選實例中的假陽性實例，并對具有相似結構的模式實例進行區分。此外，本文基于設計模式的理論描述將設計模式表示為有向圖/矩陣的形式，并使用圖論算法將二級子系統與設計模式進行匹配。使用深度學習從實際應用中實現的設計模式實例中學習規則構建設計模式預測模型，并在本文劃分的子系統和二級子系統的基礎上識別系統中的模式實例也是下一步研究的重點。