ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (4): 832-843.doi: 10.7544/issn1000-1239.2017.20151176

• 软件技术 • 上一篇    下一篇



  1. (清华大学软件学院 北京 100084) (
  • 出版日期: 2017-04-01
  • 基金资助: 

A Similarity Measure for Process Models Based on Task Occurrence Relations

Song Jinfeng, Wen Lijie, Wang Jianmin   

  1. (School of Software, Tsinghua University, Beijing 100084)
  • Online: 2017-04-01

摘要: 针对流程模型行为相似性度量难题,提出了一种基于任务发生关系的流程模型相似性度量TOR.基于Petri网的完全前缀展开理论,提出了节点编号算法以及最近公共前驱计算方法,在此基础上定义了任务间3种基本的发生关系:因果、并行和互斥,并给出这些关系的高效计算方法和模型相似度计算公式.TOR能有效处理不可见任务和非自由选择结构,基于来自企业实际模型的实验证明了TOR具备较好的效果和性能,与已有算法相比,TOR能较好地满足行为相似性算法应具备的性质.

关键词: 相似性度量, 任务发生关系, 流程模型, 完全前缀展开, Petri网

Abstract: Similarity measures between process models are increasingly important for management, reuse, and analysis of process models in modern enterprises. So far, several approaches have been proposed and behavioral profile (BP) is a good concept to judge the behavioral consistency of process models, which describes the observable relations between tasks. However, all those approaches have their own advantages and disadvantages. Towards the hard problem of behavioral similarity measure between process models, especially to improve the effectiveness of BP, a new method for measuring the behavioral similarity between process models named TOR based on the occurrence relation among tasks is proposed. Based on complete prefix unfolding (CPU) technique of Petri nets, we propose the algorithms for numbering the nodes in a CPU and computing the least common precursors for each pair of nodes. Then we define the three basic occurrence relations between tasks: causal relation, concurrent relation and conflict relation. The algorithm for efficiently computing the relations and the formalism for computing the similarity are also given. TOR can handle both invisible tasks and non-free choice constructs. The experimental results show the effectiveness and efficiency of TOR. Compared with the existing mainstream behavioral similarity algorithms for process models, TOR can satisfy all the five properties that a good similarity algorithm should have.

Key words: similarity measure, occurrence relations of tasks, process model, complete prefix unfolding (CPU), Petri nets