朱 銳，黃 月，李 彤，馬自飛，鄭 明，湯雅惠

(1.云南大學(xué) 軟件學(xué)院，云南 昆明 650091；2.云南省軟件工程重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650091；3.云南農(nóng)業(yè)大學(xué) 大數(shù)據(jù)學(xué)院，云南 昆明 650201)

1 問題的提出

隨著業(yè)務(wù)過程管理方法、工具和實(shí)踐的日益增加，當(dāng)前制造業(yè)已經(jīng)積累了海量的業(yè)務(wù)過程模型，SAP企業(yè)的參考模型大概有600多個(gè)[1]，中國北車集團(tuán)過程模型庫中已累積約20多萬個(gè)，澳洲Suncorp銀行約有6 000多個(gè)過程模型[2]。海量業(yè)務(wù)過程模型的存儲、查詢、排序等管理均需過程模型庫[3-6](process modelrepository)的支持。

過程模型庫中存儲的海量過程模型，是既有圖形表示，又有行為語義的特殊數(shù)據(jù)，其檢索和管理比較復(fù)雜。清華大學(xué)金濤等[2]較為詳細(xì)地總結(jié)了過程模型庫檢索問題，提出“過濾—驗(yàn)證”兩階段檢索框架。過濾指通過索引過濾掉不滿足需求的過程模型，獲得候選模型集；驗(yàn)證是將候選模型集中的各個(gè)模型根據(jù)與需求的相似度進(jìn)行排序，形成一個(gè)基于模型相似度的倒排表。通過“過濾—驗(yàn)證”兩階段檢索方法返回的查詢結(jié)果通常稱為過程模型集(process model collections)。“過濾—驗(yàn)證”是當(dāng)前過程庫主流的兩階段檢索框架，為了能夠過濾過程模型，需要構(gòu)建模型索引。當(dāng)前構(gòu)建的模型索引將結(jié)構(gòu)、行為與精確、模糊查詢兩兩交叉，分為基于圖結(jié)構(gòu)的精確(相似)檢索、基于行為的精確(相似)檢索[2]4類，如圖1所示。這4類索引構(gòu)建方法基本完備地總結(jié)了模型查詢的4種類型，因此建立過程模型的索引是過程模型庫檢索問題的核心。

基于結(jié)構(gòu)的精確索引方面，Jin等[7]提出一種通過B+樹構(gòu)建索引的方法；基于結(jié)構(gòu)的模糊索引方面，Jin等[8]使用基于最大公共邊子圖的相似性度量業(yè)務(wù)過程模型的相似模型檢索；基于行為的精確索引方面，Jin等[9]提出采用序關(guān)系(ordering relation)抽取模型的行為特征作為模型索引的方法；基于行為的模糊索引方面，Zha等[10]通過變遷間的緊鄰關(guān)系(Transition Adjacent Relations, TAR)來度量模型行為相似性。近年針對過程模型索引與查詢方法，又有學(xué)者提出一些新方法。Mahleko等[11]提出一種通過有限狀態(tài)機(jī)進(jìn)行建模的業(yè)務(wù)流程索引匹配方法，評估顯示該方法的順序匹配性能較好；Hofstede等[12]定義了一種基于任務(wù)之間語義關(guān)系的過程模型查詢語言，該語言可以使用戶像建模一樣給出查詢條件；董子禾等[13]提出通過定義完整觸發(fā)序列來表示模型行為，基于A*算法結(jié)合剪枝策略對觸發(fā)序列集合進(jìn)行映射，從而完成模型的相似性計(jì)算；孫晉永等[14]借鑒標(biāo)簽Petri網(wǎng)的TAR算法，在過程模型的行為和結(jié)構(gòu)特征的基礎(chǔ)上增加了模型的語義信息，提出一種兩階段相似語義工作流檢索算法；宋金鳳等[15]為解決過程模型的相似性度量問題，對TAR算法進(jìn)行改進(jìn)，提出一種基于任務(wù)發(fā)生關(guān)系的過程模型相似性度量算法。

綜上所述，現(xiàn)有過程庫索引的建立均是在某個(gè)維度構(gòu)建單一索引，不同的查詢方式需要不同的索引，為了支持4種查詢方式，在存儲一個(gè)模型時(shí)不得不同時(shí)構(gòu)建模型的4種索引，因此給模型庫的構(gòu)建效率、模型存取速度和設(shè)計(jì)的復(fù)雜性帶來一定問題。在此背景下，本文提出結(jié)構(gòu)與行為融合的過程模型庫索引的建立與檢索方法。

2 問題背景

現(xiàn)有的模型檢索方法大都針對基于塊結(jié)構(gòu)的過程模型(Block-Structured Process Model, BSPM)。Delfmann等[16]提出一種通用模型查詢語言(General Model Query Language, GMQL)，其查詢結(jié)構(gòu)采用塊結(jié)構(gòu)表達(dá)；Rosa等[17]通過基本塊表達(dá)的過程片段對模型片段進(jìn)行變體和合并，從通用片段的過程模型集合中構(gòu)建綜合業(yè)務(wù)過程模型；Yan等[18]通過基本塊之間的組合生成海量過程模型；Jin等[8]通過計(jì)算基于塊結(jié)構(gòu)模型間的結(jié)構(gòu)相似性來計(jì)算模型相似度。上述文獻(xiàn)均在塊結(jié)構(gòu)過程模型的基礎(chǔ)上對效率進(jìn)行改進(jìn)和優(yōu)化，鮮有文獻(xiàn)對復(fù)雜結(jié)構(gòu)進(jìn)行討論，因此支持復(fù)雜結(jié)構(gòu)的檢索方法是本文工作的主要特色，所提出方法能夠同時(shí)支持模型的結(jié)構(gòu)與行為，以及具有復(fù)雜結(jié)構(gòu)模型的索引構(gòu)建與檢索。

