常 震 戴汪洋 宋 巍 李晅松

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

業(yè)務(wù)過(guò)程管理旨在加快制定，分析和改進(jìn)業(yè)務(wù)過(guò)程的速度，而圍繞著過(guò)程所建立的組織，具有更高的敏捷性、效率和效益。為了支持管理決策，業(yè)務(wù)過(guò)程日志記錄了過(guò)程實(shí)例的執(zhí)行，通過(guò)分析業(yè)務(wù)過(guò)程日志數(shù)據(jù)可以了解業(yè)務(wù)過(guò)程的執(zhí)行，實(shí)現(xiàn)業(yè)務(wù)過(guò)程的管理、改進(jìn)與再造［1～3］。在日志噪音修復(fù)、過(guò)程挖掘中的合規(guī)性檢驗(yàn)方面，不可避免地要對(duì)日志中的事件序列進(jìn)行差異性度量，如驗(yàn)證事件序列的修復(fù)情況等［4～6］。

在計(jì)算機(jī)科學(xué)中，字符串編輯距離是重要而基本的概念，它在拼寫(xiě)檢查與自動(dòng)修復(fù)等方面有著廣泛的應(yīng)用［7～8］。雖然可以使用字符串編輯距離來(lái)定義業(yè)務(wù)過(guò)程日志中事件序列間的編輯距離，但該方法在應(yīng)用于含并發(fā)的業(yè)務(wù)過(guò)程時(shí)并不理想。例如在日志修復(fù)時(shí)，一個(gè)含有噪音的事件序列可能存在多個(gè)不同的正確修復(fù)方案［4～6］，不同修復(fù)方案的差異往往僅體現(xiàn)在存在并發(fā)關(guān)系的事件的先后順序上。如果利用字符串編輯距離作為評(píng)判依據(jù)，這些正確的修復(fù)有很多不被認(rèn)為是最優(yōu)修復(fù)。

考慮到現(xiàn)有方法的不足，本文針對(duì)業(yè)務(wù)過(guò)程的并發(fā)性以及事件序列可能產(chǎn)生的噪音類型，給出了業(yè)務(wù)過(guò)程事件序列編輯距離的全新定義，提出了相應(yīng)的求解算法，并將該算法實(shí)現(xiàn)為一個(gè)圖形化的桌面工具“BPETED”（Business Process Event-trace Ed?it Distance）。該工具可以解析XES格式的事件日志文件，并計(jì)算指定的事件序列間編輯距離，同時(shí)給出時(shí)間消耗。本文通過(guò)IBM公司一個(gè)真實(shí)的業(yè)務(wù)過(guò)程日志對(duì)算法進(jìn)行分析，驗(yàn)證算法的有效性和高效率。

2 背景知識(shí)

2.1 業(yè)務(wù)過(guò)程

Petri網(wǎng)［9］是一種簡(jiǎn)潔通用的表示業(yè)務(wù)過(guò)程的建模語(yǔ)言，并且擁有一套完善的數(shù)學(xué)理論進(jìn)行過(guò)程分析。因此，其他如BPEL、BPMN、EPC等工業(yè)建模語(yǔ)言也經(jīng)常被轉(zhuǎn)化為Petri網(wǎng)進(jìn)行高級(jí)的分析與應(yīng)用［10～11］。本文延用慣例，也使用 Petri網(wǎng)來(lái)表示業(yè)務(wù)過(guò)程。

定義1（Petri網(wǎng)）Petri網(wǎng)是一個(gè)滿足如下條件的三元組PN=(P，T，F(xiàn))：

·P是庫(kù)所的有限集合；

·T是變遷的有限集合，并且滿足P∩T=Φ；

·F?(P×T)∪(T×P)是被稱為流關(guān)系的有向弧的有限集。

Petri網(wǎng)所表示的業(yè)務(wù)過(guò)程中的起始庫(kù)所和終止庫(kù)所只有一個(gè)，并且它是可以執(zhí)行的。業(yè)務(wù)過(guò)程每執(zhí)行一次便產(chǎn)生一條過(guò)程實(shí)例，該過(guò)程實(shí)例可以用一條事件序列σ={t1，t2，t3，...，tn} 來(lái)表示，其中t1，...，tn代表事件，這n個(gè)事件按照發(fā)生的先后順序進(jìn)行排列。將這些過(guò)程實(shí)例記錄下來(lái)便形成了事件日志。

