改进的带可变长度通配符的近似模式串匹配算法

• 作者: 汪浩 王驰
• 来源期刊: 南京理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 可变长度通配符 近似模式串匹配 动态规划 文本-模式倒置
• 年，卷（期）: 2016,（6）
• 页码范围: 687-693
• 页数: 7页
• 分类号: TP394.1
• 字数: 7888字
• 语种: 中文
• DOI: 10.14177/j.cnki.32-1397n.2016.40.06.008

摘要

针对处理可变长度通配符的近似模式串匹配传统算法结果质量不高、易丢解等问题，提出1种启发式的文本-模式倒置算法。基于动态规划思想采用文本-模式倒置策略，搜索得到符合匹配条件子串的开始位置并划分候选集。通过获取初始解、集合划分及优化组合2个过程，筛选出匹配子串的最优解。与同类动态规划( DP)和Sail-Approx算法进行实验对比，结果表明该文算法解的平均增长率为21.9%。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王驰	合肥工业大学计算机与信息学院	9	21	3.0	4.0
2	汪浩	合肥工业大学计算机与信息学院	4	6	1.0	2.0