為了融合模型的結(jié)構(gòu)與行為檢索，過程模型的索引應(yīng)具有以下特點(diǎn)：

(1)兼具描述模型結(jié)構(gòu)與行為的功能。模型的結(jié)構(gòu)與行為信息是相關(guān)聯(lián)的，孤立討論不但破壞了模型在結(jié)構(gòu)和行為之間的相關(guān)性，而且需要針對不同維度設(shè)計(jì)檢索和存儲方法，增加了過程庫管理的復(fù)雜度。

(2)對模型的整體信息進(jìn)行表達(dá)，而不只抽取模型的部分特征。模型的索引應(yīng)盡量包含模型的整體特征，部分或者片面的特征可能造成信息缺失，降低過程檢索的準(zhǔn)確度。

(3)提升模型查詢與存儲的可操作性。當(dāng)前的過程模型常用圖的形式存儲，不易對模型的數(shù)據(jù)庫進(jìn)行操作，因此需要為圖構(gòu)建對應(yīng)的結(jié)構(gòu)化模型索引，通過結(jié)構(gòu)化的索引便于快速查找和存儲模型。

現(xiàn)有過程庫主要通過為基本Petri網(wǎng)擴(kuò)展Label標(biāo)簽，并抽取圖中的元素來構(gòu)建索引，Petri網(wǎng)的結(jié)構(gòu)和行為是分開的，無法滿足上述3個(gè)支持模型結(jié)構(gòu)與行為融合檢索的索引構(gòu)建的要求。為此，引入文獻(xiàn)[19-20]中過程樹(參見定義3)的概念。過程樹通過識別活動(dòng)間的基本關(guān)系(發(fā)生權(quán)關(guān)系)，將一個(gè)基于塊結(jié)構(gòu)(block-structured)的Petri網(wǎng)轉(zhuǎn)化為一棵過程樹。過程樹的優(yōu)勢在于模型結(jié)構(gòu)清晰、結(jié)構(gòu)與行為的關(guān)系統(tǒng)一、活動(dòng)間具有確定的行為語義，以及滿足Petri網(wǎng)的基本性質(zhì)。圖2所示為將Petri網(wǎng)轉(zhuǎn)化為過程樹的示例。

雖然現(xiàn)有方法能夠用過程樹表達(dá)基本Petri網(wǎng)的結(jié)構(gòu)和行為信息，但是所能表達(dá)的Petri網(wǎng)只是基本Petri網(wǎng)的一個(gè)子集，并非所有Petri網(wǎng)都能等價(jià)地轉(zhuǎn)化為過程樹。圖3所示過程模型P1中的活動(dòng)t0和t1之間為選擇關(guān)系或并發(fā)關(guān)系，即活動(dòng)t0和t1之間的行為語義不唯一，無法用過程樹描述過程模型，雖然文獻(xiàn)[19-22]提出可以通過補(bǔ)充基本塊的方式增加過程樹的表達(dá)能力，但是仍然有某些Petri網(wǎng)無法使用過程樹進(jìn)行等價(jià)轉(zhuǎn)換。

雖然無法等價(jià)轉(zhuǎn)換，但是過程樹可以表達(dá)一個(gè)Petri網(wǎng)的部分行為特征，因此可以通過泛化Petri網(wǎng)的一些行為將某些無法等價(jià)轉(zhuǎn)化的Petri網(wǎng)轉(zhuǎn)化為過程樹。圖3所示，可以發(fā)現(xiàn)P2的行為包括P1的所有行為。目前，一種常用的泛化方式是采用花模型[23](Flower-like Model, FM)來表達(dá)復(fù)雜結(jié)構(gòu)。Leemans等[20]在歸納過程挖掘算法中引入花模型，通過花模型有效表達(dá)用基本塊無法表達(dá)的模型結(jié)構(gòu)；VAN ZELST等[24]為了解決事件流挖掘中內(nèi)存狀態(tài)有限的問題，采用花模型精簡模型中節(jié)點(diǎn)的數(shù)量，實(shí)驗(yàn)結(jié)果表明，該方法大大改善了事件流挖掘中的內(nèi)存占用問題；Tax等[25]分析了過程實(shí)施中的不確定性，認(rèn)為過程中的混亂活動(dòng)與花模型結(jié)構(gòu)非常相似，可以通過花模型對不確定的活動(dòng)進(jìn)行建模，從而過濾大量的異常行為。

綜上所述，本文根據(jù)過程模型是否能夠完全等價(jià)地轉(zhuǎn)化為過程樹，將過程模型分為能夠完全等價(jià)轉(zhuǎn)化的BSPM和部分轉(zhuǎn)化的具有復(fù)雜結(jié)構(gòu)的過程模型(Complex-Structured Process Model, CSPM)兩類，在此基礎(chǔ)上，本文主要工作如下：

(1)基于構(gòu)造性方法，證明了BSPM與過程樹之間的行為等價(jià)性。

