袁中臣， 馬宗民

(1. 東北大學(xué) 軟件學(xué)院， 遼寧 沈陽(yáng) 110169; 2. 沈陽(yáng)工業(yè)大學(xué) 化工過程自動(dòng)化學(xué)院， 遼寧 遼陽(yáng) 111003)

隨著軟件復(fù)雜性的日益增強(qiáng)，對(duì)于軟件重用的需求在不斷增加.重用的內(nèi)容也不再僅限于代碼，而是涉及到軟件生命周期的各個(gè)階段[1].實(shí)際上，軟件開發(fā)過程中產(chǎn)生的任意產(chǎn)品都在重用范圍之內(nèi)，這種重用被視為軟件工程師的知識(shí)和經(jīng)驗(yàn)的重用.因?yàn)檐浖O(shè)計(jì)對(duì)接下來的開發(fā)階段將產(chǎn)生重要的影響，所以軟件設(shè)計(jì)的重用受到了關(guān)注.作為建模工具，UML類圖被廣泛地應(yīng)用于設(shè)計(jì)階段，已成為軟件設(shè)計(jì)事實(shí)上的標(biāo)準(zhǔn)[2]，所以UML類圖的重用成為研究熱點(diǎn)[3-4].

隨著語義web的發(fā)展，大量的本體被開發(fā).本體是共享概念的明確而詳細(xì)的說明，概念通過特定的關(guān)系建立聯(lián)系[5].本體分為通用本體和領(lǐng)域本體.通用本體覆蓋了若干領(lǐng)域的概念知識(shí)，如WordNet；領(lǐng)域本體是由來自單個(gè)領(lǐng)域的概念構(gòu)成的，如基因組學(xué)領(lǐng)域的基因本體(gene ontology，GO)等.本體為概念之間的相似性度量提供了途徑.例如，在WordNet中提供了基于路徑和信息共享兩種方法來衡量概念之間的相似性[6].相似性度量被廣泛應(yīng)用于分類、聚類和檢索等.在軟件產(chǎn)品的重用過程中，檢索是核心工作，檢索是基于相似性.UML類圖所呈現(xiàn)的信息包含語義和結(jié)構(gòu)，類、屬性和操作屬于語義范疇；UML類圖的結(jié)構(gòu)通過類之間的關(guān)系來表達(dá)，類之間的關(guān)系包含不同的類型(關(guān)聯(lián)、泛化、聚合、組合、依賴和實(shí)現(xiàn)).所以，UML類圖的相似性度量既包含語義相似性也包括結(jié)構(gòu)相似性.

現(xiàn)有的基于重用的類圖檢索可以歸結(jié)為兩種策略.第一種是基于語義的匹配[7]，類圖之間的相似性是通過語義相似性來衡量.其中，類圖的關(guān)系被定義為向量R=[端點(diǎn)類1，關(guān)系類型，端點(diǎn)類2]，關(guān)系的相似性通過向量R的差異或距離來度量.第二種是基于模型查詢語言[8]，解析類圖元素并基于模型查詢語言重寫類圖，并提出模式匹配方法.

第一種策略僅僅考慮了語義，而沒有考慮結(jié)構(gòu).即使考慮了概念之間關(guān)系，本質(zhì)上也是語義匹配，在僅考慮類圖的結(jié)構(gòu)而不考慮語義的檢索要求時(shí)，這種策略不能很好地工作.實(shí)際上，結(jié)構(gòu)對(duì)于一個(gè)UML類圖是非常重要的.在使用UML模型化一個(gè)系統(tǒng)時(shí)，首要考慮的是系統(tǒng)的結(jié)構(gòu)而不是單個(gè)類.第二種策略雖然考慮了結(jié)構(gòu)，但元素匹配是基于關(guān)鍵字而不是基于語義，沒有考慮檢索結(jié)果的非精確性.最后，兩種方法都沒有對(duì)檢索條件給出一種形式化的定義.實(shí)際上，檢索需求經(jīng)常是復(fù)雜的，通常不僅僅是一個(gè)簡(jiǎn)單的類或類圖，這就需要一個(gè)檢索條件的明確表達(dá).同時(shí)，每個(gè)檢索元素在檢索條件中的權(quán)重應(yīng)該被考慮，因?yàn)轭悎D中的不同元素在模型化一個(gè)系統(tǒng)時(shí)的重要程度不同.

