基于Levenshtein距离的流程检索方法

• 论文 •

基于Levenshtein距离的流程检索方法

曹斌，尹建伟，陈慧蕊

浙江大学计算机科学与技术学院，浙江杭州310027

出版日期:2012-08-15 发布日期:2012-08-25

Levenshtein distance based process retrieval method

CAO Bin, YIN Jian-wei, CHEN Hui-rui

College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China

Online:2012-08-15 Published:2012-08-25

摘要/Abstract

摘要： 为提高大规模流程库的检索效率，提出一种新的流程检索方法。该方法采用最小深度优先搜索编码对流程图模型进行规范化标志，并基于Levenshtein距离计算最小深度优先搜索编码获得相似度值，提高了流程图匹配时相似度计算的效率。通过对原型系统进行实验评估，证明了所提方法在检索效率方面高于图编辑距离，且在返回的检索结果中，相似度最高的前5个结果基本与图编辑距离一致，保证了方法的准确性。

关键词: 流程检索, 流程相似度计算, 深度优先搜索, Levenshtein距离

Abstract: To improve the retrieval efficiency of large scale process database, a new process retrieval method was proposed. This method adopted Depth-First Search(DFS)code to label the process model, and the similarity value was obtained by calculating DFS codes based on Levenshtein distance, which improved the similarity computing efficiency when matching occurred. The prototype system was evaluated by experiment, and the result showed that the method was more efficient than Graph Edit Distance(GED)and top 5 retrieval results were almost same with that of GED which guaranteed the accuracy of proposed method.

Key words: process retrieval, process similarity calculation, depth-first search, Levenshtein distance

中图分类号:

TP319
TP391

曹斌，尹建伟+，陈慧蕊. 基于Levenshtein距离的流程检索方法[J]. .

CAO Bin, YIN Jian-wei+, CHEN Hui-rui. Levenshtein distance based process retrieval method[J]. .