基于Petri網(wǎng)工作流模型展開樹的路徑序列相似性算法

許山山 史涯晴 簡開宇 魏居尚 張文燾

摘 要：在實際的數(shù)據(jù)遷移項目中，為了解決數(shù)據(jù)映射的問題，需要確定兩個工作流模型之間的相似度。從工作流模型的相似性方面進(jìn)行分析闡述，提出了基于Petri網(wǎng)的工作流模型展開樹的路徑序列相似性算法。首先采用深度優(yōu)先搜索算法和動態(tài)規(guī)劃算法對模型進(jìn)行搜索；其次通過提出的算法獲取展開樹的所有路徑序列；最后利用編輯距離算法計算兩個模型序列之間的兩兩相似度，進(jìn)而完成模型相似性計算；相較于其他的主流相似度算法，主要優(yōu)點在于可以精確計算得到模型部分結(jié)構(gòu)和行為相似度，可以更好地確定流程間映射，從而找到數(shù)據(jù)映射的解決方法。實驗結(jié)果表明，該方法較主流的基于模型結(jié)構(gòu)和行為相似性的算法，計算合理性和準(zhǔn)確性有很大提升。

關(guān)鍵詞：Petri網(wǎng)；相似性度量；展開樹；路徑序列

中圖分類號：TP391?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號：1001-3695（2024）01-025-0170-07

doi：10.19734/j.issn.1001-3695.2023.05.0193

Similarity algorithm of path sequence based on Petri net workflow model unfolding tree

Abstract：In the actual data migration project，in order to solve the problem of data mapping，it is necessary to determine the similarity between the two workflow models.This paper analyzed and expounded the similarity of workflow model，and proposed a path sequence similarity algorithm for the unfolding tree of workflow model based on Petri net.Firstly，it used the deep-first search algorithm and dynamic programming algorithm to search the model，and then obtained all path sequences of the unfolding tree by the proposed algorithm.Finally，it used the edit distance algorithm to calculate the pairwise similarity between the two model sequences，and then completed the model similarity calculation.Compared with other mainstream similarity algorithms，the main advantage is that the partial structure and behavior similarity of the model could be accurately calculated，which could better determine the mapping between processes，so as to find a solution to data mapping.The experimental results show that the proposed method is more reasonable and accurate than the mainstream algorithms based on model structure and behavior similarity.

Key words：Petri net；similarity measure；unfolding tree；path sequence

0 引言

業(yè)務(wù)流程（business process）是由不同的人或機(jī)器為實現(xiàn)某種有價值的目標(biāo)而共同完成的一系列活動的集合?；顒优c活動之間的順序存在嚴(yán)格的先后限定，但是可以在時間或空間上有較大跨度的轉(zhuǎn)移，且活動的內(nèi)容、方式、責(zé)任等都必須有明確的安排和界定，以便確保不同活動在不同崗位角色之間能夠進(jìn)行正常地運(yùn)轉(zhuǎn)與轉(zhuǎn)換。簡單來說，業(yè)務(wù)流程就是用于描述組織提供的服務(wù)以及實現(xiàn)這些服務(wù)的內(nèi)部流程［1］。業(yè)務(wù)流程管理（business process management，BPM）起源于軟件工程和計算機(jī)科學(xué)［2］，是將信息技術(shù)和管理科學(xué)的知識結(jié)合起來，并應(yīng)用于運(yùn)營和改善業(yè)務(wù)流程的學(xué)科［3，4］。BPM可以被視為工作流管理（workflow management，WFM）的擴(kuò)展，因為工作流管理只在乎業(yè)務(wù)流程的自動化，而BPM不僅在乎流程自動化和流程分析，而且還在乎運(yùn)用管理和工作組織，考慮了人為因素和管理因素［5］。

業(yè)務(wù)流程模型，一般簡稱流程模型，是BPM的基礎(chǔ)，采用大量的符號來建模操作業(yè)務(wù)流程以達(dá)到處理流程實例［6］的目的，成熟的符號工具有Petri網(wǎng)［7］、BPMN［8］、UML［9］和EPC［10］，使用這些工具可以將業(yè)務(wù)流程的過程節(jié)點和執(zhí)行方式抽象成具體的符號，可以有序構(gòu)造成工作流程模型，并且還可以利用仿真軟件進(jìn)行模型仿真。

近年來現(xiàn)代企業(yè)的快速發(fā)展離不開高效而無冗余的業(yè)務(wù)流程進(jìn)行支撐，業(yè)務(wù)流程是企業(yè)的重要組成部分，更是企業(yè)的寶貴知識資產(chǎn)。結(jié)構(gòu)良好的流程模型被廣泛應(yīng)用于辦公自動化、企業(yè)信息化、電子政務(wù)和電子商務(wù)等領(lǐng)域。大型集團(tuán)企業(yè)常常維護(hù)著非常大的流程模型庫，其中包含成千上萬個流程模型，這些模型涵蓋了企業(yè)架構(gòu)、產(chǎn)品周期、工程管理、網(wǎng)絡(luò)服務(wù)和日常辦公等眾多業(yè)務(wù)領(lǐng)域［11］。如何有效地進(jìn)行流程模型的比較、索引和搜索變得具有挑戰(zhàn)性。業(yè)務(wù)模型的相似性變得非常重要，需要合理的算法保證模型的檢索［12］。因此，在計算業(yè)務(wù)流程模型的相似度時，主要方法有結(jié)構(gòu)相似度、行為相似度和語義相似度［13］。