定義2（事件序列與事件日志）給定一個(gè)業(yè)務(wù)過(guò)程W=(P，T，F(xiàn))，其初始狀態(tài)為M0，事件序列σ∈T*是從狀態(tài)M0轉(zhuǎn)化為狀態(tài)M的一條活動(dòng)序列，其中M為W的任意一個(gè)可達(dá)的狀態(tài)。事件日志為事件序列的集合，即L={σ|σ∈T*}。

圖1展示了一個(gè)含并發(fā)的業(yè)務(wù)過(guò)程Petri網(wǎng)模型。

圖1 含并發(fā)的Petri網(wǎng)

2.2 字符串編輯距離

關(guān)于編輯距離問(wèn)題的研究可以追溯到字符串間編輯距離，這個(gè)概念最早由俄國(guó)科學(xué)家Levensh?tein于1965年提出，因此，編輯距離也被稱為“Lev?enshtein distance”（以下簡(jiǎn)稱 L 氏距離）［15～16］。編輯距離是一種通過(guò)計(jì)算將一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串所需的最小操作次數(shù)來(lái)量化兩個(gè)字符串間相似性的方式［7～8］。它在自然語(yǔ)言處理、生物信息科學(xué)以及計(jì)算機(jī)科學(xué)等方面有著廣泛的應(yīng)用。

字符串間編輯距離計(jì)算利用動(dòng)態(tài)規(guī)劃的算法思想，將兩個(gè)字符串間的編輯距離轉(zhuǎn)換為子序列間的編輯距離，用一個(gè)維度大小分別為源字符串長(zhǎng)度和目標(biāo)字符串長(zhǎng)度的矩陣來(lái)保存計(jì)算過(guò)程中求得的子序列編輯距離［12～14］。一般來(lái)說(shuō)，兩個(gè)字符串的編輯距離越短，則表示它們?cè)较嗨?，如果兩個(gè)字符串相同，則它們的編輯距離為零。

到目前為止，對(duì)編輯距離的定義有很多擴(kuò)展，不同的編輯距離定義了不同的字符串操作集合。其中，L氏距離的操作集合包括刪除、插入、替換［15～16］。此外還存在最長(zhǎng)公共子序列（LCS）距離，操作集合只包含刪除、插入兩類操作；海明距離（Hamming distance），只允許替換操作等多種擴(kuò)展類型的編輯距離［7］。除此之外，有人還提出了一些其他的基本操作，如鍵入文字時(shí)常見(jiàn)的錯(cuò)誤，交換相鄰兩個(gè)字符的順序。由于以上各種編輯距離定義不能直接應(yīng)用于含并發(fā)的業(yè)務(wù)過(guò)程事件序列，因此，在章節(jié)3.2中我們給出了業(yè)務(wù)過(guò)程事件序列編輯距離的全新定義。

3 編輯距離算法

3.1 事件間關(guān)系

由于字符串中的字符間的關(guān)系是相互獨(dú)立的，因此在計(jì)算字符串編輯距離的過(guò)程中，不考慮字符間的相互關(guān)系。但對(duì)于事件序列來(lái)說(shuō)，事件間存在一系列關(guān)系，這些關(guān)系可能會(huì)對(duì)事件序列編輯距離產(chǎn)生影響。

事件序列間的關(guān)系包括直接先于關(guān)系（符號(hào)表示為>）與并發(fā)關(guān)系（符號(hào)表示為||）等。直接先于關(guān)系與并發(fā)關(guān)系的定義同文獻(xiàn)［17］中定義相同。

定義3（事件間關(guān)系）給定一個(gè)業(yè)務(wù)過(guò)程W=(P，T，F(xiàn))的事件日志L，存在事件a，b，滿足a，b∈T，a≠b，則a，b存在以下關(guān)系：

·a>b，對(duì)于任一事件序列σ={t1，t2，t3，…，tn}，當(dāng)a=ti，b=t(i+1)，則a>b；

·a||b，當(dāng)且僅當(dāng)a>b，并且b>a時(shí)，a||b。

算法1旨在挖掘業(yè)務(wù)過(guò)程事件日志中事件間的并發(fā)關(guān)系集合。第1行對(duì)集合進(jìn)行初始化；第2～4行挖掘事件間的直接先于關(guān)系集合；第5～8行根據(jù)之前獲得的事件間直接先于關(guān)系集合，挖掘事件間的并發(fā)關(guān)系集合，其中第5～6行利用二重循環(huán)遍歷事件日志中所有的事件對(duì)，第7～8行根據(jù)事件間直接先于關(guān)系判斷事件間是否存在并發(fā)關(guān)系；第9行，返回事件間的并發(fā)關(guān)系集合。該算法的時(shí)間復(fù)雜度為Θ(N*l+|T|2)，其中N*l為挖掘直接先于關(guān)系集合的時(shí)間復(fù)雜度，|T|2為挖掘并發(fā)關(guān)系集合的時(shí)間復(fù)雜度，N表示事件日志中事件序列的數(shù)量，l表示事件日志中事件序列的平均長(zhǎng)度， ||T表示事件日志中事件的數(shù)量。

3.2 編輯距離

字符串編輯距離算法的計(jì)算不需要考慮字符間的并發(fā)關(guān)系，但對(duì)于事件序列編輯距離來(lái)說(shuō)，事件間的并發(fā)關(guān)系可能會(huì)對(duì)編輯距離產(chǎn)生影響。本節(jié)針對(duì)業(yè)務(wù)過(guò)程的并發(fā)性以及事件序列中可能產(chǎn)生的噪音類型，對(duì)業(yè)務(wù)過(guò)程事件序列編輯距離進(jìn)行了全新定義。

現(xiàn)實(shí)世界中的事件日志中存在三類可能的噪音類型：缺失、冗余、亂序［4～6］，針對(duì)這三類噪音類型，我們分別定義了三類業(yè)務(wù)過(guò)程事件序列基本編輯操作：刪除、插入、交換。

定義4（基本編輯操作）事件序列間的基本編輯操作包括刪除、插入、交換：

·刪除：刪除事件序列中任意一個(gè)事件，如刪除事件序列abc中的事件b后，事件序列變?yōu)閍c；

·插入：在事件序列中任意位置插入一個(gè)已定義或未定義的事件，如對(duì)于事件序列ab，在事件b之后插入一個(gè)未定義的事件c，事件序列變?yōu)閍bc；

·交換：交換事件序列中任意兩個(gè)相鄰且非并發(fā)的事件，如對(duì)于事件序列abcd，事件b，c為非并發(fā)關(guān)系，交換事件b，c，事件序列變?yōu)閍cbd。

特別地，交換兩個(gè)相鄰且并發(fā)的事件對(duì)編輯距離不產(chǎn)生影響。

定義5（編輯距離）給定兩個(gè)事件序列σ與δ，σ與δ間的編輯距離D(σ，δ)是將其中一條事件序列轉(zhuǎn)化為另一條事件序列所需的最少基本編輯操作次數(shù)。

3.3 編輯距離計(jì)算

本節(jié)提出了編輯距離的求解算法，該算法的創(chuàng)新點(diǎn)在于能夠消除事件間并發(fā)關(guān)系對(duì)事件序列編輯距離產(chǎn)生的影響，準(zhǔn)確度量事件序列間的差異。

我們運(yùn)用動(dòng)態(tài)規(guī)劃的思想，用矩陣Dm×n來(lái)存儲(chǔ)計(jì)算過(guò)程中子序列間的編輯距離。假設(shè)待求的兩條事件序列分別為 σ1={t1，t2，t3，…，tm}和 σ2={t1，t2，t3，…，tn}，則矩陣值 D[i][j]（其中 i≤m，j≤n）表示事件序列σ1的子序列σ'1={t1，t2，t3，...，ti} 和事件序列 σ2的子序列={t1，t2，t3，...，tj} 間的編輯距離。矩陣 Dm×n的維度分別為 |σ1|+1 和 |σ2|+1 ，其中 ||σ1表示事件序列σ1的長(zhǎng)度， ||σ2表示事件序列σ2的長(zhǎng)度。矩陣值 D[|σ1|][|σ2|]即為事件序列 σ1與σ2間的編輯距離。

算法的求解過(guò)程為首先對(duì)矩陣D的第零行與第零列進(jìn)行初始化，將第零行中的每個(gè)值賦值為對(duì)應(yīng)的列號(hào)，將第零列中的每個(gè)值賦值為對(duì)應(yīng)的行號(hào)；然后計(jì)算矩陣D中的其他值，計(jì)算過(guò)程需要考慮三類情況，其中情況1、2與字符串編輯距離中考慮的情況相同［7～8］，情況3考慮了并發(fā)事件對(duì)編輯距離的影響，為本文的創(chuàng)新點(diǎn)。這三類情況分別如下。

1）矩陣值D[i][j]等于與其鄰接的上方與左方矩陣值中的最小值加1，用式（1）表示為

D[i][j]=min(D[i][j-1]，D[i-1][j])+1 （1）

2）當(dāng)指針i指向的事件序列σ1中的事件σ1[i]與指針 j指向的事件序列σ2中的事件σ2[j]相同時(shí)，矩陣值D[i][j]等于矩陣值D[i-1][j-1]，用式（2）表示為

首先，對(duì)于矩陣值D[l-1][k-1]，雖然我們不可以直接得出該值，但卻可以通過(guò)矩陣值D[i-1][j-1]間接計(jì)算求得。在事件序列中將事件tl移至事件ti之前且相鄰的位置后，事件序列={t1，t2，...，t(l-1)，tl} 與 σ2'2={t1，t2，t3，...，t(j-1)} 間 的編輯距離將發(fā)生改變，產(chǎn)生的影響可以用式（3）表示為

可得矩陣值 D[l-1][k-1]=D[i-1][j-1]-?(l)-?(k)。

其次，將事件tl移至事件ti之前且相鄰的過(guò)程中，當(dāng)發(fā)生交換的事件與事件tl為非并發(fā)關(guān)系，且該事件在事件 序列={t1，t2，t3，...，t(j-1)} 中出現(xiàn)時(shí)，會(huì)使編輯距離加1，用符號(hào)lnum表示滿足條件的事件的數(shù)量。類似的，用符號(hào)knum表示將事件tk移至事件tj之前且相鄰的過(guò)程中滿足類似條件的事件數(shù)量。

最后，還需要判斷事件ti與tj間的關(guān)系，若為非并發(fā)關(guān)系，則編輯距離加1，否則編輯距離不變。用式（5）表示情況3下的矩陣值為

取上述三類情況中求得的式（1）、（2）、（5）中的最小值為矩陣值D[i][j]的最終值。

算法2設(shè)計(jì)用來(lái)計(jì)算含并發(fā)的業(yè)務(wù)過(guò)程事件序列編輯距離。第 1 行，創(chuàng)建一個(gè)矩陣 D(|σ1|+1)×(|σ2|+1)來(lái)存儲(chǔ)算法計(jì)算過(guò)程中的中間值；第2～3行，使用二重循環(huán)對(duì)矩陣D中的值逐個(gè)進(jìn)行求解；第4～5行，對(duì)第零行與第零列進(jìn)行初始化；第6行，計(jì)算情況1下的矩陣值D[i][j]；第7～8行，計(jì)算情況2下的矩陣值D[i][j]；第9～20行考慮了情況3；第10行計(jì)算式（3）和式（4）；第11行對(duì)lnum，knum和s進(jìn)行初始化；第12～14行對(duì)lnum進(jìn)行計(jì)算，第15～17行對(duì)knum進(jìn)行計(jì)算；第18～19行判斷事件ti與tj之間的關(guān)系，若為并發(fā)關(guān)系，則將s置為0；第20行計(jì)算式（5）；第21行返回待求事件序列編輯距離。該算法的時(shí)間復(fù)雜度為 Θ(|σ1|×|σ2)，其中 ||σ1表示事件序列σ1的長(zhǎng)度， ||σ2表示事件序列σ2的長(zhǎng)度。

4 評(píng)估

4.1 工具實(shí)現(xiàn)

為了評(píng)估本文算法的有效性與高效率，同時(shí)方便相關(guān)領(lǐng)域內(nèi)其他研究人員使用，我們?cè)贓clipse集成環(huán)境中使用Java語(yǔ)言開(kāi)發(fā)了原型工具“BPET?ED”，該工具運(yùn)行在裝有JDK1.8的機(jī)器上，其使用分為以下三個(gè)步驟：

1）日志解析：如圖2所示，在“日志”顯示面板下，點(diǎn)擊“選擇xes日志文件”按鈕，選擇好日志文件之后點(diǎn)擊“解析日志文件”按鈕，可在下方顯示框內(nèi)顯示事件日志中每條事件序列的起始事件、終止事件、長(zhǎng)度與數(shù)量等信息，并在“計(jì)算編輯距離”按鈕下方顯示挖掘事件間關(guān)系消耗的時(shí)間。點(diǎn)擊“顯示事件序列”按鈕可以查看事件序列詳情。

圖2 原型工具

2）編輯距離計(jì)算：選中顯示框中的事件序列，點(diǎn)擊“作為源序列”按鈕可以將該事件序列作為源序列，或者直接在編輯框內(nèi)編輯；同樣地，選擇目標(biāo)序列或直接編輯。點(diǎn)擊“計(jì)算編輯距離”按鈕，計(jì)算源序列和目標(biāo)序列間的編輯距離，并在“計(jì)算編輯距離”按鈕下方顯示計(jì)算編輯距離消耗的時(shí)間。

3）結(jié)果展示：如圖3所示，計(jì)算完編輯距離后，在“結(jié)果”顯示面板下，點(diǎn)擊“顯示結(jié)果”按鈕可以以表格形式查看矩陣的值，矩陣中最右下角的矩陣值即為待求的事件序列編輯距離。

圖3 含循環(huán)業(yè)務(wù)過(guò)程的事件序列編輯距離計(jì)算結(jié)果

4.2 案例分析

圖4為一個(gè)帶循環(huán)且含并發(fā)的業(yè)務(wù)過(guò)程案例，該案例來(lái)源于IBM公司一個(gè)真實(shí)的業(yè)務(wù)過(guò)程。由于該業(yè)務(wù)過(guò)程較大，影響在本文中的呈現(xiàn)效果，因此我們對(duì)案例進(jìn)行了一定程度的簡(jiǎn)化。

圖4 帶循環(huán)且含并發(fā)的Petri網(wǎng)

該業(yè)務(wù)過(guò)程存在兩條并發(fā)支路并包含兩個(gè)循環(huán)節(jié)點(diǎn)t40 與t31 。事件序列σ1={t57，t61，t72，t69，t67，t89，t40，t72，t67，t69，t89，t29} 與事件序列σ2={t57，t61，t72，t67，t69，t89，t29}為該業(yè)務(wù)過(guò)程產(chǎn)生的兩條運(yùn)行實(shí)例。以這兩條事件序列為例，對(duì)編輯距離計(jì)算過(guò)程進(jìn)行分析。

首先按照算法1挖掘出事件間的關(guān)系集合，其中事件間并發(fā)關(guān)系集合為||={t67||t69}；然后按照算法2，創(chuàng)建矩陣D12×7，其中l(wèi)2為事件序列σ1的長(zhǎng)度，7為事件序列σ2的長(zhǎng)度。對(duì)矩陣進(jìn)行初始化之后逐個(gè)求解矩陣中剩余的值。舉例說(shuō)明算法2的求解過(guò)程。

對(duì)于矩陣值D[1][1]，根據(jù)式（1）計(jì)算情況1的值 為D[1][1]=min(D[0][1]，D[1][0])+1=2 ；由 于σ1[1]=σ2[1]，滿足情況 2的條件，按式（2）計(jì)算得D[1][1]=min(D[0][0]，D[1][1])=0 ；因?yàn)楫?dāng)前不存在位置相互交換事件，所以不需要考慮情況3，最終得D[1][1]=0。