(2)對CSPM轉(zhuǎn)化為過程樹的方法進(jìn)行研究，提出基于花模型的復(fù)雜結(jié)構(gòu)表示法。

(3)將過程樹作為過程模型庫的索引，融合模型行為與結(jié)構(gòu)，提出基于過程樹編輯距離的過程模型檢索方法。

3 基本表述

定義1過程模型[21]。一個(gè)過程模型被表示為四元組p=(C,A;F,M0)，其中：

(1)(C,A;F)是為一個(gè)網(wǎng)結(jié)構(gòu)，內(nèi)在沒有孤立元素，A∪C≠?。

(2)C為條件集，?c∈C稱為一個(gè)條件。

(3)A為活動(dòng)集，?a∈A稱為一個(gè)活動(dòng)，A中元素a的發(fā)生稱為a被執(zhí)行(或a點(diǎn)火)。

(4)F?C×A∪A×C，為過程模型上的流關(guān)系。

(5)M0(M0?C)為p的初始情態(tài)，一個(gè)d∈M0被稱為托肯。

本文采用基本網(wǎng)系統(tǒng)描述過程本質(zhì)的控制流，基本網(wǎng)系統(tǒng)的其他相關(guān)概念可參閱文獻(xiàn)[26-27]。

定義2基本塊[21]。一個(gè)基本塊可以被表示為五元組b=(C,A;F,ae,ax)，其中：

(1)(C,A;F)為一個(gè)過程的網(wǎng)結(jié)構(gòu)。

(2)ae,ax∈A分別為基本塊的入口活動(dòng)和出口活動(dòng)。

常見的基本塊一般包括4種結(jié)構(gòu)[19,28]，但只要符合上述定義就可以不斷補(bǔ)充，因此本文將基本結(jié)構(gòu)擴(kuò)展為順序塊、選擇塊、并發(fā)塊、迭代塊、同或塊5種，如圖4所示。

定義3過程樹[21]。定義過程樹的步驟如下：

(1)活動(dòng)a∈A∪{τ}為一個(gè)過程樹，其中A為過程模型p=(C,A;F,M0)的活動(dòng)集。

(2)設(shè)M1,M2,…,Mn(n>0)為n個(gè)過程樹，過程樹間的關(guān)系符號記為⊕，則⊕(M1,M2,…,Mn)為過程樹。

針對5種基本塊，定義順序(→)、選擇(×)、并發(fā)(∧)、迭代(∝)、同或(∨)5種關(guān)系符號，符號⊕表示關(guān)系符號集{→,×,∧,∨,∝}中的一種。有關(guān)過程樹更多的概念可參考文獻(xiàn)[20-21]。

定義4過程模型的行為空間。設(shè)p=(C,A;F,M0)是一個(gè)過程模型，σ?A*為過程模型p上的一個(gè)變遷序列，則p上所有可能發(fā)生的變遷序列的集合稱為p行為空間，記為Π(p)，則σ∈Π(p)。

4 復(fù)雜結(jié)構(gòu)與過程模型索引的建立

4.1 BSPM與過程樹的行為等價(jià)性

為了證明BSPM與過程樹的行為等價(jià)性，首先給出如下定義：

定義5活動(dòng)細(xì)化。設(shè)p=(C,A;F,M0)為一個(gè)過程模型，b=(C,A;F,ae,ax)為一個(gè)基本塊，采用基本塊b細(xì)化過程模型p中活動(dòng)a后得到過程模型p′，記為p′=Refine(p.a,b)，則一次細(xì)化操作的步驟如下：

(1)p′.C=p.C∪b.C。

(2)p′.A=p.A-{a}∪b.A。

(3)p′.F=(p.F-out(a)-in(a))∪b.F∪{(x,y)|y∈b.ae∧(x,t)∈in(a)}∪{(x,y)|(a,y)∈out(a)∧x∈b.ax}。

(4)p′.M0=p.M0。

其中，對于?a∈A，活動(dòng)a的輸入流in(a)={(x,a)|(x,a)∈F∧x∈C}，輸出流out(a)={(a,x)|(a,x)∈F∧x∈C}。

該算法用基本塊替換過程中的一個(gè)活動(dòng)，在過程活動(dòng)細(xì)化后，過程的“輪廓”一致[22]。

定義6過程化簡。設(shè)p=(C,A;F,M0)為一個(gè)過程模型，若p中存在若干活動(dòng)滿足基本塊所定義的基本關(guān)系，則設(shè)p中對應(yīng)的基本塊b=(C,A;F,ae,ax)，將基本塊b化簡為活動(dòng)a后得到過程模型p′，記為p′=Simplify(p.b,a)，則一次化簡操作的步驟如下：

(1)p′.C=p.C-b.C。

(2)p′.A=p.A-b.A∪{a}。

(3)p′.F=(p.F-in(b.ae)-out(b.ax))∪{(x,y)|(x,t)∈in(b.ae)∧y∈a}∪{(x,y)|x∈a∧(b.ax,y)∈out(a)}。

(4)p′.M0=p.M0。

定義7過程重構(gòu)。將活動(dòng)細(xì)化與過程化簡統(tǒng)稱為過程重構(gòu)。

過程重構(gòu)的本質(zhì)是不斷用基本塊層次化地替換活動(dòng)，其基本思想如圖5所示。

