基于通配符和长度约束的近似模式匹配算法

作     者：黄国林 郭丹 胡学钢 HUANG Guolin;GUO Dan;HU Xuegang

作者机构：合肥工业大学计算机与信息学院合肥230009 

基　　金：国家863计划项目(2012AA011005) 国家自然科学基金资助项目(61229301) 国家博士后科学基金资助项目(2012M511403) 中央高校基本科研基金资助项目(2010HGXJ0714) 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2013年第33卷第3期

页      码：800-805页

摘      要：针对近似模式匹配算法在处理带有灵活通配符和长度约束近似模式匹配(APMWL)问题时只能解决替换操作,提出一种基于动态规划的编辑距离矩阵(EDM)构造方法,设计了基于EDM的近似模式匹配算法APM,可以处理近似匹配中的三种编辑操作,即插入、替换和删除操作。此外,根据文本中字符是否允许被重复使用的约束条件,设计APM-OF算法。实验结果表明,APM和APM-OF与同类算法相比具备显著的优势:与Sail_Approx匹配算法实验对比,获取解的平均增长率分别达到8.34%和12.37%;将APM-OF算法应用至模式挖掘中,挖掘出的频繁近似模式个数为OneoffMining算法的2.07倍。

主 题 词：近似匹配 通配符 长度约束 编辑距离矩阵 one—off条件 

学科分类：1305[艺术学-设计学类] 13[艺术学] 081104[081104] 08[工学] 0804[工学-材料学] 081101[081101] 0811[工学-水利类] 

核心收录：

D　O　I：10.3724/SP.J.1087.2013.00800

馆 藏 号：203525733...