并发感知的业务过程事件序列编辑距离∗

常 震 戴汪洋 宋 巍 李晅松

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

业务过程管理旨在加快制定，分析和改进业务过程的速度，而围绕着过程所建立的组织，具有更高的敏捷性、效率和效益。为了支持管理决策，业务过程日志记录了过程实例的执行，通过分析业务过程日志数据可以了解业务过程的执行，实现业务过程的管理、改进与再造［1～3］。在日志噪音修复、过程挖掘中的合规性检验方面，不可避免地要对日志中的事件序列进行差异性度量，如验证事件序列的修复情况等［4～6］。

在计算机科学中，字符串编辑距离是重要而基本的概念，它在拼写检查与自动修复等方面有着广泛的应用［7～8］。虽然可以使用字符串编辑距离来定义业务过程日志中事件序列间的编辑距离，但该方法在应用于含并发的业务过程时并不理想。例如在日志修复时，一个含有噪音的事件序列可能存在多个不同的正确修复方案［4～6］，不同修复方案的差异往往仅体现在存在并发关系的事件的先后顺序上。如果利用字符串编辑距离作为评判依据，这些正确的修复有很多不被认为是最优修复。

考虑到现有方法的不足，本文针对业务过程的并发性以及事件序列可能产生的噪音类型，给出了业务过程事件序列编辑距离的全新定义，提出了相应的求解算法，并将该算法实现为一个图形化的桌面工具“BPETED”（Business Process Event-trace Ed⁃it Distance）。该工具可以解析XES格式的事件日志文件，并计算指定的事件序列间编辑距离，同时给出时间消耗。本文通过IBM公司一个真实的业务过程日志对算法进行分析，验证算法的有效性和高效率。

2 背景知识

2.1 业务过程

Petri网［9］是一种简洁通用的表示业务过程的建模语言，并且拥有一套完善的数学理论进行过程分析。因此，其他如BPEL、BPMN、EPC等工业建模语言也经常被转化为Petri网进行高级的分析与应用［10～11］。本文延用惯例，也使用 Petri网来表示业务过程。

定义1（Petri网）Petri网是一个满足如下条件的三元组PN=(P，T，F)：

·P是库所的有限集合；

·T是变迁的有限集合，并且满足P∩T=Φ；

·F⊆(P×T)∪(T×P)是被称为流关系的有向弧的有限集。

Petri网所表示的业务过程中的起始库所和终止库所只有一个，并且它是可以执行的。业务过程每执行一次便产生一条过程实例，该过程实例可以用一条事件序列σ={t1，t2，t3，...，tn} 来表示，其中t1，...，tn代表事件，这n个事件按照发生的先后顺序进行排列。将这些过程实例记录下来便形成了事件日志。

定义2（事件序列与事件日志）给定一个业务过程W=(P，T，F)，其初始状态为M0，事件序列σ∈T*是从状态M0转化为状态M的一条活动序列，其中M为W的任意一个可达的状态。事件日志为事件序列的集合，即L={σ|σ∈T*}。

图1展示了一个含并发的业务过程Petri网模型。

图1 含并发的Petri网

2.2 字符串编辑距离

关于编辑距离问题的研究可以追溯到字符串间编辑距离，这个概念最早由俄国科学家Levensh⁃tein于1965年提出，因此，编辑距离也被称为“Lev⁃enshtein distance”（以下简称 L 氏距离）［15～16］。编辑距离是一种通过计算将一个字符串转换为另一个字符串所需的最小操作次数来量化两个字符串间相似性的方式［7～8］。它在自然语言处理、生物信息科学以及计算机科学等方面有着广泛的应用。

字符串间编辑距离计算利用动态规划的算法思想，将两个字符串间的编辑距离转换为子序列间的编辑距离，用一个维度大小分别为源字符串长度和目标字符串长度的矩阵来保存计算过程中求得的子序列编辑距离［12～14］。一般来说，两个字符串的编辑距离越短，则表示它们越相似，如果两个字符串相同，则它们的编辑距离为零。