定義8BSPM。設(shè)初始過程模型為p=(C,A;F,M0)，其中C={ce,cx},A={a},F={(ce,a),(a,cx)},M0={ce}，則通過以下操作獲得的過程模型p=(C′,A;F′,M0)稱為BSPM：

(1)pr=Refine(p.a,b)為一個(gè)BSPM。

(2)ps=Simplify(p.b,a)為一個(gè)BSPM。

(3)重復(fù)(1)或(2)操作有限次，所獲得的模型p′為一個(gè)BSPM。

定義8用基本塊替換過程中的一個(gè)活動(dòng)，在過程活動(dòng)細(xì)化或過程化簡后，需要證明重構(gòu)前后被重構(gòu)的部分在“輪廓上保持一致”，即模型中被替換部分與待替換部分在邊緣上一致。

定理1對于BSPM，如果存在M，M′?p.C使得M[t>M′(t∈p.A)，則存在一個(gè)步序列G1,G2,…,Gn-1(G0,G1,…,Gn-1?p′.A)和一組情態(tài)c1,c2,…,cn?p′.C，使得M[G1>c1,c1[G2>c2,…,cn-1[Gn-1>M′。

證明因?yàn)镸[t>M′，所以M[b.ae>c1。對于基本塊內(nèi)部，由于所有基本塊均為單入口單出口，容易證明基本塊內(nèi)部能夠被完全執(zhí)行，使得[b.ax>M′。因此必然存在一個(gè)步序列G1,G2,…,Gn-1(G0,G1,…,Gn-1?p′.A)和一組情態(tài)c1,c2,…,cn?p′.C，使得M[G1>c1,c1[G2>c2,…,cn-1[Gn-1>M′。證畢。

由定理1可知，重構(gòu)前后過程模型在執(zhí)行語義層面是一致的。

定義9BSPM與過程樹的行為等價(jià)。設(shè)p是一個(gè)BSPM，t是p對應(yīng)的過程樹。p與t之間的行為是等價(jià)的(記為peqt)，當(dāng)且僅當(dāng)：

其中，σ表示過程模型p或過程樹t的一個(gè)行為。peqt表示過程模型p中所有出現(xiàn)的行為一定會在過程樹t中出現(xiàn)，反之亦然。

定理2設(shè)p為通過重構(gòu)操作獲得的BSPM，則必然存在一個(gè)過程樹t，使得peqt。

證明設(shè)初始過程模型為p0=(C,A;F,M0)，其中C={ce,cx},A={a},F={(ce,a),(a,cx)},M0={ce}，此時(shí)因?yàn)橹挥谐跏蓟顒?dòng)a，所以對應(yīng)的過程樹只有一個(gè)節(jié)點(diǎn)a，即初始過程模型為p0必然對應(yīng)一棵過程樹t0，且p0eqt0。

對過程模型p0重構(gòu)n-1次后，獲得過程模型pn-1，對應(yīng)過程樹tn-1，設(shè)pn-1eqtn-1。

對過程模型pn-1：

(1)若對活動(dòng)s用基本塊b=(C,A;F,ae,ax)進(jìn)行細(xì)化操作，則pn=Refine(pn-1.s,b)，該基本塊對應(yīng)的活動(dòng)ai,aj滿足基本關(guān)系，記為ai⊕aj，則tn=tn-1-s∪{ai⊕aj}，此時(shí)tn唯一確定，且pneqtn。

(2)若將過程模型pn-1中的基本塊b化簡為活動(dòng)s后得到過程模型pn，則pn=Simplify(p.b,s)，同理可得pneqtn。綜上，對過程模型pn-1無論細(xì)化還是化簡操作，重構(gòu)后的過程模型pneqtn。

定義10復(fù)雜結(jié)構(gòu)。一個(gè)復(fù)雜結(jié)構(gòu)s為一個(gè)過程片段，該過程片段無法通過初始活動(dòng)a0有限次地采用基本塊和過程重構(gòu)操作得到。

包含復(fù)雜結(jié)構(gòu)的例子如圖3中P1所示，該模型無法用基本塊有限次重構(gòu)操作獲得。

4.2 過程模型索引的構(gòu)建方法

對于數(shù)據(jù)庫而言，索引意味著檢索速度和效率。有別于傳統(tǒng)數(shù)據(jù)庫，過程庫過程層中存儲的是過程模型，其可以基于圖、關(guān)聯(lián)矩陣或某種描述語言，例如采用PNML描述過程模型，無論哪種方法，都描述了模型中元素間的結(jié)構(gòu)關(guān)系，這些結(jié)構(gòu)關(guān)系只能用于展示圖形，無法表達(dá)模型的行為語義和特征。

正如前文所述，過程樹是一種方便快捷表達(dá)過程模型語義的方法，然而其能表達(dá)的語義有限，大量復(fù)雜的過程模型的語義無法表達(dá)，即無法構(gòu)造一個(gè)和原模型的行為具有互模擬的基于塊的過程模型。如圖6上半部模型為具有順序關(guān)系的活動(dòng)s和活動(dòng)t，右半部虛線框中，活動(dòng)a,b,c,d,e構(gòu)成一個(gè)無法用基本塊表達(dá)的復(fù)雜模型，其中活動(dòng)d和活動(dòng)e處于一個(gè)非自由選擇結(jié)構(gòu)，即兩個(gè)活動(dòng)間的選擇不是由過程模型的某個(gè)節(jié)點(diǎn)決定，而是可能依賴過程模型的其他部分，這種非局部行為無法用二元關(guān)系描述。因此，在建立索引時(shí)需將無法用基本塊描述的結(jié)構(gòu)轉(zhuǎn)化為花模型，圖6下半部虛線框中的部分，花模型能夠模擬一切與其活動(dòng)集相同的過程模型的行為，反之則不行(即無法互模擬)。

花模型雖然泛化度較高，但是其他兩個(gè)質(zhì)量維度——擬合度和簡潔度都非常好。同時(shí)，通過花模型可以用過程樹對具有復(fù)雜結(jié)構(gòu)的過程模型進(jìn)行抽象，但是需要通過定義某種語義符號表示活動(dòng)間所具有的花模型語義。下面在本文過程樹語義定義的基礎(chǔ)上給出花模型語義的定義，設(shè)L為事件日志，花模型關(guān)系符號為○*，L(○*(M1,…,Mn))表示由過程樹M1,…,Mn組成的任意關(guān)系，圖7所示為L(○*(→(s,f),∨(g,t))對應(yīng)的過程樹。

采用花模型能夠有效地用過程樹表示復(fù)雜結(jié)構(gòu)，從而可以用過程樹作為一個(gè)一般過程模型的索引，這種索引不是唯一索引，而是對過程模型特征的抽取。例如，只要是由兩個(gè)具有順序關(guān)系的活動(dòng)s，t以及具有花模型關(guān)系的5個(gè)活動(dòng)a，b，c，d，e組成的復(fù)雜結(jié)構(gòu)，都能用圖6下半部的模型P6表示，通過建立這樣的索引能夠有效地對待檢索模型的數(shù)量進(jìn)行過濾。下面給出將一般過程模型轉(zhuǎn)化為過程樹的算法：

算法1過程模型轉(zhuǎn)化為過程樹。

輸入：過程p=(C,A;F,M0)。

輸出：過程樹集processTrees。

processToPTree(p)

1.if(p.A.size equlas 0 or 1)

2. return;

3.foreach(A a:p.A){

4. foreach(A b:p.A){

5.if(beChoice(a,b))then pTree=buildATree(×,a,b);//構(gòu)造選擇子樹

6.else if(beSequnence(a,b))then pTree=buildATree(→,a,b);//構(gòu)造順序子樹

7. else if(beConcurrency(a,b))then pTree=buildATree(∧,a,b);//構(gòu)造并發(fā)子樹

8. else if(beIteration(a,b))then pTree=buildATree(∝,a,b);//構(gòu)造迭代子樹

9. else if(beAndOR(a,b))then pTree=buildATree(∨,a,b);//構(gòu)造同或子樹

10. processTrees=processTrees∪{pTree};

11. NG=updateGraph(p,pTree);

12. processToPTree(p);

13. }

14.}

15.if(p.A.size()>0){//剩下復(fù)雜結(jié)構(gòu)

16. pTree=buildATree(○*,p.A);//構(gòu)造花模型子樹

17. processTrees=processTrees∪{pTree};

18. return;}

將算法1不斷迭代，若結(jié)果未存在任何活動(dòng)，則說明過程模型能等價(jià)地表示為BSPM；若結(jié)果剩余有活動(dòng)，則說明這些活動(dòng)間的關(guān)系為復(fù)雜結(jié)構(gòu)，需要利用花模型子樹進(jìn)行表達(dá)。過程模型在轉(zhuǎn)化過程中保留的特征(基本塊)越多越好，因此盡可能將過程模型中能夠使用基本塊表達(dá)的部分都進(jìn)行表達(dá)。

5 基于過程樹編輯距離的過程模型相似性度量

在表達(dá)一個(gè)過程模型的索引后，需對其進(jìn)行查詢，因?yàn)樗饕谶^程樹，所以對過程樹的相似性進(jìn)行度量?；诮Y(jié)構(gòu)的查詢方式效率較低，目前研究較多的是對過程模型行為的檢索。本文用過程樹表示過程模型的優(yōu)勢在于過程樹既包含結(jié)構(gòu)又具有行為，而且可以用表達(dá)式表示，能夠采用已有的表達(dá)式處理方法進(jìn)行快速匹配。對過程模型進(jìn)行查詢時(shí)，需要度量模型的相似度，本文采用基于樹的編輯距離的方法對兩個(gè)過程樹間的相似度進(jìn)行度量。

樹編輯距離由字符串編輯距離演化而來，是一種有效的樹(或森林)間相似性度量方法[29]。該方法每次對樹的編輯操作設(shè)定開銷函數(shù)，計(jì)算將一棵樹T1轉(zhuǎn)變?yōu)榱硪豢脴銽2的最低開銷，即為樹的編輯距離，記為δ(T1,T2)。

定義11過程樹編輯距離。設(shè)過程p1,p2轉(zhuǎn)化后的過程樹分別為T1,T2，則T1,T2間的編輯距離為將T1轉(zhuǎn)化為T2的所有基本操作的最小開銷的總和，記作δ(T1,T2)。其中過程樹間轉(zhuǎn)化的基本操作包括刪除節(jié)點(diǎn)和修改節(jié)點(diǎn)兩種操作，刪除節(jié)點(diǎn)m的開銷記作γdelete(m)，將節(jié)點(diǎn)m修改為n的開銷記作γrelabel(m,n)，對節(jié)點(diǎn)m的修改操作指對節(jié)點(diǎn)m中的標(biāo)簽進(jìn)行修改。

需要說明的是，在T1樹上增加操作等價(jià)于在T2樹上的刪除操作，因此在計(jì)算編輯距離時(shí)，可以只定義刪除和修改兩種操作來將過程樹T1轉(zhuǎn)化為T2。Zhang等[30]提出并證明了一種時(shí)間算法復(fù)雜度為O(|T1|×|T2|×min(depth(T1),leaves(T1))×min(depth(T2),leaves(T2)))的動(dòng)態(tài)遞歸算法，其中：|T1|為樹T1的規(guī)模，即節(jié)點(diǎn)數(shù)量；depth(T1)為樹T1的深度；leaves(T1)為樹T1的葉節(jié)點(diǎn)的數(shù)量。該算法非常經(jīng)典，Klein等[31]又對該算法進(jìn)行改進(jìn)。下面對算法的預(yù)備知識進(jìn)行說明，樹是森林的特殊情況，而且一棵樹去掉根節(jié)點(diǎn)將變?yōu)橐粋€(gè)森林，該算法需要對森林進(jìn)行迭代，因此需要對森林進(jìn)行定義。設(shè)D為一個(gè)森林，v為D中的一個(gè)節(jié)點(diǎn)，D-v表示從樹D刪除節(jié)點(diǎn)v后剩下的森林，D-T(v)表示從樹D刪除以節(jié)點(diǎn)v為根節(jié)點(diǎn)的子樹T(v)后剩下的森林，D-表示刪除D根節(jié)點(diǎn)后剩下的森林，用right(D)表示森林D中最右邊樹的根節(jié)點(diǎn)，則兩個(gè)D1,D2森林之間的編輯距離δ(D1,D2)的遞歸計(jì)算如下，其中若D為一棵樹，則將刪除D的根節(jié)點(diǎn)后得到的森林記作D-：

δ(?,?)=0；

(1)

δ(D1,?)=δ(D1-right(D1),?)+

γdelete(right(D1))；

(2)

δ(?,D2)=δ(?,D2-right(D2))+

γdelete(right(D2))；

(3)

δ(D1,D2)=min

(4)

圖8所示為一棵過程樹與另一棵過程樹之間的映射關(guān)系。設(shè)刪除節(jié)點(diǎn)m的操作開銷γdelete(m)=w，則將節(jié)點(diǎn)m轉(zhuǎn)換為n的操作開銷γrelabel(m,n)=h，最小開銷的計(jì)算過程如表1所示。

表1 過程樹最小開銷的執(zhí)行過程

續(xù)表1

經(jīng)過該執(zhí)行過程可知T1和T2之間的編輯距離為2w+4h，實(shí)際執(zhí)行的迭代過程要復(fù)雜很多，該例僅計(jì)算了兩棵樹T1和T2結(jié)構(gòu)間的編輯距離。

在計(jì)算過程樹相似度的實(shí)際應(yīng)用中，還需要度量過程樹葉節(jié)點(diǎn)間的相似性。過程樹的葉節(jié)點(diǎn)均為活動(dòng)，非葉節(jié)點(diǎn)均為操作符。對于葉子節(jié)點(diǎn)而言，因?yàn)榇鎯Φ木鶠榛顒?dòng)名，采用字符串表達(dá)，所以為了對字符串的相似性進(jìn)行匹配，本文采用文獻(xiàn)[32-34]基于近義詞的匹配方法，定義過程樹葉節(jié)點(diǎn)的相似度。

定義12過程樹葉節(jié)點(diǎn)相似度。設(shè)過程p對應(yīng)的過程樹為pTree，其中a,b∈p.A為過程p中的活動(dòng)，la為pTree中活動(dòng)a的名字，可知la和lb均為字符串，設(shè)字符串la和lb所含單詞構(gòu)成的多重集(可包含相同元素)分別為fa和fb，則兩個(gè)過程樹葉節(jié)點(diǎn)間的相似度

simLeaf(la,lb)=

(5)

式中：synonym(m,n)表示單詞m和n是否為同義詞，是則返回1，否則為0；m∈fafb表示m屬于fa但不屬于fb；ωi為相同詞的權(quán)重，ωj為近義詞的權(quán)重，參考文獻(xiàn)[33]的推薦，一般設(shè)定為1和0.75；在考慮過程樹節(jié)點(diǎn)上的文本時(shí)，本文通過斯坦福CoreNLP[35]對每個(gè)單詞進(jìn)行規(guī)范化處理。例如，la={p,q,c,c}，lb={c,x,x}且已知p和x為近義詞，則simLeaf(la,lb)=(1+0.75×(1))/7=0.25。在計(jì)算過程樹編輯距離中，有可能會出現(xiàn)兩個(gè)葉節(jié)點(diǎn)不完全相似的情況，因此兩個(gè)葉節(jié)點(diǎn)a,b之間的修改開銷γrelabel(a,b)應(yīng)該與其之間的相似度成反比，故定義兩個(gè)葉節(jié)點(diǎn)之間的修改開銷γrelabel(a,b)=t(1-simLeaf(la,lb))，t為常數(shù)。

除了葉節(jié)點(diǎn)之間的相似性外，還要度量葉節(jié)點(diǎn)與非葉節(jié)點(diǎn)以及非葉節(jié)點(diǎn)間的相似性，由于非葉結(jié)點(diǎn)存儲的均為過程操作符，其相似性比較容易度量。

定義13過程樹葉節(jié)點(diǎn)與非葉節(jié)點(diǎn)以及非葉節(jié)點(diǎn)間的相似度。設(shè)過程p對應(yīng)的過程樹為pTree，na和nb分別為pTree中兩個(gè)節(jié)點(diǎn)，且兩個(gè)節(jié)點(diǎn)不能同時(shí)為葉節(jié)點(diǎn)，na和nb均為字符串，則na和nb間的相似度

(6)

通過對過程樹相似性進(jìn)行度量，發(fā)現(xiàn)過程樹的節(jié)點(diǎn)對度量結(jié)果產(chǎn)生了影響，因此需要對過程樹間的編輯距離進(jìn)行歸一化，兩棵完全不相似的過程樹間的編輯距離將達(dá)到最大值，下面對過程樹編輯距離相似度進(jìn)行定義。

定義14過程樹編輯距離相似度。設(shè)過程p1,p2轉(zhuǎn)化后的過程樹分別為T1,T2，則其之間的過程樹編輯距離相似度

(7)

6 案例及原型系統(tǒng)的實(shí)現(xiàn)

6.1 過程庫原型系統(tǒng)

本文設(shè)計(jì)并實(shí)現(xiàn)用于案例驗(yàn)證的過程庫檢索(Process Model Query, PMQ)原型系統(tǒng)，體系結(jié)構(gòu)(如圖9)主要分為用戶接口層、功能服務(wù)層和基礎(chǔ)層3層。針對當(dāng)前大部分過程建模和挖掘系統(tǒng)(ProM[36]，Disco[37]，PIPE[38])均采用客戶機(jī)/服務(wù)器(Client/Server, C/S)架構(gòu)，導(dǎo)致配置復(fù)雜、系統(tǒng)臃腫、安裝復(fù)雜、運(yùn)行速度慢、用戶體驗(yàn)差等缺點(diǎn)，整個(gè)系統(tǒng)采用瀏覽器/服務(wù)器(Browser/Server, B/S)架構(gòu)，功能以Web Service的形式進(jìn)行封裝，前端將采用HTML5進(jìn)行展示。

用戶接口層主要用于系統(tǒng)和用戶之間交互，包括過程庫的日志抽取器、過程挖掘器、過程樹編輯器和過程查詢器。功能服務(wù)層涵蓋了數(shù)據(jù)視圖構(gòu)建、過程挖掘和過程庫管理等功能。功能服務(wù)層中的挖掘服務(wù)包括過程引擎服務(wù)及與過程樹相關(guān)的服務(wù)，需要完成過程可視化、過程執(zhí)行、過程樹編輯、過程模型與過程樹直接轉(zhuǎn)化等服務(wù)。過程庫管理服務(wù)主要為已挖掘的過程模型建立高效的索引，并對其進(jìn)行存儲和檢索?；A(chǔ)層主要關(guān)注過程挖掘中用到的基礎(chǔ)數(shù)據(jù)或工具，包括過程事件日志庫、過程庫，以及開源工具ProM和PIPE的支持。存儲于事件日志庫中的事件主要采用過程挖掘事件日志格式XES[39]。

6.2 案例研究

6.2.1 建立模型索引的案例分析

(1)案例說明

圖10所示為3個(gè)軟件的開發(fā)過程，其中P1為認(rèn)證授權(quán)軟件SIS的設(shè)計(jì)和實(shí)現(xiàn)過程，為了與該過程進(jìn)行對比來詳細(xì)說明本文所提方法，再次設(shè)計(jì)過程P2和P3，分別評估活動(dòng)名間和結(jié)構(gòu)間的相似度。從P1到P2的變化過程中，活動(dòng)名稱均未改變，只是最后在P1的基礎(chǔ)上添加復(fù)雜模塊，該模塊無法用過程樹表達(dá)。從P1到P3的變化過程中，活動(dòng)Design Evolution變?yōu)镋volution，Review變?yōu)镈esign Review，Kernel Algorithm Implementation變?yōu)镕unction Coding，User Interface Implementation變?yōu)閁I Coding，其中Implementation和Coding為近義詞，Interface和UI為近義詞。

