积分商城

最新搜索： 电视机电源 光通信 QT 串口 开关电源 焊台 探地雷达
您现在的位置是：首页 > 技术资料 > 基于过程结构树的流程间差别检测算法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

更新时间：2019-12-25 06:56:44 大小：2M 上传用户：守着阳光1985查看TA发布的资源 标签：过程结构树 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

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


部分文件列表

文件名 大小
基于过程结构树的流程间差别检测算法.pdf 2M

部分页面预览

（完整内容请下载后查看）
4
Vol． 46 No． 4  
Apr． 2018  
第
期
电
子
学
报
2018  
4
ACTA ELECTRONICA SINICA  
年
月
基于过程结构树的流程间差别检测算法  
， ， ，  
曹 斌 安卫士 王佳星 范 菁  
(
，
浙江工业大学计算机科学与技术学院 浙江杭州  
310023)  
:
． ，  
流程模型差别检测是业务流程管理的关键技术之一 针对流程模型大多是由图结构建模 而流程图模  
摘
要
， ，  
型中有多种类型节点 因此经典的图编辑距离方法无法直接应用于流程差别检测的问题 提出了基于过程结构树的流  
． ;  
程间差别检测算法 算法首先将流程模型转化为基于任务节点的过程结构树 然后采用分治思想快速获得流程间的最  
; ．  
佳对等节点映射集合 最后基于节点映射集合生成一个近似最小代价编辑操作序列来表示两个流程的差别 实验结果  
，
表明 本文算法在准确率和效率两方面都能满足实际的应用需求  
．
:
;
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
业务流程管理 流程差别检测 过程结构树 编辑操作序列  
TP311 0372-2112 ( 2018) 04-0862-09  
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 04． 014  
:
:
A
:
文章编号  
文献标识码  
电子学报  
A Difference Detection Algorithm for Process  
Models Based on Process Structure Tree  
CAO Bin，AN Wei-shi，WANG Jia-xing，FAN Jing  
( Department of Computer Science and Technology，Zhejiang University of Technology，Hangzhou，Zhejiang 310023，China)  
Abstract: Detecting difference between process models is one of the key technologies in business process manage-  
ment． 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 consid-  
ered as the difference between two process models． The experimental results show that this algorithm can meet the real re-  
quirements in terms of precision and efficiency．  
Key words: business process management; process difference detection; process structure tree; edit script  
．
差别是流程合并的第一步  
1
引言  
， 1 ( a) 、( b)  
例如 图 中  
A B  
分别对应公司 和公司 的  
流程模型差别检测主要研究如何自动化的找出给  
， ．  
请假流程 两者的差别如虚线框中所示 由两个请假流  
．
定的两个流程模型间的不同 在业务流程管理  
( Business  
， B ．  
程可以看出 公司 的请假流程更加简洁高效 快速找  
Process Management，BPM)  
，
过程中 很多应用场景都要  
，
出企业业务流程与其他公司相似业务流程的差别 便  
．
对两个业务流程进行差别检测 如  
: ( 1)  
企业的业务流  
，
于业务流程人员对企业的业务流程进行优化 以此来  
，
程会随着市场以及政府政策的变化而进行多次重建  
．
增强企业的市场竞争力  
业务流程模型间的差别可以表示为一个编辑操作  
［1］  
．
因此一个流程会出现多个版本 在流程版本管理  
，
中
，
管理人员要对同一个流程的不同版本进行比较 确定  
，
序列 即将一个流程模型变为另一个流程模型所需的  
; ( 2)  
，
在企业合并时 重叠  
， 、 ． 1  
编辑操作 如删除节点 插入节点等 例如图 中的流程  
流程在哪些环节发生了变化  
［2］  
，
( a) ( b) ， :  
和流程 两者间的差别如虚线框中所示 流程  
业务的流程模型要进行合并  
找出两个流程模型的  
: 2016-10-16;  
: 2017-04-27;  
:
收稿日期  
修回日期  
责任编辑 李勇锋  
国家重点研发计划  
( No． 20152011A03)  
:
基金项目 国家自然科学基金  
( No． 61602411，No． 61572437) ;  
( No． 2016YFB1001403) ;  
浙江省重大科技专项重点工业项目  
( No． 2015C01029) ;  
杭州市重大科技创新项目  
863  
4
:
斌 基于过程结构树的流程间差别检测算法  
第
期
曹
( a)  
( b)  
． ( a)  
多了一个步骤 将流程 中虚线框中  
比流程  
( b) ，  
同样在流程  
( b)  
任务节点删除即转变为流程  
中的  
( a) ．  
，
相应位置插入该节点 则可将流程  
( b)  
转化为流程  
1 ， ，  
由图 可以看出 流程图模型中包含多种类型节点 如  
Petri  
， (  
网建模流程为例 流程模型中包含库所 以圆圈  
以
) ( ) ，  
表示 和变迁 以矩形表示 两种节点 因此经典的图编  
．
辑距离方法无法直接应用于流程差别检测问题上  
，
织成树型结构就构成了流程模型的过程结构树 如图  
4
．
所示  
， ［3］  
为解决上述问题 本文在文献 的过程结构树  
( Program Structure Tree，PST)  
，
的结构基础上 提出了基  
4 ，  
由图 可知 过程结构树中的叶子节点对应流程模  
( Task based Process Structure  
于任务节点的过程结构树  
Tree，TPST) ．  
，
型中的一条边 非叶子节点对应包含大于两条边的流  
TPST  
随后通过计算两棵  
之间的差别来表  
． ，  
程模型片段 过程结构树是无序树 因此无法体现流程  
． TPST  
，
是一棵半有序树 即  
示两个对应流程模型的差别  
，
部分节点的子节点是有顺序的 表示流程中的有序结  
．
模型中任务执行的先后关系 本文在过程结构树基础  
TPST．  
上提出了基于任务节点的过程结构树  
( 、 ) ，  
构 如顺序结构 循环结构 部分节点的子节点是无序  
， ( 、  
的 表示流程模型中的无序结构 如选择结构 并行结  
) ． PST ，TPST  
与无序树 相比  
构
可以表示流程模型中包  
．
含的各种控制流结构  
ZHANG  
等人已经证明生成一个最小代价编辑操作  
NP-Complete  
序列作 为 两 个 树 之 间 的 差 别 是 一 个  
问
［6］  
．
题
本文提出把近似最优的编辑操作序列作为两个  
，
流程模型间的差别 近似最优编辑操作序列即近似最  
． ，  
小代价编辑操作序列 算法共分为两大步骤 第一步主  
基于任务节点的过程结构树与过程结构树的差别  
，TPST  
TPST  
;
中对等节点的映射 第二步是基于上  
要进行两棵  
，
在于  
关节点 并且  
TPST  
的叶子节点都是任务节点 非叶子节点为网  
一步得到的对等节点映射集合和分片映射集合生成一  
，
TPST  
．
是 半有序树结 构 下面 举例 说明  
，
个近似最优的编辑操作序列 该编辑操作序列为两个  
，
5
:
的特点 如图 所示  
．
流程模型的差别  
2
流程差别检测的相关概念  
2. 1  
基于任务节点过程结构树  
基于任务节点的过程结构树可由过程结构树转化  
， ．  
得到 首先介绍过程结构树的概念 过程结构树是将流  
［4］  
( SESE)  
，
程模型划分成一系列单入口单出口的模块  
( 1)  
，
叶子节点是任务节点 其子节点为空  
;
．
并按照嵌套关系组织成的树型结构  
( 2)  
，
非叶子节点是非任务节点 并有以下四种类  
2 ，  
以图 中两个流程模型为例 首先将用  
Petri  
网建  
: XOR、AND、LOOP、Sequence，  
这四种类型节点分别对  
型
模的流程模型中的库所和变迁按照执行依赖关系转化  
Petri  
、 、 、  
网中的选择结构 并行结构 循环结构 顺序结  
应
， 3 ．  
为对应的网关节点 如图 所示 随后将其划分成一系  
，
构 其中  
XOR、AND ; LOOP、Sequence  
的子节点是无序的  
，
列流程模型片段 将流程模型的片段按照嵌套关系组  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号