到目前为止，对编辑距离的定义有很多扩展，不同的编辑距离定义了不同的字符串操作集合。其中，L氏距离的操作集合包括删除、插入、替换［15～16］。此外还存在最长公共子序列（LCS）距离，操作集合只包含删除、插入两类操作；海明距离（Hamming distance），只允许替换操作等多种扩展类型的编辑距离［7］。除此之外，有人还提出了一些其他的基本操作，如键入文字时常见的错误，交换相邻两个字符的顺序。由于以上各种编辑距离定义不能直接应用于含并发的业务过程事件序列，因此，在章节3.2中我们给出了业务过程事件序列编辑距离的全新定义。

3 编辑距离算法

3.1 事件间关系

由于字符串中的字符间的关系是相互独立的，因此在计算字符串编辑距离的过程中，不考虑字符间的相互关系。但对于事件序列来说，事件间存在一系列关系，这些关系可能会对事件序列编辑距离产生影响。

事件序列间的关系包括直接先于关系（符号表示为>）与并发关系（符号表示为||）等。直接先于关系与并发关系的定义同文献［17］中定义相同。

定义3（事件间关系）给定一个业务过程W=(P，T，F)的事件日志L，存在事件a，b，满足a，b∈T，a≠b，则a，b存在以下关系：

·a>b，对于任一事件序列σ={t1，t2，t3，…，tn}，当a=ti，b=t(i+1)，则a>b；

·a||b，当且仅当a>b，并且b>a时，a||b。

算法1旨在挖掘业务过程事件日志中事件间的并发关系集合。第1行对集合进行初始化；第2～4行挖掘事件间的直接先于关系集合；第5～8行根据之前获得的事件间直接先于关系集合，挖掘事件间的并发关系集合，其中第5～6行利用二重循环遍历事件日志中所有的事件对，第7～8行根据事件间直接先于关系判断事件间是否存在并发关系；第9行，返回事件间的并发关系集合。该算法的时间复杂度为Θ(N*l+|T|2)，其中N*l为挖掘直接先于关系集合的时间复杂度，|T|2为挖掘并发关系集合的时间复杂度，N表示事件日志中事件序列的数量，l表示事件日志中事件序列的平均长度， ||T表示事件日志中事件的数量。

3.2 编辑距离

字符串编辑距离算法的计算不需要考虑字符间的并发关系，但对于事件序列编辑距离来说，事件间的并发关系可能会对编辑距离产生影响。本节针对业务过程的并发性以及事件序列中可能产生的噪音类型，对业务过程事件序列编辑距离进行了全新定义。

现实世界中的事件日志中存在三类可能的噪音类型：缺失、冗余、乱序［4～6］，针对这三类噪音类型，我们分别定义了三类业务过程事件序列基本编辑操作：删除、插入、交换。

定义4（基本编辑操作）事件序列间的基本编辑操作包括删除、插入、交换：

·删除：删除事件序列中任意一个事件，如删除事件序列abc中的事件b后，事件序列变为ac；

·插入：在事件序列中任意位置插入一个已定义或未定义的事件，如对于事件序列ab，在事件b之后插入一个未定义的事件c，事件序列变为abc；

·交换：交换事件序列中任意两个相邻且非并发的事件，如对于事件序列abcd，事件b，c为非并发关系，交换事件b，c，事件序列变为acbd。

特别地，交换两个相邻且并发的事件对编辑距离不产生影响。

定义5（编辑距离）给定两个事件序列σ与δ，σ与δ间的编辑距离D(σ，δ)是将其中一条事件序列转化为另一条事件序列所需的最少基本编辑操作次数。

3.3 编辑距离计算

本节提出了编辑距离的求解算法，该算法的创新点在于能够消除事件间并发关系对事件序列编辑距离产生的影响，准确度量事件序列间的差异。

我们运用动态规划的思想，用矩阵Dm×n来存储计算过程中子序列间的编辑距离。假设待求的两条事件序列分别为 σ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的长度， ||σ2表示事件序列σ2的长度。矩阵值 D[|σ1|][|σ2|]即为事件序列 σ1与σ2间的编辑距离。

算法的求解过程为首先对矩阵D的第零行与第零列进行初始化，将第零行中的每个值赋值为对应的列号，将第零列中的每个值赋值为对应的行号；然后计算矩阵D中的其他值，计算过程需要考虑三类情况，其中情况1、2与字符串编辑距离中考虑的情况相同［7～8］，情况3考虑了并发事件对编辑距离的影响，为本文的创新点。这三类情况分别如下。