對(duì)于矩陣值D[1][2]，根據(jù)式（1）計(jì)算得，D[1][2]=min(D[0][2]，D[1][1])+1=1，當(dāng)前不滿足其他情況的條件，得D[1][2]=1。

對(duì)于矩陣值D[5][5]，指針i，k指向事件e，指針j，l指向事件 c，l=4，i=5，k=4，j=5。計(jì)算式（1）得D[5][5]=min(D[4][5]，D[5][4])+1=2 ；不滿足σ1[5]=σ2[5]，不考慮情況2；由于當(dāng)前存在位置相互交換的事件，計(jì)算式（3）得 ?(l)=D[l][j-1]-D[l-1][j-1]=1；計(jì)算式（4）得 ?(k)=D[i-1][k]-D[i-1][k-1]=1；在事件序列σ1中，事件t69與t67之間無(wú)其他事件，得lnum=0；在事件序列σ2中，事件t67與t69之間沒(méi)有其他事件，得knum=0；事件t67與t69為并發(fā)關(guān)系，不對(duì)編輯距離產(chǎn)生影響，計(jì)算式（5），得D[5][5]=D[i-1][j-1]-?(l)-?(k)+lnum+knum+{0，1}=0；取式（5）與式（1）的最小值0為D[5][5]的最終值。

對(duì)于矩陣值D[9][5]，指針i，k指向事件c，指針j，l指向事件 s，l=4，i=9，k=4，j=5。計(jì)算式（1），得D[9][5]=min(D[9][4]+1，D[8][5]+1)=4 ；由于不滿足σ1[9]=σ2[5]，無(wú)需計(jì)算式（2）；計(jì)算式（3）得 ?(l)=D[l][j-1]-D[l-1][j-1]=1；計(jì)算式（4）得 ?(k)=D[i-1][k]-D[i-1][k-1]=-1；在事件序列σ1中，事件t69與t67之間存在事件t67，t89，t40，t72，其中事件t72與t69為非并發(fā)關(guān)系，且t72在事件序列={t57，t61，t72}中出現(xiàn)過(guò)，得lnum=1；在事件序列σ2中，事件t67與t69之間不存在事件，得knum=0；事件t67與t69為并發(fā)關(guān)系，對(duì)編輯距離不產(chǎn)生影響，計(jì)算式（5）得 D[9][5]=D[i-1][j-1]-?(l)-?(k)+lnum+knum+{0，1}=5；取式（1）與式（5）的最小值4為D[9][5]的最終值。

矩陣計(jì)算完成后可得圖3，求得事件序列σ1與σ2間的編輯距離D[12][7]=5，該值恰好等于業(yè)務(wù)過(guò)程中循環(huán)部分的事件序列長(zhǎng)度，表明計(jì)算結(jié)果正確。

我們將該實(shí)例運(yùn)行在Inter（R）3.60GHz處理器，16GB內(nèi)存的Windows8.1系統(tǒng)的臺(tái)式機(jī)上。經(jīng)過(guò)100次計(jì)算，統(tǒng)計(jì)得到平均事件關(guān)系挖掘時(shí)間為0.62ms，平均事件序列編輯距離計(jì)算時(shí)間為0.49ms，表現(xiàn)了算法具有很高的效率。

5 結(jié)語(yǔ)

本文針對(duì)業(yè)務(wù)過(guò)程的并發(fā)性以及事件日志中可能存在的三類噪音類型，定義了三類事件序列基本編輯操作，并給出了業(yè)務(wù)過(guò)程事件序列編輯距離的全新定義。基于該定義，在字符串編輯距離求解算法基礎(chǔ)上，提出了一種計(jì)算含并發(fā)的業(yè)務(wù)過(guò)程事件序列編輯距離的算法。該算法能夠有效處理含并發(fā)的業(yè)務(wù)過(guò)程，忽略由并發(fā)事件交換對(duì)編輯距離產(chǎn)生的影響。我們將該算法實(shí)現(xiàn)在“BPETED”工具中，并通過(guò)一個(gè)實(shí)際案例分析闡明了算法的有效性和高效率。