本文正是基于語義和結(jié)構(gòu)兩個(gè)方面實(shí)現(xiàn)對(duì)類圖的檢索，定義了語義相似性和結(jié)構(gòu)相似性度量方法.基于檢索流程，形式化地定義了檢索表達(dá)，并提出了檢索算法.實(shí)驗(yàn)驗(yàn)證了所提算法的有效性.

1 UML類圖及其重用模型

1.1 UML類圖

UML類圖是由類和類之間的關(guān)系兩部分構(gòu)成.圖1是類圖的一個(gè)樣例，表示類“Professor”繼承類“Teacher”.

一系列工具能被用來編輯UML類圖，如Rose和MyEclipse等.對(duì)象管理組織(object management group，OMG)為所有UML模型定義了文檔類型定義(document type definition，DTD) 標(biāo)準(zhǔn)[9]，UML模型被描述為遵守DTD的基于XML元數(shù)據(jù)交換(XML-based metadata interchange，XMI)文檔.

1.2 重用模型

UML類圖的重用模型被描述為一個(gè)過程，如圖2所示.這一過程包含4個(gè)階段，分別是類圖的檢索、候選類圖返回、候選類圖調(diào)整并應(yīng)用到新項(xiàng)目和新類圖被抽取并加入到重用庫(kù).在這幾個(gè)階段中，檢索是關(guān)鍵，決定著重用質(zhì)量和效率.重用庫(kù)存儲(chǔ)大量的可重用類圖，重用庫(kù)的有效管理和組織對(duì)于提高檢索效率也是非常重要的.重用庫(kù)中的類圖被分為“域”和“目錄”兩級(jí)，如圖3所示.

2 相似性度量

2.1 語義相似性

現(xiàn)有的語義相似性能被歸結(jié)為同一類，就是基于本體來計(jì)算兩個(gè)概念的語義相似性.本文選擇被廣泛使用的基于本體路徑語義距離來計(jì)算UML類圖概念之間的語義相似性.在本文中，除了類，屬性和方法也被認(rèn)為在語義范疇內(nèi)，所以類圖之間的語義相似性為

式中：cd1和cd2是兩個(gè)類圖；類Ci來自類圖cd1，Ai和Oi分別是類Ci的屬性集合和操作集合；同理，類Cj來自類圖cd2；Aj和Oj分別是類Cj的屬性集合和操作集合；Ci被匹配到Cj，Ai被匹配到Aj,Qi被匹配到Qj；SimC，SimA和SimO分別表示類相似性、屬性相似性和操作相似性.在計(jì)算屬性和操作相似性時(shí)，除了考慮概念語義還考慮到屬性的類型和操作的返回值類型.類圖之間的語義相似性實(shí)際上就是類圖概念元素之間的相似性.這里僅計(jì)算平均相似性，|cdi|表示類圖cdi中包含的類的數(shù)目；α，β和γ是權(quán)重因子，且α+β+γ=1.

2.2 結(jié)構(gòu)相似性