1）矩阵值D[i][j]等于与其邻接的上方与左方矩阵值中的最小值加1，用式（1）表示为

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

2）当指针i指向的事件序列σ1中的事件σ1[i]与指针 j指向的事件序列σ2中的事件σ2[j]相同时，矩阵值D[i][j]等于矩阵值D[i-1][j-1]，用式（2）表示为

首先，对于矩阵值D[l-1][k-1]，虽然我们不可以直接得出该值，但却可以通过矩阵值D[i-1][j-1]间接计算求得。在事件序列中将事件tl移至事件ti之前且相邻的位置后，事件序列={t1，t2，...，t(l-1)，tl} 与 σ2'2={t1，t2，t3，...，t(j-1)} 间 的编辑距离将发生改变，产生的影响可以用式（3）表示为

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

其次，将事件tl移至事件ti之前且相邻的过程中，当发生交换的事件与事件tl为非并发关系，且该事件在事件 序列={t1，t2，t3，...，t(j-1)} 中出现时，会使编辑距离加1，用符号lnum表示满足条件的事件的数量。类似的，用符号knum表示将事件tk移至事件tj之前且相邻的过程中满足类似条件的事件数量。

最后，还需要判断事件ti与tj间的关系，若为非并发关系，则编辑距离加1，否则编辑距离不变。用式（5）表示情况3下的矩阵值为

取上述三类情况中求得的式（1）、（2）、（5）中的最小值为矩阵值D[i][j]的最终值。

算法2设计用来计算含并发的业务过程事件序列编辑距离。第 1 行，创建一个矩阵 D(|σ1|+1)×(|σ2|+1)来存储算法计算过程中的中间值；第2～3行，使用二重循环对矩阵D中的值逐个进行求解；第4～5行，对第零行与第零列进行初始化；第6行，计算情况1下的矩阵值D[i][j]；第7～8行，计算情况2下的矩阵值D[i][j]；第9～20行考虑了情况3；第10行计算式（3）和式（4）；第11行对lnum，knum和s进行初始化；第12～14行对lnum进行计算，第15～17行对knum进行计算；第18～19行判断事件ti与tj之间的关系，若为并发关系，则将s置为0；第20行计算式（5）；第21行返回待求事件序列编辑距离。该算法的时间复杂度为 Θ(|σ1|×|σ2)，其中 ||σ1表示事件序列σ1的长度， ||σ2表示事件序列σ2的长度。

4 评估

4.1 工具实现

为了评估本文算法的有效性与高效率，同时方便相关领域内其他研究人员使用，我们在Eclipse集成环境中使用Java语言开发了原型工具“BPET⁃ED”，该工具运行在装有JDK1.8的机器上，其使用分为以下三个步骤：

1）日志解析：如图2所示，在“日志”显示面板下，点击“选择xes日志文件”按钮，选择好日志文件之后点击“解析日志文件”按钮，可在下方显示框内显示事件日志中每条事件序列的起始事件、终止事件、长度与数量等信息，并在“计算编辑距离”按钮下方显示挖掘事件间关系消耗的时间。点击“显示事件序列”按钮可以查看事件序列详情。

图2 原型工具

2）编辑距离计算：选中显示框中的事件序列，点击“作为源序列”按钮可以将该事件序列作为源序列，或者直接在编辑框内编辑；同样地，选择目标序列或直接编辑。点击“计算编辑距离”按钮，计算源序列和目标序列间的编辑距离，并在“计算编辑距离”按钮下方显示计算编辑距离消耗的时间。

3）结果展示：如图3所示，计算完编辑距离后，在“结果”显示面板下，点击“显示结果”按钮可以以表格形式查看矩阵的值，矩阵中最右下角的矩阵值即为待求的事件序列编辑距离。

图3 含循环业务过程的事件序列编辑距离计算结果

4.2 案例分析

图4为一个带循环且含并发的业务过程案例，该案例来源于IBM公司一个真实的业务过程。由于该业务过程较大，影响在本文中的呈现效果，因此我们对案例进行了一定程度的简化。

图4 带循环且含并发的Petri网

