基于变迁图编辑距离的流程相似性算法

Process similarity algorithm based on editing distance of transition graph

为了提高从企业模型库中查询检索模型的效率,提出一种基于变迁图编辑距离的流程相似性算法。首先,给出了变迁图的概念及其生成方法;其次,提出边的长度概念,且删除和插入边的代价由该边的长度决定,基于此定义出图编辑操作及其代价,并用节点匹配算法计算最小图编辑距离;然后,给出两个过程模型的相似性概念和计算方法;最后,通过实验验证了算法的正确性且满足七条相似性性质,并验证了变迁图编辑距离满足四条距离性质。

In order to improve the efficiency of querying and retrieving models from the enterprise model library,this paper proposed a process similarity algorithm based on the edit distance of transition graph.Firstly,it gave the concept of the transition graph and its generation method.Secondly,it proposed the concept of the length of the edge,and determined the cost of deleting and inserting the edge by the length of the edge.Based on this,it defined the graph editing operation and its cost,and used the node matching algorithm to calculate the minimum graph editing distance.Then,it also gave the similarity concept and calculation method of the two process models.Finally,this paper verified the correctness of the algorithm and the seven similarity properties are satisfied,and verified the editing distance of the transition graph to satisfy the four distance properties.