由于UML類圖的半形式化，圖和UML類圖兩種模型在結(jié)構(gòu)上的相似性(類對(duì)應(yīng)于頂點(diǎn)，關(guān)系對(duì)應(yīng)于邊)，本文提出采用圖來表示UML類圖的結(jié)構(gòu)，目的是進(jìn)行結(jié)構(gòu)相似性度量.UML類圖中的類被轉(zhuǎn)換成圖的頂點(diǎn)，UML類圖中的關(guān)聯(lián)、泛化、聚合、組合、依賴和實(shí)現(xiàn)等關(guān)系被轉(zhuǎn)換成邊，并分別被標(biāo)記為e1,e2,e3,e4,e5和e6.這樣類圖之間的結(jié)構(gòu)相似性就被轉(zhuǎn)換成對(duì)應(yīng)的兩個(gè)圖的相似性.兩個(gè)圖之間的結(jié)構(gòu)相似性可以通過最大公共子圖(maximum common subgraph，MCS)度量[10].公式為

其中：NMCS表示存在于MCS中的邊的數(shù)目；|gi|是表示圖gi中邊的數(shù)目.

當(dāng)然，這里求解最大公共子圖是基于邊，而不是頂點(diǎn)，并且邊的匹配是基于上面所述的標(biāo)記.求解最大公共子圖的算法見算法1.

算法1 搜索圖g1和g2之間的最大公共子圖

輸入：圖g1和g2

輸出:最大公共子圖(MCS)

1.初始化狀態(tài)空間S=NULL;

2.//在g1中與S相連的下一條邊ek

while(nextEdge(g1,S,ek)) do

3.begin

4.//ek是否使得g1和g2的公共子圖尺寸增加

if(IsFeasible(g1,g2,S,ek)) then

5. begin //更新公共子圖

6.S=S+ek;//更新狀態(tài)

7. if(size(S)>z)then

8.z=size(S); //更新尺寸

9. end;

10. else //退回S的上一個(gè)狀態(tài)

11. backState(S);

12.end;

13.returnS;

算法執(zhí)行了一個(gè)深度優(yōu)先搜索.S是一個(gè)狀態(tài)空間，用于存儲(chǔ)圖g1和g2之間的公共子圖.S的尺寸會(huì)隨著更多邊的加入而變大直至最后形成最大公共子圖.

3 類圖檢索

3.1 檢索流程

UML類圖的檢索過程描述如圖4所示.用戶首先輸入檢索需求，用戶的輸入可以是單個(gè)類(屬性和操作)，也可以是類圖結(jié)構(gòu).解析是從檢索要求獲取檢索元素，任何基于SAX(simple API for XML)的工具能被用來解析XMI文檔[11].檢索需求經(jīng)常是復(fù)雜的，包含著用戶的多種意愿，所以將檢索需求轉(zhuǎn)換成一個(gè)形式化表述，作為檢索算法的輸入.檢索算法是核心，這里提到的檢索應(yīng)該是非精確的，目的是發(fā)現(xiàn)最貼近檢索需求的候選類圖序列.

3.2 檢索表達(dá)

在輸入檢索需求時(shí)，經(jīng)常會(huì)有如下幾種情況：

1) 希望幾個(gè)檢索元素在候選類圖中同時(shí)出現(xiàn).可以被表達(dá)為

e1∧e2∧e3∧∧em.

2) 希望在候選類圖中某些元素部分出現(xiàn)或者同時(shí)出現(xiàn).可以被表述為

e1∨e2∨e3∨∨ep.

3) 希望有些檢索元素在候選類圖中不要出現(xiàn).可以被表述為

!(e1∨e2∨e3∨∨en) .

所以，綜合上述幾種情況，檢索需求能被形式化地描述如下：

UCD_QS=

3.3 檢索算法

一般情況下，在類圖的檢索中，候選類圖不一定完全滿足檢索需求.這里設(shè)定一個(gè)閾值σ，當(dāng)檢索元素被匹配到重用庫(kù)中的類圖所取得的相似性值大于σ時(shí)，重用庫(kù)中的類圖即被列為候選類圖.因?yàn)椴煌脑?概念和結(jié)構(gòu))在模型化一個(gè)系統(tǒng)時(shí)具有不同的重要程度，所以不同的檢索元素在檢索條件中被分別賦予權(quán)重，W=[w1,w2,,wn].類圖的檢索算法被描述為算法2.

