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

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

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

關鍵詞：Petri網；相似性度量；展開樹；路徑序列

中圖分類號：TP391?? 文獻標志碼：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 引言

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

業務流程模型，一般簡稱流程模型，是BPM的基礎，采用大量的符號來建模操作業務流程以達到處理流程實例［6］的目的，成熟的符號工具有Petri網［7］、BPMN［8］、UML［9］和EPC［10］，使用這些工具可以將業務流程的過程節點和執行方式抽象成具體的符號，可以有序構造成工作流程模型，并且還可以利用仿真軟件進行模型仿真。

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

然而，現有的相似性算法存在諸多問題，主要包括共同相似性性質不足、耗時成本高、存在非自由選擇等特定結構不可用等。

文獻［11］中提出相似性算法至少應該滿足五個屬性，分別是互斥結構漂移不變性、跨度負相關性、無關遞減性、循環序列長度負相關性和順序結構漂移不變性。現有的算法，如TAR［14］、PTS［15］、行為特征［16］，不能滿足所有屬性。

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

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

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

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

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

1 相關知識

本章對本文使用的一些基本概念進行介紹，主要是表達業務流程模型的Petri網。

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

下面給出Petri網的正式定義：

定義1 Petri網。Petri網是一個五元組，N=（P，T，F，W，M0），其中：P={p1，p2，…，pm}是一組有限的庫所集，T={t1，t2，…，tn}是一個有限的變遷集，F（P×T）∪（T×P）→{0，1}是一組有向弧，W：F→{0，1，2，3，…}是權重函數，M0：P→{0，1，2，3，…}是初始標記，P∩T=，P∪T=。

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

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

如果沒有任何特定初始標記的Petri網結構Nw=（P，T，F，W）記為Nw，所以具有給定初始標記的Petri網可以用（N，M0）表示。通常庫所和變遷可以稱為節點，而F則是節點之間的有向弧，因此，Petri網可以被認為是一個有向圖，而圖中的路徑通常是一個非空的節點序列，沒有重復，從每個節點到下一個節點都有一條弧（不考慮首尾節點）［17］。

2 Petri網展開樹

2.1 Petri網展開樹的定義

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

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

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

2.2 展開樹的路徑序列

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

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

性質1 結構差異大的兩個業務流程模型，對應展開樹的路徑序列差異也越大。

性質2 采用展開樹路徑序列能夠處理業務流程模型Petri網中包含的不可見任務、非自由選擇結構、循環結構及各種基本控制流結構。

2.3 Petri網展開樹的性質

性質3 Petri網展開樹Nt=（P，T，F），對于根庫所Proot，·Proot=和p∈P{Proot}，|·p|=1。如果P是葉庫所，p·=，否則|p·|≥1。對于t∈T，|t·|≥1和|·t|=1。對于兩個標記M0、M1，M1可從N中的M0到達當且僅當M0可從N中的M1到達N-1。

性質4 展開樹是Petri網業務流程模型結構的一種表示方法，與模型節點存在一對一關系。

3 Petri網展開樹的路徑序列相似度算法

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

3.1 展開樹的路徑序列算法

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

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

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

輸入：Petri網G。

輸出：Petri網展開樹的路徑序列。

a）在原網G上構造一個開始變遷Ts和一個結束變遷Te，并獲取其位置；

b）從開始變遷Ts到結束變遷Te進行Petri網G的順向節點廣度優先搜索，得到順向最短路徑S；

c）從結束變遷Te到開始變遷Ts進行Petri網G的逆向節點廣度優先搜索，得到逆向最短路徑S′；

d）將最短路徑S和S′進行綜合，得到一個復合主干路徑S主，從Petri網G中去除復合主干路徑S主，得到一個殘差網絡G′，如果殘差網絡G′沒有其他結構，則結束算法，否則繼續下面步驟；

e）如果殘差網絡G′中仍然存在其他復雜網絡結構，則重復進行步驟a）～d），直到得到最簡單的順序結構殘差網絡G′；

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

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

h）重復循環步驟a）～g），直至找到所有路徑。

然而對于存在環狀結構的Petri網，如圖4（a）所示，雖然其展開過程可以在帶環處無限循環，但是在本文中，所有帶環的Petri網只考慮在環狀結構處循環一次，如圖4（b）所示，根據展開樹的路徑序列算法可以得到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 展開樹的路徑序列的算法理論證明

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

1）Petri網特點

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

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

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

2）廣度優先搜索

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

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

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

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

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

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

性質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）無環子圖

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

4）動態規劃算法

求得G′中Ts到業務流程節點v的所有路徑π′（v）和節點v到Te的所有路徑π′i（v），因此π′（Ts）=π′（Te）。每一次Ts到業務流程節點v的路徑以及業務流程節點v到Te的路徑會暫時存儲起來，當具有重復路徑時直接進行調用，大大降低了算法的時間消耗。

5）路徑組合獲取

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

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

6）路徑遍歷迭代

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

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

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

算法2 業務流程模型相似度計算

輸入：Petri網展開樹的路徑序列。

輸出：業務流程相似度值。

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

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

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

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

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

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

4 實驗設計與分析

4.1 實驗環境

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

4.2 實驗設計

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

利用Petri網構建30個業務流程模型，采用人工統計、普通廣度優先搜索算法和展開樹路徑序列算法對業務流程模型的路徑序列進行數量統計。利用節點和邊的總數來表示業務流程模型的大小，一般而言，模型越大復雜程度越大，但是對于一些節點和邊數量較多的順序結構模型并不能反映結構的復雜度，因此需要考慮帶環狀結構的業務流程模型。在一些較小的業務流程模型中，帶環狀結構的模型利用展開樹路徑序列算法可以正確識別；在一些較大的業務流程模型中，展開樹路徑序列算法的平均識別準確率也達到了72.6%。

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

4.2.2 五種屬性的對比實驗

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

屬性1 互斥結構漂移不變性。如圖8所示，給定導出的互斥結構的業務流程模型，無論在何處添加新的轉換，新模型和舊模型的相似性都不會改變，即sim（N1，N2）=sim（N1，N3）=sim（N1，N4）。

如圖8所示，假如N1中的變遷數為10個，然后在每個變遷處添加新的變遷分支，構成一種互斥結構模型，可以得到10個新的業務流程模型N2～N11。

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

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

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

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

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

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

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

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

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

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

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

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

4.3 實驗小結

路徑序列算法實現了對Petri網展開樹路徑序列的獲取，實驗中以節點和邊的總數表示模型的復雜程度，在模型復雜度變高的情況下，路徑序列算法在實現基本功能的同時，其性能明顯優于一般的廣度優先算法。在時間上面顯著優于人工統計路徑序列。

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

5 案例分析

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

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

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

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

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

6 結束語

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

參考文獻：

［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，Fettke 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網系統活標識判定的結構化方法［J］.計算機應用研究，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］汪抒浩，聞立杰，魏代森，等.基于任務最短跟隨距離矩陣的流程模型行為相似性算法［J］.計算機集成制造系統，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，Figueroa 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.