然而，現(xiàn)有的相似性算法存在諸多問題，主要包括共同相似性性質(zhì)不足、耗時成本高、存在非自由選擇等特定結(jié)構(gòu)不可用等。

文獻(xiàn)［11］中提出相似性算法至少應(yīng)該滿足五個屬性，分別是互斥結(jié)構(gòu)漂移不變性、跨度負(fù)相關(guān)性、無關(guān)遞減性、循環(huán)序列長度負(fù)相關(guān)性和順序結(jié)構(gòu)漂移不變性?，F(xiàn)有的算法，如TAR［14］、PTS［15］、行為特征［16］，不能滿足所有屬性。

Zha等人［14］提出了一種基于變遷緊鄰關(guān)系（transition adjacency relation，TAR）的行為相似性度量算法，該算法關(guān)注成對變遷的緊鄰關(guān)系，即變遷a和b是順序執(zhí)行的，a和b構(gòu)成的元組〈a，b〉則稱為TAR，但是該算法只關(guān)注兩兩變遷之間的TAR，利用TAR集合的Jaccard系數(shù)來評估流程模型的相似性。然而，TAR算法的不足之處在于其不能處理諸如非自由選擇和不可見任務(wù)之類的特定結(jié)構(gòu)，只能滿足順序結(jié)構(gòu)漂移不變性。

Wang等人［15］使用主變遷序列（principal transition sequences，PTS）概念來計算相似度，即PTS算法，主要區(qū)分三種主變遷序列，分別是非循環(huán)結(jié)構(gòu)、優(yōu)先循環(huán)結(jié)構(gòu)和無限循環(huán)結(jié)構(gòu)，以此來計算模型行為相似度。PTS算法首先計算最長的公共子序列，然后用子序列百分比的加權(quán)和表示相似度。對于具有大量分支的并發(fā)結(jié)構(gòu)，PTS非常耗時，而且在具有循環(huán)的業(yè)務(wù)流程中，PTS的使用效果并不理想，因此也不滿足循環(huán)序列長度負(fù)相關(guān)性。

Kunze等人［16］介紹了基于行為特征（behavioral profile）的相似度算法，行為特征算法定義了一個弱序來擴(kuò)展相鄰關(guān)系的語義。弱序關(guān)系包括嚴(yán)格順序關(guān)系、排他關(guān)系、交錯關(guān)系，在此基礎(chǔ)上，本文提出了五種基本相似性度量，分別是排他相似性、嚴(yán)格順序相似性、交錯順序相似性、擴(kuò)展嚴(yán)格順序相似性和擴(kuò)展交錯順序相似性。行為特征算法缺點在于其不能有效地處理不可見任務(wù)，也不能區(qū)分來自并行結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的行為模式，也不滿足跨度負(fù)相關(guān)性。

以上幾種流程模型相似性度量方法都有著不同程度的缺陷，或者不能完整處理各種結(jié)構(gòu)，或者計算效率低下，或者相似性計算結(jié)果難以直觀理解。因此，有必要提出一種新的行為相似性度量方法來解決上述問題，從而直觀、準(zhǔn)確、高效地度量任意合理流程模型間的結(jié)構(gòu)和行為相似性。

本文提出一種全新的流程模型行為相似性度量方法，路徑序列相似算法（path sequence similarity algorithm，PSSA），通過流程模型展開樹的路徑序列來表達(dá)流程模型結(jié)構(gòu)和行為，進(jìn)而計算兩個模型間的結(jié)構(gòu)和行為相似度。通過實驗證明：PSSA算法能夠全部滿足上述五個性質(zhì)，優(yōu)于TAR算法、行為特征算法和PTS算法。

1 相關(guān)知識

本章對本文使用的一些基本概念進(jìn)行介紹，主要是表達(dá)業(yè)務(wù)流程模型的Petri網(wǎng)。

在建模中，采用條件和事件的概念，庫所表示條件，變遷表示事件。變遷（事件）有一定數(shù)量的前置庫所和后置庫所，分別表示該事件的前置條件和后置條件。一個庫所的令牌的存在被解釋為持有與該庫所相關(guān)條件的真實性。在另一種解釋中，k個令牌被放置在一個庫所，以表明k個數(shù)據(jù)項或資源是可用的。變遷及其輸入庫所和輸出庫所的一些典型解釋［7］如表1所示，具體實例如圖1所示。

下面給出Petri網(wǎng)的正式定義：

定義1 Petri網(wǎng)。Petri網(wǎng)是一個五元組，N=（P，T，F(xiàn)，W，M0），其中：P={p1，p2，…，pm}是一組有限的庫所集，T={t1，t2，…，tn}是一個有限的變遷集，F(xiàn)（P×T）∪（T×P）→{0，1}是一組有向弧，W：F→{0，1，2，3，…}是權(quán)重函數(shù)，M0：P→{0，1，2，3，…}是初始標(biāo)記，P∩T=，P∪T=。

簡單Petri網(wǎng)是一個三元組，可以不考慮權(quán)重函數(shù)和初始標(biāo)記，Ns=（P，T，F(xiàn)），其中：P={p1，p2，…，pm}是一組有限的庫所集，T={t1，t2，…，tn}是一個有限的變遷集，F(xiàn)（P×T）∪（T×P）→{0，1}是一組有向弧，本文主要是針對簡單Petri網(wǎng)進(jìn)行研究和實驗。

定義2 前綴集合和后綴集合。對于N中的一個節(jié)點x的前綴集合{y∈P∪T|F（y，x）=1}，用·x表示，而x的后綴集合為{y∈P∪T|F（x，y）=1}，用x·表示。

