鄧雅方，林雷蕾，聞立杰+，劉璦瑋，錢 忱，王建民

(1.清華大學 軟件學院，北京 100084;2.首都師范大學 管理學院，北京 100048)

0 引言

業(yè)務過程管理(Business Process Management, BPM)在信息化時代具有顯著提高生產(chǎn)力和節(jié)約成本的作用，其中無論過程挖掘(process mining)還是過程建模(process modeling)領域，都需要量化過程模型的行為。例如，對已有模型進行質(zhì)量檢查，即合規(guī)性檢查，將事件日志與過程模型的行為進行對比，找出相同點和差異，發(fā)現(xiàn)過程模型存在的偏差，分析偏差原因并對過程模型進行改進或者調(diào)整偏差，使過程模型更符合實際。同時，合規(guī)性檢查還可以度量過程發(fā)現(xiàn)算法的效果[1-2]，其主要依賴4個質(zhì)量標準[3]，即擬合度、精確度、泛化度和簡潔度，其中精確度衡量模型中所有行為是否在日志中出現(xiàn)，為此需要先從模型中計算出模型所有可能的行為(即軌跡變體的數(shù)量)。類似地，在隱式真實性測量[4](implicit realism measure)中，也常用模型中路徑的數(shù)量來計算模型中某些行為未出現(xiàn)在日志中的概率。另外，模型中的行為量還可以代替模型的復雜度，通過計算過程模型不同軌跡長度對應的軌跡數(shù)量來量化過程模型行為，可以更容易地對過程模型進行復雜度評估。

計算過程模型中的行為量(本文將其量化為軌跡變體的數(shù)量)是一項具有挑戰(zhàn)的任務，尤其是對非結構化模型。如果只是簡單遍歷所有路徑得到軌跡數(shù)，則很可能遇到路徑組合爆炸式增長，尤其當軌跡數(shù)較大時，如過程模型中含復雜的并行結構、包含性“或”(OR)結構和復雜循環(huán)結構的情況。目前，現(xiàn)有研究集中在塊結構過程模型的軌跡數(shù)計算方法[5]，缺乏計算非結構化模型軌跡的研究，而挖掘得到的模型大部分是非結構化的，因此對非結構化過程模型軌跡計數(shù)方法進行研究，顯得十分必要。同時，如何快速、正確地計算出任意過程模型不同長度軌跡的數(shù)量，是計算軌跡數(shù)的難點。基于以上背景，本文主要研究對過程模型各種基本和復雜結構都能適用的軌跡計數(shù)方法，由于非結構化過程模型更加復雜且無規(guī)律，需要重點解決非結構化過程模型的軌跡計數(shù)問題。

針對上述問題，本文在已有工作基礎上對過程模型軌跡的長度與數(shù)量計算方法進行研究，并給出相應的實驗評估。主要貢獻包括：

(1)給出對過程模型解析生成的精煉過程結構樹(Refined Process Structure Tree, RPST)的遞歸遍歷軌跡計數(shù)方法。

(2)對可以結構化的過程模型，提出其對應的軌跡計數(shù)方法，包括對非結構化過程模型轉結構化方法的預處理和后處理，處理后能夠更好地將現(xiàn)有結構化方法組合，結構化后再用塊結構過程模型的軌跡計數(shù)方法進行計算；同時設計了簡單半塊結構過程模型的軌跡長度和數(shù)量計算方法。

(3)對于不可結構化的過程模型，其中復雜的非自由選擇結構部分采用完全前綴展開技術，對Petri網(wǎng)展開后結果的無循環(huán)部分調(diào)用祖先抖動算法進行結構化，有循環(huán)部分進行循環(huán)歸約計算，使非結構化的部分不再出現(xiàn)，從而計算出軌跡數(shù)。

(4)對本文過程模型軌跡的長度和數(shù)量計算方法進行測試與評估，分別在人工合成的數(shù)據(jù)集、公開數(shù)據(jù)集以及相關工作評估使用的數(shù)據(jù)集上進行測試。

1 動機案例

1.1 非結構化過程模型軌跡計數(shù)示例

如圖1所示，交叉同步結構是一種非結構化的過程模型，以一個Petri網(wǎng)表示的簡單交叉同步結構為例，在兩個并行分支ac和bd中存在交叉同步，即并行執(zhí)行兩個分支的同時，要求節(jié)點a先于節(jié)點d執(zhí)行，可能的發(fā)生序列有a,c,b,d，a,b,d,c，a,b,c,d，b,a,d,c，b,a,c,d5種，一種發(fā)生序列看作為一條軌跡，其長度為發(fā)生序列中包含的任務數(shù)，因此有5條長度為4的軌跡。圖中：節(jié)點i為源庫所，節(jié)點o為匯庫所；填充黑色的方框為一種特殊的任務，稱為不可見任務，該任務不出現(xiàn)在發(fā)生序列中，其軌跡長度為0。

圖2所示為4種非塊結構過程模型的例子，其軌跡數(shù)分別為8，19，2，3。其中，圖2b任意循環(huán)結構含有的兩個循環(huán)之間存在交叉，如果限定最大循環(huán)次數(shù)為2，則這兩個循環(huán)的循環(huán)次數(shù)都有0，1，2三種可能，對兩個循環(huán)的不同循環(huán)次數(shù)排列組合共9種情況，還需要考慮在每種排列組合下兩個循環(huán)的先后遍歷問題，例如a,b,c,e,f,c,d,b,c,d,b,c,e,g和a,b,c,d,b,c,e,f,c,d,b,c,e,g都是循環(huán)變遷d兩次，循環(huán)變遷f一次，遍歷先后順序不同，發(fā)生序列就不同；圖2c非自由選擇結構可能的發(fā)生序列有a,c,d，b,c,e兩種；圖2d任意跳轉結構可能的發(fā)生序列為a,d，b,e，a,c,e3種。

1.2 問題分析

