基于Petri网工作流模型展开树的路径序列相似性算法  

Similarity algorithm of path sequence based onPetri net workflow model unfolding tree

作　　者：许山山 史涯晴 简开宇 魏居尚 张文焘 Xu Shanshan;Shi Yaqing;Jian Kaiyu;Wei Jushang;Zhang Wentao(College of Command&Control Engineering,Army Engineering University of PLA,Nanjing 210007,China;Dept.of Unit 96512,Xining Qinghai 810001,China;College of Software,Liaoning Technical University,Fuxin Liaoning 123032,China)

机构地区：[1]陆军工程大学指挥控制工程学院,南京210007 [2]96512部队,青海西宁810001 [3]辽宁工程技术大学软件学院,辽宁阜新123032

出　　处：《计算机应用研究》2024年第1期170-176,共7页Application Research of Computers

摘　　要：在实际的数据迁移项目中,为了解决数据映射的问题,需要确定两个工作流模型之间的相似度。从工作流模型的相似性方面进行分析阐述,提出了基于Petri网的工作流模型展开树的路径序列相似性算法。首先采用深度优先搜索算法和动态规划算法对模型进行搜索;其次通过提出的算法获取展开树的所有路径序列;最后利用编辑距离算法计算两个模型序列之间的两两相似度,进而完成模型相似性计算;相较于其他的主流相似度算法,主要优点在于可以精确计算得到模型部分结构和行为相似度,可以更好地确定流程间映射,从而找到数据映射的解决方法。实验结果表明,该方法较主流的基于模型结构和行为相似性的算法,计算合理性和准确性有很大提升。In the actual data migration project,in order to solve the problem of data mapping,it is necessary to determine the similarity between the two workflow models.This paper analyzed and expounded the similarity of workflow model,and proposed a path sequence similarity algorithm for the unfolding tree of workflow model based on Petri net.Firstly,it used the deep-first search algorithm and dynamic programming algorithm to search the model,and then obtained all path sequences of the unfolding tree by the proposed algorithm.Finally,it used the edit distance algorithm to calculate the pairwise similarity between the two model sequences,and then completed the model similarity calculation.Compared with other mainstream similarity algorithms,the main advantage is that the partial structure and behavior similarity of the model could be accurately calculated,which could better determine the mapping between processes,so as to find a solution to data mapping.The experimental results show that the proposed method is more reasonable and accurate than the mainstream algorithms based on model structure and behavior similarity.

关 键 词：PETRI网 相似性度量 展开树 路径序列 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]