如果沒有任何特定初始標(biāo)記的Petri網(wǎng)結(jié)構(gòu)Nw=（P，T，F(xiàn)，W）記為Nw，所以具有給定初始標(biāo)記的Petri網(wǎng)可以用（N，M0）表示。通常庫所和變遷可以稱為節(jié)點，而F則是節(jié)點之間的有向弧，因此，Petri網(wǎng)可以被認(rèn)為是一個有向圖，而圖中的路徑通常是一個非空的節(jié)點序列，沒有重復(fù)，從每個節(jié)點到下一個節(jié)點都有一條?。ú豢紤]首尾節(jié)點）［17］。

2 Petri網(wǎng)展開樹

2.1 Petri網(wǎng)展開樹的定義

定義3 樹Petri網(wǎng)。如果存在一個簡單Petri網(wǎng)Ns=（P，T，F(xiàn)），在忽略庫所和變遷的差異時，弧從父節(jié)點到子節(jié)點，并且根節(jié)點和葉節(jié)點都是庫所，可以將其稱之為樹Petri網(wǎng)［18］，如圖2所示。根節(jié)點稱為根庫所，葉節(jié)點稱為葉庫所。樹Petri網(wǎng)的逆網(wǎng)稱為逆樹Petri網(wǎng)。

Winskel［19］給出了Petri網(wǎng)“折疊”和“展開”的定義，其考慮的映射是從網(wǎng)絡(luò)到網(wǎng)絡(luò)的同態(tài)，這里定義的同態(tài)在文章中稱為“折疊”。直觀地說，從網(wǎng)絡(luò)N1到N2的同態(tài)，即N1可以折疊到N2的一部分上，或者換句話說，可以通過展開N2的一部分來獲得N1。

對于一個有根庫所和葉庫所的Petri網(wǎng)N而言，可以將其“展開”成一棵樹Petri網(wǎng)，如圖3所示，圖3（b）的展開樹中路徑的根節(jié)點是從圖3（a）中根庫所開始的，樹Petri網(wǎng)的節(jié)點被標(biāo)記為與之對應(yīng)Petri網(wǎng)的節(jié)點。然而有向Petri網(wǎng)可能存在環(huán)狀結(jié)構(gòu)［17］，如圖4（a）所示，因此其展開過程可以在帶環(huán)處無限循環(huán)，可以產(chǎn)生不同的樹Petri網(wǎng)，但是最小標(biāo)記樹只有唯一一棵，對于所有帶環(huán)的有向Petri網(wǎng)只考慮在環(huán)狀結(jié)構(gòu)處循環(huán)一次，如圖4（b）所示。這種將原Petri網(wǎng)通過一定形式轉(zhuǎn)換得到的樹Petri網(wǎng)稱為Petri網(wǎng)的展開樹。

2.2 展開樹的路徑序列

定義4 展開樹的路徑序列。令Nt=（P，T，F(xiàn)）是Petri網(wǎng)展開樹，Σ是其所有可能執(zhí)行路徑序列的集合。對于任意兩個任務(wù)a，b∈T（a，b可能是同一個任務(wù)），與其相關(guān)的三個觸發(fā)條件x，y，z∈P（x，y，z可能是同一個條件），表示因果關(guān)系的有向弧→∈F，Σ中所有形如…x→a→y→b→z…的執(zhí)行路徑序列，即為樹Petri網(wǎng)的路徑序列。

示例1 展開樹的路徑序列。圖1所示的樹Petri網(wǎng)路徑序列集S如下所示。

性質(zhì)1 結(jié)構(gòu)差異大的兩個業(yè)務(wù)流程模型，對應(yīng)展開樹的路徑序列差異也越大。

性質(zhì)2 采用展開樹路徑序列能夠處理業(yè)務(wù)流程模型Petri網(wǎng)中包含的不可見任務(wù)、非自由選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)及各種基本控制流結(jié)構(gòu)。

2.3 Petri網(wǎng)展開樹的性質(zhì)

性質(zhì)3 Petri網(wǎng)展開樹Nt=（P，T，F(xiàn)），對于根庫所Proot，·Proot=和p∈P{Proot}，|·p|=1。如果P是葉庫所，p·=，否則|p·|≥1。對于t∈T，|t·|≥1和|·t|=1。對于兩個標(biāo)記M0、M1，M1可從N中的M0到達(dá)當(dāng)且僅當(dāng)M0可從N中的M1到達(dá)N-1。

性質(zhì)4 展開樹是Petri網(wǎng)業(yè)務(wù)流程模型結(jié)構(gòu)的一種表示方法，與模型節(jié)點存在一對一關(guān)系。

3 Petri網(wǎng)展開樹的路徑序列相似度算法

在現(xiàn)有的相似度算法中，并沒有考慮到庫所對于業(yè)務(wù)流程模型的影響，而是將變遷作為主要的研究對象，通過研究業(yè)務(wù)流程模型之間的變遷序列以及帶有權(quán)重的變遷序列對，計算出彼此之間的相似度值?？紤]到庫所可能存在對于業(yè)務(wù)流程模型相似度的影響，提出了包含庫所和變遷的展開樹路徑序列，通過展開樹的路徑序列算法獲取業(yè)務(wù)流程模型的所有可能存在的路徑序列，最后借助編輯距離公式對路徑序列進(jìn)行計算，算出兩個業(yè)務(wù)流程模型之間的相似度值，下面進(jìn)行詳細(xì)說明。

3.1 展開樹的路徑序列算法

3.1.1 展開樹的路徑序列的算法步驟

對于無環(huán)Petri網(wǎng)，圖3（b）展開樹中路徑的根庫所是從圖3（a）中根節(jié)點開始的，其余節(jié)點依次對應(yīng)，根據(jù)展開樹的路徑序列算法，在圖3（a）上構(gòu)造一個開始變遷Ts和一個結(jié)束變遷Te，從Ts到Te開始進(jìn)行順向節(jié)點廣度優(yōu)先搜索，得到順向最短路徑S：Ts→p0→t0→p1→Te，從Te到Ts開始進(jìn)行逆向節(jié)點廣度優(yōu)先搜索，得到順向最短路徑S′：Te→p1→t0→p0→Ts，得到一個復(fù)合主干路徑S主：Ts→p0→t0→p1→Te，最終得到簡單的殘差網(wǎng)絡(luò)G′：兩條邊和一個變遷t1，選取一條邊E進(jìn)行廣度優(yōu)先搜索，從起始邊節(jié)點u到結(jié)束變遷Te得到一條最短路徑S殘：p1→Te，從結(jié)束邊節(jié)點v到開始變遷Ts得到一條最短路徑S′殘：t1→p0→Ts，將最短路徑S殘、S′殘和邊E進(jìn)行綜合，得到一條完整路徑S主：Ts→p0→t1→p1→Te，因此綜上所述可以得到兩條路徑序列，分別是Ts→p0→t0→p1→Te和Ts→p0→t1→p1→Te。下面給出展開樹的路徑序列算法步驟過程如算法1所示。

算法1 獲取展開樹的路徑序列

輸入：Petri網(wǎng)G。

輸出：Petri網(wǎng)展開樹的路徑序列。

a）在原網(wǎng)G上構(gòu)造一個開始變遷Ts和一個結(jié)束變遷Te，并獲取其位置；

b）從開始變遷Ts到結(jié)束變遷Te進(jìn)行Petri網(wǎng)G的順向節(jié)點廣度優(yōu)先搜索，得到順向最短路徑S；

c）從結(jié)束變遷Te到開始變遷Ts進(jìn)行Petri網(wǎng)G的逆向節(jié)點廣度優(yōu)先搜索，得到逆向最短路徑S′；

d）將最短路徑S和S′進(jìn)行綜合，得到一個復(fù)合主干路徑S主，從Petri網(wǎng)G中去除復(fù)合主干路徑S主，得到一個殘差網(wǎng)絡(luò)G′，如果殘差網(wǎng)絡(luò)G′沒有其他結(jié)構(gòu)，則結(jié)束算法，否則繼續(xù)下面步驟；

e）如果殘差網(wǎng)絡(luò)G′中仍然存在其他復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，則重復(fù)進(jìn)行步驟a）～d），直到得到最簡單的順序結(jié)構(gòu)殘差網(wǎng)絡(luò)G′；

f）如在G′中選取邊E節(jié)點對Petri網(wǎng)G進(jìn)行廣度優(yōu)先搜索，從起始邊節(jié)點u到結(jié)束變遷Te得到一條最短路徑S殘，從結(jié)束邊節(jié)點v到開始變遷Ts得到一條最短路徑S′殘；

g）將最短路徑S殘、S′殘和邊E進(jìn)行綜合，得到一條完整路徑S全；

h）重復(fù)循環(huán)步驟a）～g），直至找到所有路徑。

然而對于存在環(huán)狀結(jié)構(gòu)的Petri網(wǎng)，如圖4（a）所示，雖然其展開過程可以在帶環(huán)處無限循環(huán)，但是在本文中，所有帶環(huán)的Petri網(wǎng)只考慮在環(huán)狀結(jié)構(gòu)處循環(huán)一次，如圖4（b）所示，根據(jù)展開樹的路徑序列算法可以得到8條路徑序列，分別是

Ts→p0→t0→p2→t3→p5→t5→p0→Te

Ts→p0→t0→p2→t3→p6→t6→p1→Te

Ts→p0→t1→p3→t4→p5→t5→p0→Te

Ts→p0→t1→p3→t4→p6→t6→p1→Te

Ts→p1→t2→p4→t3→p5→t5→p0→Te

Ts→p1→t2→p4→t3→p6→t6→p1→Te

Ts→p1→t2→p4→t4→p5→t5→p0→Te

Ts→p1→t2→p4→t4→p6→t6→p1→Te

3.1.2 展開樹的路徑序列的算法理論證明

為了說明本文所提展開樹的路徑序列算法的有效性，本節(jié)從以下6個方面對其進(jìn)行理論證明。

1）Petri網(wǎng)特點

定義5 存在一個或多個開始庫所Ps，在Ps之前加入一個開始變遷Ts；存在一個或多個結(jié)束庫所Pe，在Pe之后加入一個結(jié)束變遷Te，則整個Petri網(wǎng)業(yè)務(wù)流程圖上只有一個開始變遷和一個結(jié)束變遷。

定義6 設(shè)Petri網(wǎng)G=（P，T，E），Petri網(wǎng)中存在業(yè)務(wù)流程節(jié)點V=（P，T），P為庫所和T為變遷，存在P→T（或者T→P）的有向邊，記為E=（P，T）（或者E=（T，P），E為有向邊，則對于v∈V，存在路徑Ts→Pv→Tv→P′v→Te都是可達(dá)的。

性質(zhì)5 設(shè)有向邊e=（m，n），e∈E，則m≠n，且m與n不能同時為庫所或者變遷。

2）廣度優(yōu)先搜索

