Page 175 - 《软件学报》2021年第5期

朱锐 等:基于完全有限前缀展开的行为等价过程树生成算法 1399

9(b)所示)进行检测,可以发现事件 T3 和 T2_1、T1 和 T0_1 满足可重构的迭代关系判断条件,这时可抽取出∝
(T0,T1)和∝(T2,T3).∝(T0,T1)和∝(T2,T3)并不冲突,将其重构后可得到图 9(c),将其展开可得到图 9(d)所示的展
开网,此时展开网(图 9(d)所示)上无法检测出新的关系,而图 9(c)所示的活动尚未全部重构为一个因此图 9 中的
案例 2 不能转化为过程树.
综合上述实验结果,基于完全有限前缀展开的等价过程树生成算法将过程模型进行展开,然后对模型进行
活动关系判断,对符合可重构关系的活动进行重构,更新过程模型,以此迭代,直到所有可重构的关系重构完毕,
该方法能将与过程树等价的过程模型转化为过程树.

(a) 实验模型 (b) 与(a)对应的展开网

(c) 模型(a)重构后的模型 (d) 与(c)对应的展开网

Fig.9 Cases of process models that cannot be transformed into process trees
图 9 不能转化为过程树的过程模型案例

4.3 性能分析
在验证本文算法性能之前,首先分析算法的时间复杂度.本文的行为等价过程树生成算法采用完全前缀展
开分析模型,然后抽取模型的行为,在获得优先级高的活动关系集合,从而重构过程模型,通过不断重复这些操
作最终获得行为等价过程树.本文算法的时间复杂度由算法 IR 的复杂度以及迭代次数(过程树深度)决定,其中
算法 IR 由完全前缀展开算法和计算活动关系两部分构成.首先考虑最坏情况下算法的复杂度,完全前缀展开算
ξ
法的复杂度最坏情况下为 O(|A|·R ),其中,|A|是模型中的活动数量,R 是展开网中非截断条件的数量,ξ是活动的
3
出度和入度中的最大数.计算活动关系的复杂度是稳定的为 O(|T| ),|T|是展开网中的事件数.因此本文算法复杂
ξ
3
度最坏为 O(h(|T| +|A|·R )),其中 h 为过程树的深度.但通常情况下完全前缀展开算法的复杂度为 O(R),此时完全
3
前缀展开算法的复杂度就远低于计算活动关系的复杂度 O(|T| ),所以本文算法的时间复杂度通常由迭代次数
3
和计算活动关系的复杂度决定,具体为 O(|T| ·h).相比同样可以处理 TEPM 结构的经典文献[27]达到指数级的时
n
间复杂度 O((|C|/n) )(|C|是模型中的条件数量,n 是活动的入度中的最大数),本文算法的时间复杂度在通常情况
下是非常低的.
对于 RD 组实验数据,经过验证可以全部正确的转化为行为等价过程树.现将统计抽取过程树花费的时间,
以及对应过程模型的活动数的统计图展示如图 10 所示.图 11 显示了 RD 组实验模型平均活动耗时统计,从该图
可以看出文本的算法将 BSPM 转化为过程树的效率稳定,平均到每个活动的耗时趋于 0.5ms.
根据本文中的算法已经开发了本实验的原型系统(http://47.110.142.51:8080/ProcessModel/Jump?type=
processModelling),原型系统中的过程树生成功能就是利用基于完全有限前缀展开的等价过程树生成算法来实
现的.