(2)索引構(gòu)建過程及結(jié)果

用過程樹建立過程模型P1，P2，P3的索引，采用4.2節(jié)的索引構(gòu)建方法，通過重復(fù)執(zhí)行算法1得到活動(dòng)兩兩之間的行為關(guān)系來發(fā)掘活動(dòng)間的特征。以P1為例，活動(dòng)Design和Design Evolution之間為迭代塊，表示為過程樹∝(Design，Design Evolution)；然后通過過程重構(gòu)將∝(Design，Design Evolution)重構(gòu)為一個(gè)活動(dòng)，并判斷與活動(dòng)Review之間為順序關(guān)系，表示為→(∝(Design，Design Evolution), Review)；接著判斷Kernael Algorithm Implementation與User Interface Implementation之間為并發(fā)關(guān)系，表示為∧(Kernael Algorithm Implementation,User Interface Implementation)；判斷→(∝(Design，Design Evolution), Review)和∧(Kernael Algorithm Implementation,User Interface Implementation)之間為順序關(guān)系，表示為→(→(∝(Design，Design Evolution), Review),∧(Kernael Algorithm Implementation,User Interface Implementation))；再次為順序結(jié)構(gòu)：→(→(→(∝(Design，Design Evolution),Review),∧(Kernael Algorithm Implementation,User Interface Implementation)),Integration)。通過上述過程，最終建立的過程樹T1，T2，T3如圖11所示。

