宋金凤 闻立杰 王建民

(清华大学软件学院 北京 100084)

(632230913@qq.com)

流程模型对于一个企业来说，具有十分重要的价值，它的作用不仅仅是对企业业务流程的具体刻画，而且有利于企业对业务流程进行分析、验证和优化[1].流程模型的管理包括模型分析、模型检索和模型重用等方面[2].流程模型相似性度量在流程模型管理的各个方面都发挥着非常重要的作用.目前的流程模型相似性算法主要分为3类[2]：1)元素标签映射的相似性度量；2)模型结构的相似性度量；3)行为语义的相似性度量.

元素标签映射的相似性度量，是基于节点的成对标签比较.它是通过定义2个模型的节点标签之间的映射，从而计算出相似性.标签匹配相似度等于匹配的节点数除以总节点数.为了检测标签的相似性，常常运用模式匹配算法[3]和本体匹配算法[4].Dijkman等人[5]在相似性度量方面做出了很多研究，提出了较多的相似性度量算法，最简单的一种叫标签对齐的相似性度量算法.Ehrig等人[6]提出了基于标签语义的相似性度量方法.该类算法思路简单、计算快速，但未对模型的拓扑结构和行为语义加以考虑，导致计算结果不够精准.

结构相似性度量方法，是把模型看作一个图，利用公共子图同构和图编辑距离对模型的相似性进行度量.图编辑距离详细定义了从一个图转换到另一个图所需的最小原子级图操作.Dijkman等人[7]提出了一种结构相似性度量方法，该方法定义了进行每一种编辑操……