算法 2 類圖的檢索算法

輸入：檢索表達(dá)UCD_QS，W和重用庫(kù)L

輸出：候選類圖序列

1.//初始化目標(biāo)類圖所在域、目錄和候選類圖序列

d=NULL;c=NULL;l={NULL};

2.//獲取檢索元素

classElements=getClass(UCD_QS); //概念元素

noClassElements=getNoClass(UCD_QS);

strucElements=getStructures(UCD_QS);//結(jié)構(gòu)元素

noStrucElements=getNoStructures(UCD_QS);

3.//賦予權(quán)重

assignWeight(classElements, strucElements,W);

4.//候選類圖所在的域

if(classElements!=NULL) then

5.for eachDiinLdo

6.begin

7.FCi=getFeatClass(Di); //獲取特征概念

8.SimDi=SimCS(classElements，F(xiàn)Ci); //域相似性

9.end;

10.SimDx=max(SimD);

11.d=Dx;

12.//候選類圖所在的目錄

if(strucElements!=NULL) then

13.for eachCiinddo

14.begin

15.FSi=getFeatStrucs(Ci); //獲取特征結(jié)構(gòu)

16.SimCi=SimSS(strucElements，F(xiàn)Si); //目錄相似性

17.end;

18.SimCy=max(SimC);

19.c=Cy;

20.//計(jì)算類圖相似性，并插入候選序列

for each cdkincdo

21.if(μ*SimCS(classElements, cdk)+(1-μ) *

SimSS(strucElements, cdk)>σ) then

22.insertCD(cdk,l);

23.//刪除不期望包含元素的類圖

for eacheifrom noClassElements and eachsifrom noStrucElements do

24.for each cdqinldo

25.if(eiorsi) in cdqthen

26.deleteCD(cdq,l);

27.returnl; //返回候選類圖序列

在檢索算法中，基于定義的特征概念和特征結(jié)構(gòu)，通過相似性計(jì)算分別決定候選類圖所在的域和目錄，這樣能過濾掉大量的類圖，大大提高檢索的效率.檢索元素被匹配到已經(jīng)確定目錄內(nèi)的每個(gè)目標(biāo)類圖并計(jì)算相似性，當(dāng)相似性的值高于指定閾值σ，目標(biāo)類圖被插入候選序列.最后，從候選序列中刪除不期望的元素所在類圖.μ為相似性權(quán)重，在應(yīng)用中可以根據(jù)檢索需求進(jìn)行調(diào)整.

4 實(shí) 驗(yàn)

使用Java語言實(shí)現(xiàn)了本文所提出的檢索算法，并且在PC機(jī)(Win 10, Intel Core i7, RAM 8GB)上執(zhí)行.實(shí)驗(yàn)中使用的類圖來自3個(gè)領(lǐng)域，分別為教育、醫(yī)療和房地產(chǎn)，每個(gè)類圖中類的數(shù)目在15～25之間.所有類圖均來自公司已經(jīng)開發(fā)的項(xiàng)目，每個(gè)領(lǐng)域的類圖、目錄、特征概念以及每個(gè)目錄包含的特征結(jié)構(gòu)數(shù)量如表1所示.

表1 重用庫(kù)中UML類圖

本文做三種檢索類型(概念、結(jié)構(gòu)和混合)操作，如表2所示.每種檢索類型操作基于不同領(lǐng)域元素被執(zhí)行3次，檢索條件的設(shè)定主要從檢索元素?cái)?shù)量和分布考慮.

表2 檢索條件設(shè)定

注：括號(hào)中數(shù)字表示不允許出現(xiàn)在候選列表中的概念或結(jié)構(gòu)的數(shù)量.

提出的檢索算法和其他方法(語義檢索[6]和模型語言檢索[8])進(jìn)行比較，本文提出的檢索方法被稱為二級(jí)檢索，主要從檢索質(zhì)量和檢索效率兩個(gè)方面進(jìn)行比較.參數(shù)設(shè)置α=0.5,β=0.25,γ=0.25,σ=0.5.在三種檢索方法中，相似性計(jì)算權(quán)重μ分別被設(shè)定為1.0，0和0.5.檢索元素權(quán)重設(shè)定為平均權(quán)重.

衡量檢索質(zhì)量可以從查準(zhǔn)率P、查全率R和二者調(diào)和平均值F三個(gè)指標(biāo)來度量[12].這里設(shè)定A表示正確地出現(xiàn)在查詢結(jié)果中候選類圖的數(shù)量；B表示錯(cuò)誤地出現(xiàn)在查詢結(jié)果中候選類圖的數(shù)量；C表示應(yīng)該出現(xiàn)但沒有出現(xiàn)在檢索結(jié)果中的類圖數(shù)量.P，R和F計(jì)算公式為

平均查準(zhǔn)率P、查全率R和調(diào)和平均值F的對(duì)比分別如圖5，圖6和圖7所示.可以看出，三種檢索方法查準(zhǔn)率差別不大，如圖5所示.但查全率出現(xiàn)較大差別，特別是結(jié)構(gòu)和混合檢索，如圖6所示.綜合來看，對(duì)于概念檢索(Q1)，三種檢索方法呈現(xiàn)的結(jié)果差別不大；而對(duì)于結(jié)構(gòu)檢索(Q2)，本文提出算法和模型語言檢索得出的結(jié)果要明顯優(yōu)于語義檢索；對(duì)于混合檢索(Q3)，本文提出的算法的檢索結(jié)果要優(yōu)于其他兩種方法，如圖7所示.原因是本文的檢索算法同時(shí)考慮了語義和結(jié)構(gòu)，而其他兩種方法存在片面性.

檢索效率是指執(zhí)行檢索的響應(yīng)時(shí)間.三種檢索方法分別在不同檢索類型數(shù)據(jù)上執(zhí)行檢索所需的響應(yīng)時(shí)間如圖8所示.

可見，對(duì)于每種檢索類型，本文算法的檢索響應(yīng)時(shí)間要少于其他兩種方法.類圖檢索的響應(yīng)時(shí)間主要取決檢索元素和重用庫(kù)中目標(biāo)類圖匹配的次數(shù).本文提出的算法的匹配次數(shù)決定于重用庫(kù)中域的數(shù)、候選類圖所在域包含的結(jié)構(gòu)目錄數(shù)以及候選類圖所在結(jié)構(gòu)目錄包含的類圖數(shù)，所以匹配次數(shù)要遠(yuǎn)遠(yuǎn)少于其他兩種方法.關(guān)于重用庫(kù)中類圖分類的這部分內(nèi)容將會(huì)在接下來的工作中討論.

所以，無論從檢索質(zhì)量還是從檢索效率上，本文提出的算法都是可行的并且要優(yōu)于其他兩種方法.由于特征概念和特征結(jié)構(gòu)的引入，算法對(duì)數(shù)據(jù)量越大的存儲(chǔ)庫(kù)檢索表現(xiàn)越好.

5 結(jié) 語

本文基于軟件重用從語義和結(jié)構(gòu)兩個(gè)方面提出對(duì)UML類圖的檢索.通過本體和圖的引入，分別提出了類圖之間語義相似性和結(jié)構(gòu)相似性度量方法.基于檢索流程，提出了類圖的檢索算法.實(shí)驗(yàn)結(jié)果表明，本文提出的算法在語義、結(jié)構(gòu)和混合三種檢索類型都獲得較好的檢索質(zhì)量，特別是對(duì)結(jié)構(gòu)和混合檢索，與其他檢索方法相比具有明顯的優(yōu)勢(shì).同時(shí)，本文提出的算法的檢索效率也是可以接受的，并且優(yōu)于其他兩種方法.