该业务过程存在两条并发支路并包含两个循环节点t40 与t31 。事件序列σ1={t57，t61，t72，t69，t67，t89，t40，t72，t67，t69，t89，t29} 与事件序列σ2={t57，t61，t72，t67，t69，t89，t29}为该业务过程产生的两条运行实例。以这两条事件序列为例，对编辑距离计算过程进行分析。

首先按照算法1挖掘出事件间的关系集合，其中事件间并发关系集合为||={t67||t69}；然后按照算法2，创建矩阵D12×7，其中l2为事件序列σ1的长度，7为事件序列σ2的长度。对矩阵进行初始化之后逐个求解矩阵中剩余的值。举例说明算法2的求解过程。

对于矩阵值D[1][1]，根据式（1）计算情况1的值 为D[1][1]=min(D[0][1]，D[1][0])+1=2 ；由 于σ1[1]=σ2[1]，满足情况 2的条件，按式（2）计算得D[1][1]=min(D[0][0]，D[1][1])=0 ；因为当前不存在位置相互交换事件，所以不需要考虑情况3，最终得D[1][1]=0。

对于矩阵值D[1][2]，根据式（1）计算得，D[1][2]=min(D[0][2]，D[1][1])+1=1，当前不满足其他情况的条件，得D[1][2]=1。

对于矩阵值D[5][5]，指针i，k指向事件e，指针j，l指向事件 c，l=4，i=5，k=4，j=5。计算式（1）得D[5][5]=min(D[4][5]，D[5][4])+1=2 ；不满足σ1[5]=σ2[5]，不考虑情况2；由于当前存在位置相互交换的事件，计算式（3）得 ∆(l)=D[l][j-1]-D[l-1][j-1]=1；计算式（4）得 ∆(k)=D[i-1][k]-D[i-1][k-1]=1；在事件序列σ1中，事件t69与t67之间无其他事件，得lnum=0；在事件序列σ2中，事件t67与t69之间没有其他事件，得knum=0；事件t67与t69为并发关系，不对编辑距离产生影响，计算式（5），得D[5][5]=D[i-1][j-1]-∆(l)-∆(k)+lnum+knum+{0，1}=0；取式（5）与式（1）的最小值0为D[5][5]的最终值。

对于矩阵值D[9][5]，指针i，k指向事件c，指针j，l指向事件 s，l=4，i=9，k=4，j=5。计算式（1），得D[9][5]=min(D[9][4]+1，D[8][5]+1)=4 ；由于不满足σ1[9]=σ2[5]，无需计算式（2）；计算式（3）得 ∆(l)=D[l][j-1]-D[l-1][j-1]=1；计算式（4）得 ∆(k)=D[i-1][k]-D[i-1][k-1]=-1；在事件序列σ1中，事件t69与t67之间存在事件t67，t89，t40，t72，其中事件t72与t69为非并发关系，且t72在事件序列={t57，t61，t72}中出现过，得lnum=1；在事件序列σ2中，事件t67与t69之间不存在事件，得knum=0；事件t67与t69为并发关系，对编辑距离不产生影响，计算式（5）得 D[9][5]=D[i-1][j-1]-∆(l)-∆(k)+lnum+knum+{0，1}=5；取式（1）与式（5）的最小值4为D[9][5]的最终值。

矩阵计算完成后可得图3，求得事件序列σ1与σ2间的编辑距离D[12][7]=5，该值恰好等于业务过程中循环部分的事件序列长度，表明计算结果正确。

我们将该实例运行在Inter（R）3.60GHz处理器，16GB内存的Windows8.1系统的台式机上。经过100次计算，统计得到平均事件关系挖掘时间为0.62ms，平均事件序列编辑距离计算时间为0.49ms，表现了算法具有很高的效率。

5 结语

本文针对业务过程的并发性以及事件日志中可能存在的三类噪音类型，定义了三类事件序列基本编辑操作，并给出了业务过程事件序列编辑距离的全新定义。基于该定义，在字符串编辑距离求解算法基础上，提出了一种计算含并发的业务过程事件序列编辑距离的算法。该算法能够有效处理含并发的业务过程，忽略由并发事件交换对编辑距离产生的影响。我们将该算法实现在“BPETED”工具中，并通过一个实际案例分析阐明了算法的有效性和高效率。