[發明專利]考慮并發的業務過程事件序列間編輯距離的求解方法

有效

• 申請號: 201810966487.7
• 申請日: 2018-08-23
• 公開（公告）號: CN109271606B
• 公開（公告）日: 2023-05-26
• 發明（設計）人: 宋巍;戴汪洋;常震;尚慶民;李晅松
• 申請（專利權）人: 南京理工大學
• 主分類號: G06F17/16
• 分類號: G06F17/16;G06F9/46
• 代理公司: 南京理工大學專利中心 32203
• 代理人: 陳鵬

1.一種考慮并發的業務過程事件序列間編輯距離的求解方法，其特征在于，具體步驟如下：

步驟1，解析XES描述的業務過程事件日志，獲得所有事件序列集合L；

步驟2，從所得到的事件序列集合L中挖掘出所有事件之間的并發關系集合；

步驟3，根據所有事件之間的并發關系集合，計算出待求的兩條事件序列間的編輯距離；具體為：

步驟3-1，根據兩條待求事件序列σ_A和σ_B，其中σ_A的長度表示為l_A，σ_B的長度表示為l_B，構建一個距離矩陣其中矩陣中的值D(m，n)表示σ_A的子序列σ_A＝{t₁，t₂，t₃，...，t_m}和σ_B的子序列σ_B＝{t₁，t₂，t₃，...，t_n}之間的編輯距離；

步驟3-2，初始化矩陣中的第一行與第一列為對應的行號和列號；

步驟3-3，依次計算矩陣中的值，用i表示當前所求矩陣值對應的行號，用j表示當前所求矩陣值對應的列號，l表示i所指向的序列σ_A中的事件σ_A(i)在事件序列σ_B中的離j最近的位置，k表示j所指向的序列σ_B中的事件σ_B(j)在事件序列σ_A中的離i最近的位置，即l和k為滿足{l，k|σ_A(k)＝σ_B(j)，σ_B(l)＝σ_A(i)，l∈[1，j]，k∈[1，i]}條件的最大的行列號；從D(1，1)開始，根據如下規則計算距離矩陣D中剩下的值：

(1)D₁(i，j)＝D(i-1，j)+1；

(2)D₂(i，j)＝D(i，j-1)+1；

(3)當A(i)與B(j)相同時，D₃(i，j)＝D(i-1，j-1)；

(4)當l與k存在時，

D₄(i，j)＝D(i-1，j-1)-Δ(k)-Δ(l)+Anum(k，i，j)+Bnum(l，j，i)+{0，1}；

Δ(k)＝D(k-1，j-1)-D(k，j-1)；

Δ(l)＝D(i-1，l-1)-D(i-1，l)；

(5)D(i，j)＝min{D₁(i，j)，D₂(i，j)，D₃(i，j)，D₄(i，j)}

其中Δ(k)＝D(k，j-1)-D(k-1，j-1)表示刪除事件σ_A(k)后σ_A{1...k}與σ_B{1...j-1}之間的編輯距離的變化，Δ(l)＝D(i-1，l)-D(i-1，l-1)表示刪除事件σ_B(l)后σ_A{1...i-1}與σ_B{1...l}之間的編輯距離的變化，D(i-1，j-1)-Δ(k)-Δ(l)表示刪除事件σ_A(k)和σ_B(l)后σ_A{1...i-1}與σ_B{1...j-1}之間的編輯距離，Anum(k，i，j)表示σ_A(k)與σ_A(i)之間的所有不與σ_A(k)并發且在序列σ_B{1...j}中包含的事件數量，Bnum(l，j，i)表示σ_B(l)與σ_B(j)之間的所有不與σ_B(l)并發且在序列σ_A{1...i}中包含的事件數量；

步驟3-4，取矩陣D(l_A+1，l_B+1)為事件序列σ_A與σ_B間的編輯距離。