過程模型軌跡數(shù)指過程模型可能的發(fā)生序列數(shù)，如圖2中4種非結構化過程模型的總軌跡數(shù)分別為其可能的發(fā)生序列數(shù)，即總軌跡數(shù)分別為8，19，2，3。其中，對于循環(huán)結構，由于無限循環(huán)的情況對軌跡計數(shù)沒有意義，本文只討論有限次的循環(huán)行為，即對循環(huán)結構限制了最大循環(huán)次數(shù)k，用戶可指定參數(shù)k的大小，一般為2或3(本文默認k=2)。另外，文獻[6]通過公平假設(fairness assumption)規(guī)定一個流程中的一個任務不能被無限期地推遲，并證明無限循環(huán)行為被認為是不現(xiàn)實的。

軌跡長度指某軌跡中執(zhí)行的任務數(shù)，即某個發(fā)生序列中含有的變遷(transitions)數(shù)，一個變遷長度為1，例如一個過程模型的某個發(fā)生序列為a,b，即1條長度為2的軌跡。注意有一種特殊的變遷，不可見任務[7](也稱靜默活動)擁有變遷的能力，但在計算軌跡長度時不算在變遷數(shù)中，即是長度為0的變遷，為了區(qū)分不可見任務與其他變遷，常用填充為黑色的方框表示不可見任務，如圖1所示。

已知的非結構化過程模型主要包括非對稱分裂合并、任意循環(huán)、非自由選擇[8]、任意跳轉和交叉同步結構5種結構。需要說明的是，現(xiàn)有研究對結構化模型(也稱塊結構模型)有明確的定義(如文獻[9])，即對于每個有多條出邊的分裂(split)節(jié)點，總存在一個有相同數(shù)量入邊的同類型合并(join)節(jié)點與之對應，在塊結構之間可以嵌套表達。然而，由于非結構化模型的包含情況十分繁雜，目前對其尚未有明確的定義。相比結構化過程模型，非結構化過程模型更不容易找到統(tǒng)一計算軌跡數(shù)的規(guī)律。因此，首先考慮利用結構化方法將非結構化過程模型轉為結構化過程模型，再進行計算?，F(xiàn)有方法只能將交叉同步結構轉為半結構化過程模型，需要設計對半結構化過程模型的軌跡計數(shù)方法。對于不能結構化的非自由選擇模型，可通過完全前綴展開算法展開后設計對應的計算方法，再將這些方法整合在一起。

2 預備知識

2.1 過程模型表示方法

現(xiàn)有BPM已由數(shù)據(jù)驅動轉為模型驅動，過程模型是對信息系統(tǒng)中業(yè)務過程的抽象表達。過程模型的表示方法多種多樣，本節(jié)簡要介紹本文涉及的業(yè)務流程建模與標注(Business Process Model and Notation，BPMN)[10]和Petri網(wǎng)[11]兩種過程模型表示方法，其中BPMN表示的過程模型對應的文件格式為XML過程定義語言(XML Process Definition Language，XPDL)[12]。

定義1BPMN[13]。一個BPMN用元組W=(A,G,C,,μ)表示，其中：

(1)A為過程模型中的所有任務或者活動節(jié)點的非空集合。

(2)G為過程模型中所有網(wǎng)關(gateway)節(jié)點的集合，網(wǎng)關用于描述控制流邏輯，包括AND網(wǎng)關(用帶“+”的菱形框表示)、XOR網(wǎng)關(用帶“×”的菱形框表示)和OR網(wǎng)關(用帶“○”的菱形框表示)3種類型，每個網(wǎng)關只屬于一種類型?？捎肰=A∪G表示過程模型中所有節(jié)點的集合。

(3)C?V×V為有向弧的集合，表示流動關系，即控制流(control flow)。

(5)μ:A→，為一個映射函數(shù)，其將每個任務映射為對應的名稱。

作為另一種業(yè)務過程建模語言，BPMN雖然在表達形式上沒有Petri網(wǎng)簡潔，但是目前在BPM領域的使用非常廣泛，大部分情況下BPMN和Petri網(wǎng)能相互轉換，對于含有一些特別結構(如包含性“或”結構)的過程模型，BPMN往往比Petri網(wǎng)的表達能力更強。

定義2Petri網(wǎng)[2]。一個Petri網(wǎng)N=(P,T;F)，其中：

(1)P為庫所(place，用圓圈表示)集合，表示條件、狀態(tài)或容器。

(2)T為變遷(transition，用方框表示)集合，表示動作、事件、活動或任務，且P∩T=?，P∪T≠?。

(3)F?(P×T)∪(T×P)為有向弧的集合，表示流動關系，“×”表示笛卡爾積。

定義3前驅和后繼集合[14]。一個Petri網(wǎng)N=(P,T;F)，令X=P∪T，對于?x∈X，有：

(1)?x={y∈X|(y,x)∈F}，表示節(jié)點x的所有前驅節(jié)點集合。

(2)x?={y∈X|(x,y)∈F}，表示節(jié)點x的所有后繼節(jié)點集合。

定義4網(wǎng)系統(tǒng)[14]。一個Petri網(wǎng)N=(P,T;F)的狀態(tài)通常稱為標識(marking)，設S=(N,M0)是一個網(wǎng)系統(tǒng)，有：

(1)M0為S的初始標識，若初始狀態(tài)只有源庫所i中有一個托肯(token，用黑點表示)，則M0={i}，M0(i)=1，剩下的?pi∈P的托肯數(shù)M0(pi)=0。

(3)S從M0可達的全部標識集合記為。

本文只討論一個源庫所和一個匯庫所的情況，即工作流網(wǎng)[15]，且Petri網(wǎng)是合理、安全的。合理(soundness)指工作流網(wǎng)的每次執(zhí)行以一個托肯到達匯庫所結束，此時只有一個托肯在匯庫所中，其他庫所都沒有托肯，網(wǎng)中任意一個變遷都可以使能，無死變遷；安全(safeness)[15]指所有庫所中的托肯數(shù)都小于或等于1。

2.2 完全前綴展開算法

基于網(wǎng)展開(unfolding)算法，可以使非結構化過程模型在保留原有可達狀態(tài)完整信息的同時，其表達結構更加簡單，有利于進一步計算非結構化過程模型的軌跡數(shù)。