定義7 從Ts開始，按照廣度優(yōu)先搜索算法進(jìn)行搜索，獲得一顆廣度優(yōu)先生成樹，Gπ=（Vπ，Eπ），設(shè)節(jié)點v∈V，則v與Ts的距離記為v.d，Ts至v的最短路徑記為π（v）Gπ，v.d=length（π（v））。

定義8 從Te開始，按照邊的逆方向進(jìn)行廣度優(yōu)先搜索，獲得一顆廣度優(yōu)先生成樹，Gπi=（Vπi，Eπi），設(shè)節(jié)點v∈V，則v與Te的距離記為v.di，v至Te的最短路徑記為πi（v）Gπi，v.di=length（πi（v））。

性質(zhì)6 若有向邊e=（m，n），e∈E，則m.d≠n.d，m.di≠n.di。

證明 若m.d=n.d，則Ts經(jīng)過相同數(shù)量的邊可達(dá)m和n，即m和n同為庫所或變遷，與性質(zhì)5矛盾；同理m.di≠n.di。

性質(zhì)7 正向搜索距離Te.d，逆向搜索距離Ts.d，則Ts.di=Te.d都等于最短路徑Vπ（Te）和Vπi（Ts）的長度D（常數(shù)）。

性質(zhì)8 對于v∈V，則有v.d+v.di≥D。

性質(zhì)9 若v.d+v.di>D，則π（v）∪πi（v）不是Ts至Te的最短路徑；若π（v）∪πi（v）是Ts至Te的最短路徑，則v.d+v.di=D；若v.d+v.di=D，則π（v）∪πi（v）是Ts至Te的最短路徑。

證明 π（v）中v和Ts是連通的，存在e=（Ts，v），e∈E；πi（v）中v和Te是連通的，存在e=（v，Te），e∈E，則π（v）∪πi（v）中，存在變遷路徑Ts→v→Te；又因為v.d+v.di=D，所以π（v）∪πi（v）是一條最短路徑。

3）無環(huán)子圖