需要說明的是，在具體算法中，判斷算法更加復(fù)雜。因?yàn)楸疚闹攸c(diǎn)是闡述通過過程樹能夠構(gòu)建索引，以及檢索方法的基本原理，所以算法的詳細(xì)實(shí)現(xiàn)不再贅述，功能可在過程庫檢索原型系統(tǒng)PMQ上測試。

(3)過程樹編輯距離計(jì)算方法

度量過程樹的編輯距離時(shí)，可以先度量T1和T3過程樹間的相似性，再度量T1和T2，其中T2是在T1的基礎(chǔ)上增加了一個(gè)復(fù)雜結(jié)構(gòu)，其在轉(zhuǎn)化為過程樹時(shí)被轉(zhuǎn)化為一個(gè)花型結(jié)構(gòu)。通過本文所述方法，假定p=1，t=2，則刪除節(jié)點(diǎn)m的操作開銷γdelete(m)=1，γrelabel(m,n)=2(1-simLeaf(la,lb))。首先計(jì)算葉子節(jié)點(diǎn)的相似性，得simLeaf(“User Interface Implementation”,“UI Coding”)=0.3，simLeaf(“Kernel Algorithm Implementation”,“Function Coding”)=0.15，simLeaf(“Review”,“Desgin Review”)=0.5，simLeaf(“Design Evolution”,“Evolution”)=0.5；然后計(jì)算編輯距離，得δ(T1,T2)=5，δ(T1,T3)=5.1；最后計(jì)算過程樹間的相似度，得simTree(T1,T2)=0.706，simTree(T1,T3)=0.575?？芍猅1,T2之間更加相似，原因是將γrelabel操作的系數(shù)設(shè)為2，即認(rèn)為重命名的開銷是刪除節(jié)點(diǎn)開銷的兩倍。由于重命名的開銷大于刪除節(jié)點(diǎn)的開銷，導(dǎo)致重命名操作對模型的影響大于結(jié)構(gòu)修改操作對模型的影響。

