南京理工大学学报（自然科学版）2016，Vol.40Issue(6)：687-693,7.DOI:10.14177/j.cnki.32-1397n.2016.40.06.008
改进的带可变长度通配符的近似模式串匹配算法
Improved approximate pattern matching algorithm with variable length wildcards
摘要
Abstract
A heuristic text-pattern reversion algorithm is proposed for the low result quality and losing solution problems of traditional approximate pattern matching algorithms for variable length wildcards. The starting position of the substrings meeting the matching condition is searched and the candidate sets are partitioned based on dynamic programming and text-pattern reversion. The optimal solution of matching substrings is screened by obtaining the initial solution,dividing and assembling the sets optimally. Compared with the similar dynamic programming ( DP ) and Sail-Approx algorithms,the experimental results show that the average growth rate of the solution of this algorithm is improved by 21 . 9%.关键词
可变长度通配符/近似模式串匹配/动态规划/文本-模式倒置Key words
variable length wildcards/approximate pattern matching/dynamic programming/text-pattern reversion分类
信息技术与安全科学引用本文复制引用
汪浩,王驰..改进的带可变长度通配符的近似模式串匹配算法[J].南京理工大学学报（自然科学版）,2016,40(6):687-693,7.基金项目
国家自然科学基金(61229031) （61229031）
