|Table of Contents|

Improved approximate pattern matching algorithm with variable length wildcards


Research Field:
Publishing date:


Improved approximate pattern matching algorithm with variable length wildcards
Wang HaoWang Chi
School of Computer and Information,Hefei University of Technology,Hefei 230009,China
variable length wildcards approximate pattern matching dynamic programming text-pattern reversion
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%.


[1] Fischer M J,Paterson M S.String matching and other products[R].Cambridge,MA,USA:Massachusetts Institute of Technology,1974:113-125.
[2]Sellers P H.The theory and computation of evolutionary distances:Pattern recognition[J].Journal of Algorithms,1980,1(4):359-373.
[3]Manber U,Baeza-Yates R.An algorithm for string matching with a sequence of don't cares[J].Inf Proc Lett,1991,37(3):133-136.
[4]Akutsu T.Approximate string matching with variable length don't care characters[J].IEICE Transactions Info and Systems,1996,79(9):1353-1354.
[5]Cole R,Gottlieb L A,Lewenstein M.Dictionary matching and indexing with errors and don't cares[C]//Proceedings of the 36th ACM Symposium on the Theory of Computing.New York,USA:ACM Press,2004:91-100.
[6]Chen G,Wu X D,Zhu X Q,et al.Efficient string matching with wildcards and length constraints[J].Know-ledge and Information Systems,2006,10(4):399-419.
[7]He D,Wu X,Zhu X.SAIL-APPROX:An efficient on-line algorithm for approximate pattern matching with wildcards and length constraints[C]//Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine.Silicon Valley,CA,USA:IEEE Computer Society Press,2007:151-158.
[8]Zhong Cheng,Fan Dajuan.Parallel algorithms for approximate string matching with multi-round distribution strategy on heterogeneous cluster computing systems[J].Journal of Computer Research and Development,2008,51:105-112.
[9]Xu Kefu,Cui Wenke,Hu Yue,et al.Bit-parallel multiple approximate string matching based on GPU[J].Procedia Computer Science,2013,17:523-529.
[10]Prasad R,Sharma A K,Singh A.Efficient bit-parallel multi-patterns approximate string matching algorithms[J].Scientific Research and Essays,2011,6(4):876-881.
[11]Wu Youxi,Wu Xindong,Min Fan,et al.A net tree for pattern matching with flexible wildcard constraints[C]//Proceedings of the 11th IEEE International Conference on Information Reuse and Integration(IR12010).Las Vegas,USA:IEEE,2010:109-114.
[12]Wang Haiping,Xie Fei,Hu Xuegang,et al.Pattern matching with flexible wildcards and recurring characters[C]//Pro of the 2010 IEEE Conference on Granular Computing(GrC-2010).Washington,DC,USA:IEEE Computer Society,2010:782-786.
[13]Min Fan,Wu Xindong,Lu Zhenyu.Pattern matching with independent wildcard gaps[C]//Proceedings of the 8th IEEE International Conference on Pervasive Intelligence and Computing(PICom2009).Chengdu:IEEE,2009:12-14.
[14]Wang Chi,Wang Hao,Xie Zhao,et al.Exact string matching with variable length of don't cares based on suffix tree[C]//2011 International Conference on Information Science and Technology.Nanjing:IEEE,2011:109-113.
Huang Guolin,Guo Dan,Hu Xuegang.Algorithms for approximate pattern matching with wildcards and length constraints[J].Journal of Computer Applications,2013,33(3):800-805.


Last Update: 2016-12-30