-
题名基于通配符和长度约束的近似模式匹配算法
被引量:5
- 1
-
-
作者
黄国林
郭丹
胡学钢
-
机构
合肥工业大学计算机与信息学院
-
出处
《计算机应用》
CSCD
北大核心
2013年第3期800-805,共6页
-
基金
国家863计划项目(2012AA011005)
国家自然科学基金资助项目(61229301)
+1 种基金
国家博士后科学基金资助项目(2012M511403)
中央高校基本科研基金资助项目(2010HGXJ0714)
-
文摘
针对近似模式匹配算法在处理带有灵活通配符和长度约束近似模式匹配(APMWL)问题时只能解决替换操作,提出一种基于动态规划的编辑距离矩阵(EDM)构造方法,设计了基于EDM的近似模式匹配算法APM,可以处理近似匹配中的三种编辑操作,即插入、替换和删除操作。此外,根据文本中字符是否允许被重复使用的约束条件,设计APM-OF算法。实验结果表明,APM和APM-OF与同类算法相比具备显著的优势:与Sail_Approx匹配算法实验对比,获取解的平均增长率分别达到8.34%和12.37%;将APM-OF算法应用至模式挖掘中,挖掘出的频繁近似模式个数为OneoffMining算法的2.07倍。
-
关键词
近似匹配
通配符
长度约束
编辑距离矩阵
one—off条件
-
Keywords
approximate pattern matching
wildcard
length constraint
edit distance matrix
one-off condition
-
分类号
TP391.4
[自动化与计算机技术—计算机应用技术]
-