文獻[14]對網(wǎng)展開算法[16]進行改進，避免了有時生成的有限完全前綴沒有最小化的問題，而且詳細介紹了改進后的Petri網(wǎng)展開算法。該算法通過保持原網(wǎng)的并行結構，避免了標識狀態(tài)空間爆炸問題；在循環(huán)處不指向之前的節(jié)點，而是繼續(xù)生成節(jié)點；遇到后繼與之前經(jīng)歷的節(jié)點一樣時進行截斷，不再繼續(xù)生成新的節(jié)點。結合2.1節(jié)介紹的Petri網(wǎng)基礎知識，下面對算法進行定義。

定義5排序關系[14]。對一個網(wǎng)中兩節(jié)點x和y的排序關系分為3種：

(1)因果關系(記x

(2)沖突關系(記x#y) 若網(wǎng)中有從同一庫所p開始的兩條路徑p,…,ti,…,x1和p,…,tj,…,x2，且任意ti≠tj，則x1#x2。

(3)并發(fā)關系(記xcoy) 若x

若網(wǎng)N=(P,T,F)是因果網(wǎng)，則網(wǎng)中沒有XOR互斥結構(即對?p∈P，有|?p|≤1，且|p?|≤1)，也沒有循環(huán)結構，節(jié)點間的排序關系只有因果和并發(fā)關系。若網(wǎng)O=(P,T,F)是發(fā)生網(wǎng)(occurrence net)，則O沒有XOR合并(即對?p∈P，有|?p|≤1)，也沒有循環(huán)結構，發(fā)生網(wǎng)O是前驅有限的，沒有元素與自身沖突(即x#x)，由此可知發(fā)生網(wǎng)中任意兩個節(jié)點間的排序關系是因果、沖突、并發(fā)關系中的一種。發(fā)生網(wǎng)O中前驅集為空的元素集合表示為Min(O)[14]。

定義6分支過程[14]。一個網(wǎng)系統(tǒng)S=(N,M0)=(PN,TN,FN,M0)的分支過程為β=(O,v)，其中O=(P,T,F)為發(fā)生網(wǎng)，標簽函數(shù)v滿足以下性質(zhì)：

(1)v是一個從O到N的節(jié)點映射函數(shù)，v(P)?PN且v(T)?TN，即函數(shù)v保留了節(jié)點的性質(zhì)。

(2)對?t∈T，有v(·t)=·v(t)且映射v:·t→·v(t)為雙射，同理v(t·)=v(t)·且映射v:t·→v(t)·為雙射，即v保留了變遷的環(huán)境。

(3)映射v:Min(O)→M0為雙射，即β“開始”于M0。

(4)對?t1,t2∈T，若·t1=·t2，且v(t1)=v(t2)，則t1=t2。

定義7分支過程的前綴[13]。設β1=(O1,v1)和β2=(O2,v2)是同一個系統(tǒng)的兩個分支進程，若O1是O2的子網(wǎng)，且v1是v2對O1發(fā)生網(wǎng)中節(jié)點的映射函數(shù)，則β1是β2的前綴。

定義8完全前綴展開[13]。設β=(O,v)是網(wǎng)系統(tǒng)S=(N,M0)的一個分支過程，其中O=(P,T,F)是發(fā)生網(wǎng)。

(1)分支過程β的一個配置(configuration)C是一個變遷集合，C?T，滿足以下兩個條件：①當t∈C時，若有t′∈T，且t′≤t，則t′∈C(即C是因果閉集)；②對?t1,t2∈C，有(t1#t2)(即C是無沖突的)。

(2)一個變遷t∈T的局部配置(localconfiguration)t是一個集合{t′∈T|t′≤t}。

(3)對β的一個有限配置C，有Cut(C)=(Min(O)∪C·)]·C，且v(Cut(C))是S的一個可達狀態(tài)，記為Mark(C)。

(4)若對S的每個可達標識M在β中存在一個配置C，使得：①Mark(C)=M，即M在β中表示；②對在N中由標識M使能的每個變遷t，存在一個β的配置C∪{t′}，t′∈T，使得t′?C，v(t′)=t。則稱β是完全的(complete)。

(5)如果滿足以下條件，則在β的有限配置上的一個偏序關系(partial order)是一個適當順序(adequate order)：①是有根據(jù)的(well-founded)；②C1?C2表示C1C2；③由有限擴展保留，詳見文獻[14]。

(6)一個變遷t∈T，令是β的有限配置上的適當順序，如果存在一個對應的變遷corr(t)∈T，使得Mark(t)=Mark(corr(t))，且corr(t)t，則t是β(關于)的一個截斷變遷(cut-off transition)。

(7)β是一個由引起的完全前綴展開，當且僅當β是S展開的最大前綴，且在截斷變遷后不再有變遷。

圖3所示為Petri網(wǎng)對應的展開和完全前綴展開的一個示例[13]，其中圖3b是對圖3a中的R1區(qū)域進行完全前綴展開，圖3b中虛線表示展開中需要被截斷的部分，變遷tv是展開的截斷變遷，即tv之后不再有變遷，而虛線箭頭tv指向變遷tu，表示截斷變遷tv對應的變遷為tu(即tu=corr(tv))。變遷tv和tu的兩個局部配置在原系統(tǒng)圖3a中有相同的標識(即Mark(tv)=Mark(tu)={pw,px})，因此tv之后的展開是重復的，在此進行截斷。圖3a中R1區(qū)域對應為該模型解析得到的RPST[17]中的一個組件(component)，RPST共有，，，4種組件類型[13]，組件是非結構化的，其余均為結構化的組件，用簡單RPST算法[18]可以在線性時間內(nèi)完成解析。

3 非結構化模型的軌跡計算過程

本章概述非結構化過程模型的軌跡計數(shù)方法與詳細的方法設計，計算方法是在塊結構模型軌跡計數(shù)算法[5]基礎上，結合了對非塊結構模型的結構化方法以及完全前綴展開算法，總體流程如圖4所示，主要步驟如下：

(1)通過RPST技術[18]將過程模型解析為一個塊結構與非塊結構子過程(即過程組件)組合在一起的樹形結構，遞歸遍歷RPST時，對不同的過程組件調(diào)用對應的計算算法，計算結果以塊字典[5](用于存儲塊內(nèi)所有軌跡長度對應的軌跡數(shù)集合，如{(0,1)}表示長度為0的軌跡有1條)的形式保存在RPST的節(jié)點中，其中計算塊結構的過程組件時，判斷出塊類型后調(diào)用文獻[5]中不同塊計算應的計算算法，計算非塊結構的過程組件(即組件)時，因為組件內(nèi)部可能存在循環(huán)嵌套組件的情況，所以從最底層的單個組件開始計算到上層組件。

3.1 過程組件的塊類型判斷方法

利用RPST技術[18]可以快速解析過程模型得到一個樹形結構，包括其所有規(guī)范過程組件(canonical process component)的集合，即過程組件之間不重疊，且包含原有過程模型所有邊的集合，如圖5所示，每個過程組件對應過程模型單入單出(Single Entry Single Exit, SESE)區(qū)域中所有邊的集合，用RPST解析技術解析后再進行計算，能快速辨別模型中的結構化部分(，，)和非結構化部分()，且對非對稱分裂合并結構(如圖2a)解析后不再含有非結構化部分(即無組件)。在RPST上遞歸遍歷計算過程組件對應的模型軌跡數(shù)，對結構化部分需判斷塊類型后才能用文獻[5]的方法計算，非結構化部分則采用本文方法計算(見3.2節(jié)和3.3節(jié))，直到計算完RPST的根節(jié)點，得出整個過程模型的軌跡數(shù)。

在文獻[5]中的塊結構過程模型軌跡數(shù)是用過程樹[19]計算的，過程樹中葉子節(jié)點對應過程模型中的點(一個活動、任務或變遷)，而RPST中葉子節(jié)點對應的是過程模型中的一條邊，如圖5b中所有葉子節(jié)點組件類型均為，每個葉子節(jié)點對應原模型中的某一條邊，保存了每條邊的入口節(jié)點和出口節(jié)點，為了表示簡潔將原模型中的所有網(wǎng)關節(jié)點都用“gw”表示(實際上每個網(wǎng)關節(jié)點表示是不同的)。若將基于過程樹的塊結構過程模型軌跡計數(shù)算法用在RPST上，則需將RPST中3種表示結構化過程模型的組件，，與過程樹中運算符類型O={→,×,∧,k,∨}進行對應(即判斷過程組件對應的塊類型)，從而使過程模型解析為RPST后，結構化的過程組件能應用改進塊結構的軌跡長度與數(shù)量計算算法，對非結構化部分(組件)采用非塊結構過程模型的計算方法進行計算。由于組件直接對應非結構化子過程，遞歸遍歷RPST時很容易判斷，且過程樹中的節(jié)點無法表達非結構化的子過程，本節(jié)只對，，3種過程組件對應的過程樹節(jié)點塊類型進行判斷。

在遞歸遍歷RPST時，可以通過其組件類型、出入口節(jié)點特征和子節(jié)點出入口節(jié)點特征，分析出該過程組件對應的過程樹節(jié)點(即其對應過程模型SESE區(qū)域的結構類型)，對應關系如表1所示。其中過程組件的塊類型判斷過程如下：

表1 過程樹節(jié)點與RPST過程組件類型的對應關系

3.2 可結構化模型的計算方法

部分非結構化過程模型可以轉為結構化，因此可以利用已有算法將正確的、非結構化的過程模型轉換為等效的(半)塊結構模型，再對等效的(半)塊結構過程模型進行軌跡計數(shù)，這是一種解決非塊結構過程模型跡計數(shù)問題的研究思路。因此，本節(jié)將已有BPStruct[13]和StructXPDL[20]結構化轉換方法的優(yōu)點相結合，使更多種非塊結構過程模型結構化，并對結構化轉換后可能出現(xiàn)的半塊結構模型設計軌跡計數(shù)方法。

本文主要解決的是5種類型的非結構化過程模型的軌跡計數(shù)問題，包括非對稱分裂合并、任意跳轉、任意循環(huán)、非自由選擇和交叉同步。表2所示為兩種結構化方法分別對5種類型過程模型結構化結果的比較，其中“√”為可以結構化，“×”為不能結構化(包括無返回結果、結果錯誤或結果為原模型)，文獻[20]也給出了兩種方法的比較，但側重點不同。對非對稱分裂合并的結構化，采用RPST解析技術，得到的RPST結構即為塊結構，當然BPStruct方法和StructXPDL方法均可正確結構化；對任意跳轉的結構化，如果是XOR網(wǎng)關或庫所進行的跳轉(非循環(huán)結構)，則BPStruct方法和StructXPDL方法均可結構化，如果是AND網(wǎng)關或變遷進行的任意跳轉，則為一個交叉同步結構，BPStruct方法返回原模型，StructXPDL方法返回半塊結構的過程模型；對于任意循環(huán)的結構化，用BPStruct工具(BPstruct-0.1.97.jar[21])能夠對如圖2b所示的任意循環(huán)結構結構化，而StructXPDL方法無返回結果；對于非自由選擇的結構化，BPStruct方法和StructXPDL方法對如圖2c所示的簡單的非自由選擇結構都會返回錯誤的結果，如果為復雜的非自由選擇結構，則BPStruct方法不能返回結果，而StructXPDL方法能返回結果，但錯誤率較高；對于交叉同步結構的結構化，BPStruct方法會返回原有的交叉同步結構，StructXPDL方法可以將不帶循環(huán)的交叉同步結構結構化為半塊結構的過程模型。

表2 BPStruct方法與StructXPDL方法比較

經(jīng)過上述分析可知，使用BPStruct方法時的預處理和后處理，主要針對簡單非自由選擇結構，如圖6a簡單非自由選擇結構在用BPStruct工具結構化后會返回錯誤的結果(如圖6b)，圖6b雖為塊結構模型，但比正確的等效結構化表達多出了T1和T2兩條邊，刪除邊T1和T2就能得到正確的結果。對類似圖6a的簡單非自由選擇結構，在用BPStruct方法結構化后都會多出從XOR分裂指向XOR合并的傳遞邊[20](transitive edge)，需要通過后處理刪除這些多余的傳遞邊，注意在采用BPStruct方法之前，需要對原模型中存在的上述傳遞邊進行預處理，增加一個不可見任務，從而在不改變模型軌跡長度與對應軌跡數(shù)的情況下，避免后處理時刪除原模型中的這種傳遞邊而使結果出現(xiàn)錯誤。

因此，對非塊結構的過程組件結構化，優(yōu)先采用BPStruct方法，需預處理后進行結構化。由于非結構化模型的RPST中有時存在組件的嵌套結構，所以從最里層的組件開始使用BPStruct方法進行結構化，并進行如下判斷：

(1)如果已經(jīng)結構化為塊結構的過程組件，則后處理刪除多余的從XOR分裂指向XOR合并的傳遞邊，然后調(diào)用文獻[5]的計算方法對塊結構過程模型計算軌跡長度和數(shù)量。

(3)如果返回結果為空，說明其中含有BPStruct方法不能解決的復雜非自由選擇結構(見3.3節(jié))，則調(diào)用算法1處理(若返回模型的RPST中仍有組件，則再次進行結構化操作)，再計算軌跡長度和數(shù)量。

針對上述情況(2)，若StructXPDL方法結構化后得到的是半塊結構過程模型(如圖7a)，則將帶有某些特征(見定義9)的半塊結構模型進行半塊結構后處理，刪除這部分多余同步條件，等效轉換為塊結構的過程模型(如圖7b)，再對后處理的(半)塊結構模型進行軌跡計數(shù)。類似定義9的多余同步條件情況還有很多，有的并不影響半塊結構軌跡長度與數(shù)量計算方法(見定義10和定義11)的計算結果，在這里沒有對其進行后處理，只對圖7a的情況進行后處理，對需要刪除的多余同步給出定義9，對選出的ym，yn所在分支進行如圖7所示的后處理。

定義9半塊結構后處理判斷。一個BPMN中帶有同步條件的節(jié)點集合為S，syn為從帶同步條件的節(jié)點到對應條件節(jié)點的映射函數(shù)，存在一個AND網(wǎng)關gwi符合如下條件：

(1)滿足|?gwi|≥2，即gwi是一個AND合并節(jié)點。

(2)當Y={y|y∈?gwi∧y∈S}時，|Y|≥2。

(3)?ym,yn∈Y，若syn(yn)=·ym且syn(ym)=·yn，則選擇ym，yn進行后處理。

對含交叉同步結構的過程模型，因為交叉同步結構中存在多個AND合并節(jié)點，如果采用完全前綴展開，則展開后與展開前的交叉同步結構不會改變，所以選用StructXPDL方法對交叉同步結構進行結構化，再計算所生成半塊結構過程模型的軌跡長度與數(shù)量。刪除結構化結果多余的同步條件后，模型中仍然可能存在同步條件，該同步條件不能被后處理方法刪除，需要在塊字典中添加同步條件屬性T后進行計算。例如原來{(1,1)}表示一條長度為1的軌跡，現(xiàn)在增加為{{(1,1)},Ti}，表示這是一條長度為1的軌跡，且軌跡中帶有任務Ti，等遇到帶有與其對應的同步條件節(jié)點Tj的塊字典時，再完整地計算軌跡長度與對應數(shù)目。如果不帶有同步條件，或者同步條件已經(jīng)計算完畢，則為正常的塊字典{{(1,1)},?}(同步條件屬性T=?)，可簡寫為{(1,1)}。本節(jié)提出兩種計算方法，并對兩種方法的優(yōu)缺點進行分析。

同步條件產(chǎn)生的原因是原始非塊結構過程模型有交叉同步，用StructXPDL方法結構化后，得到帶有同步條件的節(jié)點，如圖8a中節(jié)點C帶有同步條件DONE(E)，意為E執(zhí)行后C才能執(zhí)行，因此半塊結構中的同步條件會出現(xiàn)在一個共同的并行結構中，即兩個節(jié)點之間的SESE區(qū)域是包含關系。設ydonex為帶有同步條件的節(jié)點，x為其對應的同步條件，兩種方案都會用相同的帶有同步條件屬性的塊字典存儲。存在節(jié)點V，用Vf表示其所在分支前面的部分，Vb表示其后面的部分，V若為ydonex則參與Vb部分的計算，若為x則參與Vf部分的計算。兩種計算方法見定義10和定義11，其中用節(jié)點及其前后部分簡化表示對應的塊字典參與計算，R保存的是中間結果，D是最后計算得到的不帶同步條件屬性的塊字典。

定義10半塊結構軌跡長度與數(shù)量計算方案1。設ydonex為帶有同步條件的節(jié)點，x為其對應的同步條件，且xb={{(n,1)},x}，n為0或1，有：

(1)R1=parallel(xf,ydonexf)。

(2)R2=parallel(xb,ydonexb)。

(3)R3=sequence(parallel(sequence(xf,xb),ydonexf),ydonexb)。

(4)R4=sequence(R1,xb,ydonexb)。

(5)D=exclusiveChoice(sequence(R1,R2),R3)removeR4。

定義11半塊結構軌跡長度與數(shù)量計算方案2。設ydonex為帶有同步條件的節(jié)點，x為其對應的同步條件，不涉及AND結構的嵌套，且xb={{(n,1)},x}，整數(shù)n≥0，有：

(1)從后部分集合ydonexb中先移除ydonex，得到y(tǒng)donexb。

(2)R1=parallel(xf,ydonexf)。

(3)R2=parallel(xb,ydonexb)。

(4)R3=sequence(R1,ydonex)。

(5)R4=sequence(R3,R2)。

(6)D=exclusiveChoice(D,R4)。

(7)若n≥1，則xf=sequence(xf,{(1,1)})，xb=xbremove{(1,1)}，n=n-1，再從(2)開始計算；否則輸出D。

兩種方案都不能有節(jié)點與x或ydonex的節(jié)點重名，相同名稱的節(jié)點會被認為是同一個節(jié)點。匹配過程按照就近原則，匹配計算后塊字典不再帶有同步條件標記，再出現(xiàn)的同名任務會正常計算，其中的parallel()，sequence()，exclusiveChoice()指調(diào)用文獻[5]中對應的塊函數(shù)。方案1可以計算含有嵌套的AND結構，但對x后軌跡長度大于1的情況，計算結果會小于真實值，如圖8a所示。方案2可以計算x后軌跡長度大于等于0情況，但要求軌跡數(shù)目只能為1，不能含有AND塊結構的嵌套，如圖8b所示。因此當x所在分支后部分xb為一條軌跡，軌跡長度大于1，且ydonex不是一個歸約節(jié)點，即塊字典需要是{{(1,1)},ydonex)}或{{(0,1)},ydonex)}時，采用方案2，其他情況采用方案1。

3.3 不可結構化模型的計算方法

非自由選擇結構在簡單情況下可以被BPStruct方法或XPDLStruct方法結構化，但也存在很多不能被結構化的情況，需要轉為Petri網(wǎng)再進行有限完全前綴展開，在展開的結果上計算軌跡長度與數(shù)量。

本文主要針對兩種較復雜非自由選擇結構進行研究，即不帶循環(huán)的復雜非自由選擇結構和帶循環(huán)的復雜非自由選擇結構。這兩種結構在Petri網(wǎng)展開后仍然是一個非結構化的網(wǎng)，對于這樣的情況，首先對Petri網(wǎng)進行有限完全前綴展開[14]，由于展開算法只能對Petri網(wǎng)使用，如果輸入為BPMN形式，則用已有的BPMN轉Petri網(wǎng)的算法[13,22]進行轉換后再展開，然后對不帶循環(huán)的復雜非自由選擇結構，在Petri網(wǎng)展開后的結果中找到可以抖動的節(jié)點進行祖先抖動，得到一個結構化的網(wǎng)，將截斷節(jié)點的后繼庫所合并即可進行計算，例如圖9a～圖9c所示；對于帶循環(huán)的復雜非自由選擇結構，在Petri網(wǎng)展開后的結果中找到循環(huán)中的AND合并節(jié)點，并計算循環(huán)結果，歸約循環(huán)結構為一個節(jié)點，以互斥關系將節(jié)點加入原來的網(wǎng)，例如圖9d～圖9f所示。最后將圖9c和圖9f解析為RPST后按塊結構模型計算。

對于不帶循環(huán)的復雜非自由選擇結構，如圖9a展開后得到圖9b，會發(fā)現(xiàn)非自由選擇結構在展開后會變得更加簡單，只要找到兩個及以上AND合并節(jié)點(如“G-8”和“D-4”，有一個共同的AND分裂節(jié)點“A-1” )就能對圖9b進行祖先抖動，從AND合并節(jié)點向對應的同一個AND分裂節(jié)點抖動，找出需要復制的變遷集合。圖9b中為集合{A-1,E-2}，復制后通過合并截斷庫所，即合并“G-8”與“G-9”的后繼庫所，得到圖9c，包含了新增的節(jié)點“A-10”和“E-11”。對于帶循環(huán)的復雜非自由選擇結構，如圖9d展開后得到圖9e，不同于結構化循環(huán)結構的是循環(huán)第1次與第2次的軌跡不同，當循環(huán)次數(shù)大于2時才有規(guī)律，圖9e中節(jié)點“i-1”到“o-6”是不循環(huán)的情況，節(jié)點“i-1”到“C-7”再到“o-10”是循環(huán)一次的情況，節(jié)點“i-1”到“C-7”再到“C-11”再到“o-10”是循環(huán)兩次的情況(對應圖9d中節(jié)點i循環(huán)到C，再循環(huán)到C，再到o)，當循環(huán)大于兩次時一直都是在增加節(jié)點C到C的軌跡開始有規(guī)律，因此類似圖9e情況時，分別構造從節(jié)點i到節(jié)點C、從節(jié)點C到C、從節(jié)點C到o的3個AND塊結構，再分別計算出對應的塊字典，如圖9f所示，虛線方框中將按最大循環(huán)次數(shù)為k-1計算得到的塊字典存儲在循環(huán)歸約節(jié)點“LOOPcomponent:4”中，并以互斥關系將節(jié)點插入刪除循環(huán)后的AND塊結構部分。

算法1給出了上述非自由選擇結構的歸約式結構化計算方法，算法輸入為不能被已有方法結構化的過程模型p和用于循環(huán)歸約的最大循環(huán)次數(shù)k。在第1～4行中，將輸入的過程模型p轉為Petri網(wǎng)petri，并進行完全前綴展開得到網(wǎng)cpu，找出cpu中一個AND分裂節(jié)點對應多個AND合并節(jié)點的情況，將一對多的映射關系保存在map中(第3行)，

然后根據(jù)展開的網(wǎng)構建一個節(jié)點與邊關系均相同的網(wǎng)系統(tǒng)pn。第7～9行判斷join是否為圖9e中節(jié)點C到C的情況，是則不需要計算，繼續(xù)循環(huán)換map中下一個分裂節(jié)點，對圖9e只在并行分裂節(jié)點為“i-1”、并行合并節(jié)點為“C-7”才開始循環(huán)歸約。第10行中，j0是AND合并節(jié)點集合joins中不為開始循環(huán)的節(jié)點，因為祖先抖動或者循環(huán)歸約均在兩個join節(jié)點之間進行，所以規(guī)定調(diào)用算法時第1個j0不能為循環(huán)中的節(jié)點，第2個ji如果是循環(huán)中的節(jié)點，則進行循環(huán)歸約(第13～15行)，c表示循環(huán)歸約后返回的新節(jié)點(第13行)，對pn添加節(jié)點c，刪除ji及其后的循環(huán)部分(第14～15行)，如圖9f所示；如果不是循環(huán)中的節(jié)點，則進行祖先抖動(第17～18行)，先計算需要復制的變遷和庫所節(jié)點集合E(第17行)，然后在網(wǎng)系統(tǒng)中增加復制的節(jié)點(第18行)。其中判斷節(jié)點是否在循環(huán)中(第7,10,12行)，采用的是完全前綴展開后節(jié)點e的局部配置?e?中事件前驅對應的所有庫所，其與局部配置中包含節(jié)點e的截斷變遷到節(jié)點e之間的事件(包括節(jié)點e)后繼對應的所有庫所存在交集，判斷為節(jié)點e在一個循環(huán)的結構中，即節(jié)點e之后存在指向該節(jié)點之前的庫所的邊。最后，若存在多個截斷變遷的后繼庫所對應到原Petri網(wǎng)中是同一個庫所，則合并這些庫所(第22行)。

算法1非自由選擇結構展開后軌跡長度與數(shù)量計算算法unfolding。

輸入：過程模型p、最大循環(huán)次數(shù)k(傳參)。

輸出：與過程模型相同塊字典的Petri網(wǎng)pn、所有歸約節(jié)點名稱及其對應的塊字典R_loop_pd。

1: petri←transPetriNet(p)

2: cpu←properCompletePrefixUnfolding(petri)//有限完全前綴展開

3: map←findSplitJains(cpu)

4: pn←transNet(cpu)

5: for split∈map.kevset()do

6: joins←map(split)

7: if ?j∈joins,j.getTransition()=split.getTransition()且j是循環(huán)節(jié)點then

8: continue

9: end if

10: j0←getNoLoop(joins)

11: for ji∈joins(〗j0} do

12: if ji是在循環(huán)中的節(jié)點then

13: c←reduceNFCLoop(cpu,split,j0,ji)//局部求解循環(huán)部分，歸約節(jié)點保存在R_loop_pd中

14: pn←addLoopComponent(pn,c)//以互斥關系加入c

15: pn←removeLoop(pn)

16: else

17: E←getAddNodes(split,j0,ji)//其中變遷集合為j0∩jisplit∪{split}

18: pn←forwardAncestorFlutter(E,split,j0,ji)//祖先抖動算法復制E中節(jié)點

19: end if

20: end for

21:end for

22:pn←joinPlces(pm)

23:return pn

4 實驗評估

本章對非結構化過程模型的軌跡計數(shù)方法進行實驗評估。因為模型的軌跡數(shù)未標注在真實數(shù)據(jù)集上，所以用人造模型和結構化方法提供的評估數(shù)據(jù)集驗證算法的有效性，用真實數(shù)據(jù)集測試算法性能，并對測試結果進行分析。

4.1 基于人造模型的評估

本文算法實驗的開發(fā)工具為IntelliJ IDEA，選擇的編程語言為Java語言，因為大部分工具均用Java語言編寫，所以涉及調(diào)用的方法不是Java語言時需轉寫為Java語言。算法中使用的工具有結構化工具BPStruct[21]和結構化方法StructXPDL[20]，以及調(diào)用ProM5.2[23]和jBPT[24]中的一些對過程模型的處理和分析方法，如完全前綴展開算法。

采用XPDL圖形化編輯工具[25]人工繪制一些過程模型，用于對算法進行單元測試，主要測試算法在有限時間內(nèi)能正確計算的非結構化過程模型類型。單元測試分半塊結構和非塊結構過程模型，半塊結構模型通過StructXPDL方法對含交叉同步的過程模型結構化后得到，非塊結構模型主要包括非對稱分裂合并、任意循環(huán)、非自由選擇、任意跳轉4種結構。對以上5種結構分別構造多個只含單一結構的示例過程模型，作為算法單元測試的輸入。

對半塊結構模型，即交叉同步結構的結構化結果，其計算方法見3.2節(jié)，在文獻[20]的算法評估中提供了11個基準示例過程模型，其中只有5個模型輸入后生成半塊結構的過程模型，因此選擇這5個模型進行測試，同時測試本文示例圖8a和圖8b，測試結果如表3所示，可見參加測試的幾種模型均能得到正確結果。模型7819結構化后為與圖8b同類型的模型，只是節(jié)點數(shù)更少，其同步條件節(jié)點所在分支后面的部分為一條長度為1的軌跡(即定義10和定義11中的xb={{(1,1)},x})，可以用方案1或方案2計算，實現(xiàn)時是用方案1計算；模型7820只需用StructXPDL方法結構化后，通過后處理直接得到塊結構模型，然后再計算；模型7821，7823，7826結構化后為與圖8a同類型的模型，只是增加了XOR結構，均用方案1計算；表3中只有圖8b用方案2計算，且不能使用方案1計算。

表3 半塊結構模型計算算法有效性測試結果

對其他非塊結構過程模型計算的不同長度軌跡數(shù)如表4所示，包括非對稱分裂合并、任意循環(huán)、非自由選擇、任意跳轉4種結構，模型3～模型5均為非自由選擇結構(簡寫為NFC)，都能得出正確的結果。按照本文方法，模型1在經(jīng)過RPST分解后不存在非結構化組件，按對塊結構模型求不同長度軌跡數(shù)的算法計算；模型2用BPStruct工具轉為塊結構后再計算；模型3需要用預處理加后處理方法改進結構化后的模型，模型4和模型5用算法1計算；此處對任意跳轉結構的測試只有XOR網(wǎng)關(或XOR分裂合并節(jié)點)任意跳轉的情況(如圖2d)，且不構成循環(huán)結構，先結構化為塊結構模型再計算。

表4 4種非塊結構模型計算算法有效性測試結果

其中模型2為任意循環(huán)結構，所得結果總軌跡數(shù)為39，與第1.1節(jié)描述的19條軌跡有出入，原因是用BPStruct工具將圖2b結構化生成了一個等效的嵌套循環(huán)結構，計算嵌套的結構化循環(huán)結構時，內(nèi)層循環(huán)和外層循環(huán)的最大循環(huán)次數(shù)均為2，但是外層循環(huán)每經(jīng)過一次內(nèi)層循環(huán)，會用一次內(nèi)層循環(huán)的計算結果參與計算，外層循環(huán)次數(shù)為2時經(jīng)過3次內(nèi)層循環(huán)，單次的最大循環(huán)次數(shù)為2，即內(nèi)層循環(huán)的實際最大循環(huán)次數(shù)為6，結果不同是計算方法制定的最大循環(huán)次數(shù)規(guī)則不同，當內(nèi)層循環(huán)實際最大循環(huán)次數(shù)為2時總軌跡數(shù)為19，當內(nèi)層循環(huán)單次最大循環(huán)次數(shù)為2時總軌跡數(shù)為39，兩種結果都正確，計算時只能二選一。

通過測試5種非塊結構模型的計算算法可見，算法在各個已測試的過程模型上都能正確計算出模型的軌跡數(shù)，從而量化過程模型的行為量，計算結果可以用于合規(guī)性檢查中精確度的計算，并作為模型復雜度的參考指標之一。

4.2 基于現(xiàn)實例子的評估

性能測試使用的9個數(shù)據(jù)集包括，在文獻[13]的算法評估中提供的一些實際模型(BPMN)；在文獻[20]的算法評估中提供的用于比較結構化算法的11個基準示例過程模型(BPMN)，可以用于對本文進行評估；在文獻[26]實驗部分收集整理的7個公開數(shù)據(jù)集(Petri網(wǎng))，包括SAP，TC，DG，IBM，BAI，GPM，SPM[27-30]，其中SAP，TC，DG，IBM 來自企業(yè)等工業(yè)領域的過程模型，BAI，GPM，SPM來自在線教程等學術領域過程模型。以上9個過程模型數(shù)據(jù)集的詳細說明如表5所示，其中平均可見任務數(shù)精確到小數(shù)點后兩位，這些模型總數(shù)為456，非結構化模型有261個，約占57.24%，此處統(tǒng)計的非結構化模型數(shù)指模型轉為RPST后含有組件的過程模型數(shù)量，可見任務數(shù)指輸入模型中識別為可見任務并參與軌跡計數(shù)的節(jié)點數(shù)量。

表5 數(shù)據(jù)集說明

續(xù)表5

測試結果中195個結構化模型均能計算，246個非結構化模型可以計算，其余有1個含有多個源節(jié)點或多個匯節(jié)點的模型、8個BPStruct工具無法結構化的任意循環(huán)結構模型和6個含有復雜交叉同步結構的模型無法得到計算結果，不能計算的這3種情況均為相似的過程模型。對于能夠得到結果的數(shù)據(jù)，繼續(xù)分析運行時間、可見任務數(shù)和模型總軌跡數(shù)之間的關系，為了更好地展示測試結果，去掉3個可見任務數(shù)大于60的模型結果。圖10a所示為運行時間與可見任務數(shù)對應的散點圖，其中可見任務數(shù)小于10的區(qū)域有少數(shù)模型的計算時間高于400 ms，均為含有任意循環(huán)或非自由選擇結構的模型，由于對這兩種結構調(diào)用BPStruct工具會大大增加返回的時間，當排除調(diào)用返回時間后，對于大部分模型，運行時間不受可見任務數(shù)影響，主要取決于輸入模型的組成結構。在圖10b中，因為部分模型的軌跡數(shù)較大，會使呈現(xiàn)出來的散點距離較遠，大部分集中在原點區(qū)域，不利于分析性能測試結果，所以先對總軌跡數(shù)取以2為底的對數(shù)，再與運行時間進行分析?？梢娺\行時間與總軌跡數(shù)正相關，對不含任意循環(huán)或復雜非自由選擇結構的模型，計算不同長度軌跡數(shù)的運行時間可以保持在400 ms以內(nèi)。

5 相關工作

已有對過程模型軌跡計數(shù)的研究工作，如文獻[5]中提出的算法，只能計算塊結構過程模型的軌跡數(shù)，不能計算非塊結構過程模型的軌跡數(shù)，而本文方法能夠計算大部分非塊結構過程模型的軌跡數(shù)。

本文方法與文獻[5]方法的比較如表6所示，其中對于重復任務，在帶有交叉同步的結構中不能出現(xiàn)與同步條件重名的不同任務；對于非對稱分裂合并結構，本文中此類過程模型經(jīng)過RPST解析后即為結構化的過程組件，而過程樹在表達上存在局限性，只能等效表達，文獻[5]只支持等效表達形式；對于交叉同步結構，不支持的情況指對含有交叉同步結構的模型用StructXPDL方法結構化后，經(jīng)過后處理得到的半塊結構模型，其中對應同步條件x與ydonex節(jié)點所在的過程組件含有AND塊結構的嵌套，且x節(jié)點后軌跡長度大于1，如圖11所示；對于非自由選擇結構，目前只能解決已知的非自由選擇結構類型，是否有其他非自由選擇結構類型還不確定；對于循環(huán)結構，本文方法的支持范圍比文獻[5]更廣，不僅可以計算含結構化循環(huán)的模型，還可以計算部分含非結構化循環(huán)的模型。

表6 本文方法與相關工作的比較

6 結束語

軌跡數(shù)是量化過程模型行為的一種形式，快速計算得到正確的軌跡數(shù)有助于評估模型的質(zhì)量和復雜度。本文圍繞非結構化過程模型軌跡計數(shù)問題展開研究，在現(xiàn)有算法基礎上對可能遇到的各種過程模型結構逐一提出解決方案和方法設計。首先，判斷RPST中結構化的過程組件塊類型(順序、互斥、并行、循環(huán)或OR)；接著，利用組件對嵌套的非結構化過程模型進行歸約計算；然后，用BPStruct方法和StructXPDL方法對可以結構化的過程組件進行結構化，其中需要添加或刪除節(jié)點以結構化更多模型類型，再按照塊結構的計算方法計算，若帶有同步條件，則用半塊結構的計算方法計算；最后，對于無法結構化的過程組件，用完全前綴展開技術對展開的網(wǎng)進行結構化或循環(huán)歸約，隱藏非結構化部分，從而計算出軌跡數(shù)。

本文所提方法在計算一些特殊非結構化過程模型時仍存在不足，如BPStruct工具無法結構化的任意循環(huán)結構、結構化后會含多個同步條件的復雜交叉同步結構模型等，未來將在完善算法的同時降低時間復雜度。