定義9 設(shè)V={v|v∈V，v.d+v.di=D}，E′={（m，n）|（m，n）∈E，m∈V′，n∈V′，m.d

4）動態(tài)規(guī)劃算法

求得G′中Ts到業(yè)務(wù)流程節(jié)點v的所有路徑π′（v）和節(jié)點v到Te的所有路徑π′i（v），因此π′（Ts）=π′（Te）。每一次Ts到業(yè)務(wù)流程節(jié)點v的路徑以及業(yè)務(wù)流程節(jié)點v到Te的路徑會暫時存儲起來，當(dāng)具有重復(fù)路徑時直接進(jìn)行調(diào)用，大大降低了算法的時間消耗。

5）路徑組合獲取

定義10 設(shè)E″=E-E′，對（m，n），（m，n）∈E′，在π（m）中找到距離m最近的，∈V′，以及到m的路徑（，n），在πi（n）中找到距離n最近的，∈V′，以及n到的路徑（n，），獲得路徑（，）=→m→n→，記為π″。對（Ts，）∈π′（），（，Te）∈π′i（）和（，）∈π″，構(gòu)造路徑Ts→→→Te，記為π。

雖然π在E″中只能保證所有的邊經(jīng)過一次，所有的環(huán)也只經(jīng)過一次，不能保證組合是完全可能的，但是可保證G′的所有的可能組合。

6）路徑遍歷迭代

若對G″=（V，E″）有遍歷全部可能路徑的需求，可將3.2.5節(jié)中獲得的π″，每一個相同的（，）構(gòu)建成一個新的Petri網(wǎng)，繼而重復(fù)前述步驟即可。

3.2 展開樹的路徑序列相似度算法

在相似度計算方面，存在語義相似度、行為相似度和結(jié)構(gòu)相似度，由于本文在實際應(yīng)用中主要針對的是業(yè)務(wù)流程的整體結(jié)構(gòu)映射，主要研究的側(cè)重點是結(jié)構(gòu)相似度，為了找到最相似的路徑序列，分別將兩個業(yè)務(wù)流程模型的路徑進(jìn)行結(jié)構(gòu)相似度比較，所以通過展開樹的路徑序列算法得到業(yè)務(wù)流程模型的Petri網(wǎng)路徑序列。下面利用路徑序列進(jìn)行相似度值的計算，將這個過程稱為展開樹的路徑序列相似度算法（path sequence similarity algorithm，PSSA）。為了比較兩個模型的整體相似度，在路徑兩兩相似度的基礎(chǔ)之上，采用所有單條路徑序列相似度求取平均值的結(jié)果作為整體相似度的一個參考值，具體如算法2所示，PSSA算法總體流程如圖5所示。

算法2 業(yè)務(wù)流程模型相似度計算

輸入：Petri網(wǎng)展開樹的路徑序列。

輸出：業(yè)務(wù)流程相似度值。

a）利用算法2分別讀取兩個業(yè)務(wù)流程Petri網(wǎng)模型轉(zhuǎn)換后的樹Petri網(wǎng)的全部路徑序列Si（i=1，2，…，n）和Sj（j=1，2，…，m）；

b）分別取Si中一條路徑與Sj中每一條路徑進(jìn)行編輯距離計算得到Dij（i=1，2，…，n；j=1，2，…，m），求取路徑的長度l=max（|Si|，|Sj|）；

示例2 展開樹的路徑序列相似度的計算。計算圖6中業(yè)務(wù)流程模型N1和N2的相似性。展開樹的路徑序列集S如下所示。

a）可以得到N1和N2的全部路徑序列：

b）取S（N1）中的路徑序列Ts→p0→t0→p1→t2→p2→Te與S（N2）的四條路徑序列進(jìn)行編輯距離的計算，得到編輯距離分別為0，1，1，2；再取S（N1）中的路徑序列Ts→p0→t1→p1→t2→p2→Te與S（N2）的四條路徑序列進(jìn)行編輯距離的計算，得到編輯距離分別為1，2，0，1；路徑的長度l=max（|S（N1）|，|S（N2）|）=7；

因為路徑序列是業(yè)務(wù)流程模型通過一定形式轉(zhuǎn)換得到的，所以綜上所述，可以等價地認(rèn)為路徑序列相似度值0.86即為業(yè)務(wù)流程模型N1和N2的相似度值。

4 實驗設(shè)計與分析

4.1 實驗環(huán)境

本文使用臺式PC作為測試環(huán)境，電腦運(yùn)行的是Windows 11 家庭中文版，配備了11th Gen Intel CoreTM i5-11320H @ 3.20 GHz 3.19 GHz的處理器和16 GB內(nèi)存。在PyCharm中創(chuàng)建工程，采用Python語言實現(xiàn)路徑序列算法以及相似性算法的功能，在此基礎(chǔ)上，利用Tina軟件構(gòu)建了30個業(yè)務(wù)流程模型驗證路徑序列完整性，實驗的具體數(shù)據(jù)和結(jié)論參看4.2.1節(jié)內(nèi)容。在30個業(yè)務(wù)流程模型中抽取了部分典型的業(yè)務(wù)流程模型進(jìn)行擴(kuò)展用于相似度五種性質(zhì)的比較實驗，因為這個比較實驗的模型與Wang等人［19］的相同，除了本文算法的數(shù)據(jù)是通過計算得到，其余相似性算法的對比數(shù)據(jù)均參考其文章中的數(shù)據(jù)，實驗的具體數(shù)據(jù)和結(jié)論參看4.2.2節(jié)內(nèi)容。

4.2 實驗設(shè)計

4.2.1 路徑序列完整性驗證實驗

利用Petri網(wǎng)構(gòu)建30個業(yè)務(wù)流程模型，采用人工統(tǒng)計、普通廣度優(yōu)先搜索算法和展開樹路徑序列算法對業(yè)務(wù)流程模型的路徑序列進(jìn)行數(shù)量統(tǒng)計。利用節(jié)點和邊的總數(shù)來表示業(yè)務(wù)流程模型的大小，一般而言，模型越大復(fù)雜程度越大，但是對于一些節(jié)點和邊數(shù)量較多的順序結(jié)構(gòu)模型并不能反映結(jié)構(gòu)的復(fù)雜度，因此需要考慮帶環(huán)狀結(jié)構(gòu)的業(yè)務(wù)流程模型。在一些較小的業(yè)務(wù)流程模型中，帶環(huán)狀結(jié)構(gòu)的模型利用展開樹路徑序列算法可以正確識別；在一些較大的業(yè)務(wù)流程模型中，展開樹路徑序列算法的平均識別準(zhǔn)確率也達(dá)到了72.6%。

從圖7中可以看出人工統(tǒng)計的路徑序列數(shù)量是最多、最完整的，但是其缺點是在業(yè)務(wù)流程模型存在大量節(jié)點和邊的情況下，其人工統(tǒng)計難度大且耗時巨大；從圖中可以看出，在一些簡單的模型中，主要是節(jié)點和邊的數(shù)量約在20個以下時，采用普通廣度優(yōu)先算法可以獲取完整的路徑序列，在數(shù)量上幾乎與人工統(tǒng)計數(shù)量以及路徑序列算法相同，但是在處理一些復(fù)雜度較大的模型中，尤其是在節(jié)點和邊的數(shù)量大量增加時，其路徑序列獲取能力差，根本達(dá)不到業(yè)務(wù)要求；在使用展開樹路徑序列算法的情況下，只要是簡單的順序結(jié)構(gòu)的業(yè)務(wù)流程模型，即使存在大量的節(jié)點和邊，獲取的路徑序列與人工統(tǒng)計的數(shù)量相同，在時間效率上明顯要優(yōu)于人工統(tǒng)計。隨著節(jié)點和邊的數(shù)量增加，人工統(tǒng)計將會變得難上加難，但是本文算法依然可以快速實現(xiàn)路徑序列的統(tǒng)計。

4.2.2 五種屬性的對比實驗

在文獻(xiàn)［11］中提到了相似性算法的五個屬性。在本節(jié)中，使用這些屬性對展開樹PSSA算法和其他主流模型相似性算法進(jìn)行對比。

屬性1 互斥結(jié)構(gòu)漂移不變性。如圖8所示，給定導(dǎo)出的互斥結(jié)構(gòu)的業(yè)務(wù)流程模型，無論在何處添加新的轉(zhuǎn)換，新模型和舊模型的相似性都不會改變，即sim（N1，N2）=sim（N1，N3）=sim（N1，N4）。

如圖8所示，假如N1中的變遷數(shù)為10個，然后在每個變遷處添加新的變遷分支，構(gòu)成一種互斥結(jié)構(gòu)模型，可以得到10個新的業(yè)務(wù)流程模型N2～N11。

相似度結(jié)果如圖9所示，隨著新添加的變遷位置的變化，相似性不會改變，因此證明了PSSA滿足屬性1。此外，行為特征算法和PTS也滿足該屬性，但是算法計算的相似度值的精度并沒有PSSA高，唯一不滿足屬性的是TAR算法。

屬性2 跨度負(fù)相關(guān)性。如圖10所示，給定一個業(yè)務(wù)流程模型，隨著新的互斥分支跨度的增大，新模型與舊模型的相似度逐漸減小，即sim（N1，N2）>sim（N1，N3）。假如N1中的變遷數(shù)為10個，然后在每個變遷處添加新的變遷分支，構(gòu)成一種互斥結(jié)構(gòu)模型，可以得到10個新的業(yè)務(wù)流程模型N2～N11。

相似度結(jié)果如圖11所示，隨著新添加的變遷位置的變化，相似性會呈遞減狀態(tài)，因此證明了PSSA滿足屬性2。此外，行為特征算法和PTS也滿足該性質(zhì)，但是隨著跨度的變大，模型的相似程度肯定會越來越小，也就是說算法計算的相似度值的遞減性并沒有PSSA好，而TAR算法保持不變，最后還呈上升趨勢，因此不滿足此條屬性。

屬性3 無關(guān)遞減性。如圖12所示，給定一個業(yè)務(wù)流程模型，在原模型的同一個變遷上添加新的分支，添加的分支越多，新模型與舊模型的相似度越低，即sim（N1，N2）>sim（N1，N3）。在每個變遷處添加新的變遷分支，在變遷t2處添加一個變遷得到N2，在變遷t2處添加兩個變遷得到N3，依此類推，添加10個變遷為止，可以得到10個新的業(yè)務(wù)流程模型N2～N11。

相似度結(jié)果如圖13所示，隨著新添加的變遷位置的變化，相似性會逐漸變小，因此證明了PSSA滿足屬性3。此外，TAR、行為特征算法和PTS也滿足該性質(zhì)。

屬性4 循環(huán)序列長度負(fù)相關(guān)性。如圖14所示，給定一個業(yè)務(wù)流程模型，在原模型上增加一個新的環(huán)路分支，該分支的跨度越大，新模型與舊模型的相似度逐漸減小，即sim（N1，N2）>sim（N1，N3）。

假如N1中的變遷數(shù)為10個，增加一個新的跨躍t1的環(huán)路分支，然后是t2、t3，依此類推可以得到10個新的業(yè)務(wù)流程模型N2～N12。

相似度結(jié)果如圖15所示，隨著新添加的變遷位置的變化，相似性會逐漸減小，因此證明了PSSA滿足屬性4。此外，行為特征算法滿足該性質(zhì)，但是TAR和PTS算法并不滿足該條屬性。

屬性5 順序結(jié)構(gòu)漂移不變性。如圖16給定了一個業(yè)務(wù)流程模型，無論在哪里插入新的變遷，新模型和舊模型的相似性都不會改變，即sim（N1，N2）=sim（N1，N3）=sim（N1，N4）。

假如N1中的變遷數(shù)為10個，然后在包括開始和結(jié)束這兩個變遷的11個間隔中添加一個新的變遷，可以得到11個新的業(yè)務(wù)流程模型N2-N12。

相似度結(jié)果如圖17所示，隨著新添加的轉(zhuǎn)換的位置變化，相似性不會改變，因此證明了PSSA滿足屬性5。此外，行為特征算法和PTS也滿足該性質(zhì)，但是算法計算的相似度值的精度并沒有PSSA高，唯一不滿足屬性的是TAR算法。

綜上所述，可以得出算法滿足表2所示的結(jié)論。

4.3 實驗小結(jié)

路徑序列算法實現(xiàn)了對Petri網(wǎng)展開樹路徑序列的獲取，實驗中以節(jié)點和邊的總數(shù)表示模型的復(fù)雜程度，在模型復(fù)雜度變高的情況下，路徑序列算法在實現(xiàn)基本功能的同時，其性能明顯優(yōu)于一般的廣度優(yōu)先算法。在時間上面顯著優(yōu)于人工統(tǒng)計路徑序列。

算法PSSA和主流的基于行為的模型相似性算法相比，在滿足五個性質(zhì)方面具有優(yōu)勢，只有PSSA能夠滿足全部五個性質(zhì)；而在相似度計算精度方面，算法PSSA計算的相似度值要優(yōu)于其他三種算法。

5 案例分析

以某航天發(fā)動機(jī)A、B兩個信號處理業(yè)務(wù)流程為例具體說明Petri網(wǎng)模型，根據(jù)涉及的狀態(tài)和產(chǎn)生的變化，將其相應(yīng)地轉(zhuǎn)換為庫所和變遷；將這些庫所和變遷按照Petri網(wǎng)的定義用有向弧進(jìn)行連接，將起始點和第一個庫所結(jié)合為帶有起始條件令牌庫所，可以形成一個與業(yè)務(wù)流程圖對應(yīng)的一個P/T_模型，如圖18所示的是A信號處理業(yè)務(wù)流程Petri網(wǎng)。

利用Petri網(wǎng)創(chuàng)建工具Tina繪制如圖18所示的圖形，并對模型進(jìn)行分析論證，如果模型正確，則可以將其導(dǎo)出為“.pnml”格式的文件，利用路徑獲取算法對“.pnml”文件進(jìn)行解析，完成路徑的提取，可以正確完整地獲得12條路徑序列，具體如表3所示。

B信號處理業(yè)務(wù)流程形成的P/T_模型，如圖19所示。

可以正確完整地獲得8條路徑序列，具體如表4所示。

上文可知路徑序列是業(yè)務(wù)流程模型通過一定形式轉(zhuǎn)換得到的，利用本文的相似度計算方法可以確定兩個模型的相似度，因此，可以等價地認(rèn)為路徑序列相似度值0.63即為信號業(yè)務(wù)流程模型A和B的相似度值。

6 結(jié)束語

本文提出了一種基于模型結(jié)構(gòu)和執(zhí)行語義的過程模型相似性度量算法。該算法建立在Petri網(wǎng)展開樹的路徑序列基礎(chǔ)之上，利用展開樹表示模型結(jié)構(gòu)，其路徑序列來表示過程模型的行為，可應(yīng)用于包含循環(huán)結(jié)構(gòu)的模型，并能夠有效處理Petri網(wǎng)中的各類結(jié)構(gòu)。本文通過實驗衡量模型相似性算法是否滿足五種相似性屬性，通過實驗可知該算法較其他基于行為的相似性算法計算結(jié)果更加合理且高效。最后將該模型相似性算法實際應(yīng)用到具體項目中，結(jié)合相似度計算值，可以精確化確定模型的相似之處。本文方法還存在一些有待深入研究的問題：當(dāng)業(yè)務(wù)流程模型十分巨大時，獲取的路徑序列耗時欠缺考慮，如何降低時間消耗是下一步需要考慮的問題。并且在下一步研究過程中，考慮將獲取的路徑序列轉(zhuǎn)換為實際運(yùn)用的測試用例或者作為某些問題的相似性參考，將有助于實施測試數(shù)據(jù)復(fù)用或者數(shù)據(jù)遷移等工作，

參考文獻(xiàn)：

［1］Leemans S，McGree J，Polyvyanyy A，et al.Statistical tests and association measures for business processes［J］.IEEE Trans on Know-ledge and Data Engineering，2023，35（7）：7497-7511.

［2］Surkova E，Mazhaiskii Y.Management of business processes［J］.Russian Engineering Research，2022，42（3）：292-294.

［3］Paolo B，Andrea D，Tommaso P.A model based framework for IoT-aware business process management.［J］.Future Internet，2023，15（2）：50-78.

［4］Bubenik P，Capek J，Rakyta M，et al.Impact of strategy change on business process management［J］.Sustainability，2022，14（17）：11112-11135.

［5］Lopez L，Guerrero S，Sierra E.Epistemic analysis of BPM business process management.［J］.Webology，2022，19（6）：321-329.

［6］Schoknecht A，Thaler T，F(xiàn)ettke P，et al.Similarity of business process models-a state-of-the-art analysis［J］.ACM Computing Surveys，2017，50（4）：1-33.

［7］徐穎蕾.無沖突Petri網(wǎng)系統(tǒng)活標(biāo)識判定的結(jié)構(gòu)化方法［J］.計算機(jī)應(yīng)用研究，2023，40（5）：1447-1451，1458.（Xu Yinglei.A structured method for determining liveness of conflict-free Petri net systems［J］.Application Research of Computers，2023，40（5）：1447-1451，1458.）

［8］Corradini F，Muzi C，Re B，et al.BPMN 2.0 OR-join semantics：glo-bal and local characterisation［J］.Information systems，2022，105（5）：101934-101957.

［9］Carnevali L，German R，Santoni F，et al.Compositional analysis of hierarchical UML statecharts［J］.IEEE Trans on Software Engi-neering，2022，48（12）：4762-4788.

［10］Van B，Dijkman R，Mendling J.Measuring similarity between business process models［J］.Seminal Contributions to Information Systems Engineering，2013，5074：405-420.

［11］汪抒浩，聞立杰，魏代森，等.基于任務(wù)最短跟隨距離矩陣的流程模型行為相似性算法［J］.計算機(jī)集成制造系統(tǒng)，2013，19（8）：1822-1831.（Wang Shuhao，Wen Lijie，Wei Daisen，et al.Behavior similarity algorithm of process models based on task minimum following distance matrix［J］.Computer Integrated Manufacturing Systems，2013，19（8）：1822-1831.）

［12］Rivas D F，Corchuelo D S，F(xiàn)igueroa C，et al.Business process model retrieval based on graph indexing method［C］//Proc of International Conference on Business Process Management.2010：238-250.

［13］Saranya K G，Sadasivam G S.Modified heuristic similarity measure for personalization using collaborative filtering technique［J］.Applied Mathematics & Information Sciences，2017，11（1）：307-315.

［14］Zha Haiping，Wang Jianmin，Wen Lijie，et al.A workflow net similarity measure based on transition adjacency relations［J］.Computers in Industry，2010，61（5）：463-471.

［15］Wang Jianmin，He Tengfei，Wen Lijie，et al.A behavioral similarity measure between labeled Petri nets based on principal transition sequences（short paper）［C］//Proc of OTM Confederated International Conferences on the Move to Meaningful Internet Systems.2010：394-401.

［16］Kunze M，Weidlich M，Weske M.Behavioral similarity-a proper metric［C］//Proc of Business Process Management International Confe-rence.Berlin：Springer，2011：166-181.

［17］Esparza J，Rmer S，Vogler W.An improvement of McMillans unfolding algorithm［R］.［S.l.］：Technische Universitat Munchen，1996：285-310.

［18］Cui Huanqing.Tree Petri nets：properties and applications in logical problems［C］//Proc of the 2nd WRI Global Congress on Intelligent Systems.Piscataway，NJ：IEEE Press，2011.

［19］Wang Shuhao，Yin Ming，Wang Zixuan，et al.TAR+：a new process model similarity algorithm based on the importance of TARs［J］.Asia Pacific Business Process Management，2015，219：98-112.

［20］Winskel G.Event structures［M］.Berlin：Springer，1987.