电子学报 ›› 2018, Vol. 46 ›› Issue (4): 862-870.DOI: 10.3969/j.issn.0372-2112.2018.04.014

• 学术论文 • 上一篇    下一篇

基于过程结构树的流程间差别检测算法

曹斌, 安卫士, 王佳星, 范菁   

  1. 浙江工业大学计算机科学与技术学院, 浙江杭州 310023
  • 收稿日期:2016-10-16 修回日期:2017-04-27 出版日期:2018-04-25
    • 作者简介:
    • 曹斌 男.1985年5月出生,山西孟县人,博士、讲师、CCF会员,主要研究领域为业务流程管理、大数据.E-mail:bincao@zjut.edu.cn;安卫士 男.1990年4月出生,河南郸城县人,硕士生、CCF学生会员,主要研究领域为业务流程管理;王佳星 女,1990年11月出生,浙江海宁人,博士生、CCF学生会员,主要研究领域为工作流
    • 基金资助:
    • 国家自然科学基金 (No.61602411,No.61572437); 国家重点研发计划 (No.2016YFB1001403); 浙江省重大科技专项重点工业项目 (No.2015C01029); 杭州市重大科技创新项目 (No.20152011A03)

A Difference Detection Algorithm for Process Models Based on Process Structure Tree

CAO Bin, AN Wei-shi, WANG Jia-xing, FAN Jing   

  1. Department of Computer Science and Technology, Zhejiang University of Technology, Hangzhou, Zhejiang 310023, China
  • Received:2016-10-16 Revised:2017-04-27 Online:2018-04-25 Published:2018-04-25
    • Supported by:
    • National Natural Science Foundation of China (No.61602411, No.61572437); National Key Research and Development Program of China (No.2016YFB1001403); Key Science and Technology Project of Zhejiang Province  (Key Industry Program) (No.2015C01029); Major Technological Innovation Project of Hangzhou (No.20152011A03)

摘要: 流程模型差别检测是业务流程管理的关键技术之一.针对流程模型大多是由图结构建模,而流程图模型中有多种类型节点,因此经典的图编辑距离方法无法直接应用于流程差别检测的问题,提出了基于过程结构树的流程间差别检测算法.算法首先将流程模型转化为基于任务节点的过程结构树;然后采用分治思想快速获得流程间的最佳对等节点映射集合;最后基于节点映射集合生成一个近似最小代价编辑操作序列来表示两个流程的差别.实验结果表明,本文算法在准确率和效率两方面都能满足实际的应用需求.

关键词: 业务流程管理, 流程差别检测, 过程结构树, 编辑操作序列

Abstract:

Detecting difference between process models is one of the key technologies in business process management. The classical graph edit distance cannot directly be used to detect the difference between process models because there are many kinds of nodes in a process model. To solve this problem, we present an algorithm for detecting difference between process models based on process structure tree. Firstly, the process models are converted to their corresponding task based process structure trees (TPSTs). Then the divide and conquer strategy is used to obtain the optimal mapped node set between two TPSTs. Finally, an edit script with approximate minimum cost is generated based on the mapped nodes, which is considered as the difference between two process models. The experimental results show that this algorithm can meet the real requirements in terms of precision and efficiency.

Key words: business process management, process difference detection, process structure tree, edit script

中图分类号: