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

Improved approximate pattern matching algorithm with variable length wildcards

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

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%.