6.2.2 過程檢索案例

(1)案例說明

過程庫模型檢索功能的基本原理是首先給定過程查詢語言，然后計(jì)算基于過程樹的過程索引間的相似性，最后獲取和過濾滿足查詢條件的過程模型。本案例將ISO/IEC 12207標(biāo)準(zhǔn)提出的軟件維護(hù)過程[40]進(jìn)行擴(kuò)展，建立過程P4說明模型檢索的實(shí)現(xiàn)步驟，如圖12所示。

(2)檢索結(jié)果

過程P4已經(jīng)存儲在PMQ系統(tǒng)中，為了通過軟件過程庫獲取該過程模型，需要在過程查詢器界面輸入查詢條件。查詢過程是先計(jì)算查詢條件與該過程模型對應(yīng)的過程索引之間的相似性，再返回相似度最高的查詢結(jié)果，當(dāng)輸入查詢條件為“→(Process Implementation,∧(Problem Analysis, Risk Analysis))”時(shí)，PMQ查詢結(jié)果如圖13所示，該原型系統(tǒng)的部分功能已經(jīng)上線。

7 結(jié)束語

過程模型索引構(gòu)建方法常根據(jù)結(jié)構(gòu)和行為劃分，導(dǎo)致索引構(gòu)建方法需要針對不同的底層架構(gòu)設(shè)計(jì)，因此復(fù)雜而繁瑣。過程樹是一種能夠同時(shí)表達(dá)結(jié)構(gòu)和行為的數(shù)據(jù)結(jié)構(gòu)，其不能表示所有過程模型，比較適合用作過程模型的索引。一方面，過程樹中同時(shí)融合了結(jié)構(gòu)和行為信息，不需要再針對結(jié)構(gòu)或行為單獨(dú)構(gòu)建索引；另一方面，過程樹結(jié)構(gòu)簡單、合理、易于理解，能夠保持良好的性質(zhì)，可以在樹結(jié)構(gòu)和表達(dá)式間等價(jià)快速地轉(zhuǎn)化并保持語義信息，其特點(diǎn)是容易進(jìn)行過程庫的各類管理操作。然而，由于并不是所有過程模型都能用過程樹描述，本文提出采用花模型表達(dá)模型中的復(fù)雜結(jié)構(gòu)，并將過程樹作為過程模型的索引。在此基礎(chǔ)上，度量過程模型相似性時(shí)，可以將其索引(過程樹)之間的編輯距離作為相似度的評判標(biāo)準(zhǔn)，最終解決過程模型的索引和相似性度量問題。

未來工作將進(jìn)一步優(yōu)化過程模型的檢索效率。雖然在過程庫量級較少時(shí)采用過程樹編輯距離可以取得較好的效果，但是隨著過程庫中模型存儲數(shù)量的遞增，需要逐個(gè)計(jì)算待查詢模型的相似度，導(dǎo)致檢索效率較低。因此，對模型進(jìn)行并行檢索是未來的研究方向。另外，過程模型還包含有組織維、信息維、資源維等多維信息，過程庫不應(yīng)僅存儲控制流信息，在現(xiàn)有過程庫的基礎(chǔ)上增加模型的其他維度信息，并進(jìn)行多維度過程庫檢索也是下一步需要考慮的內(nèi)容。