|Table of Contents|

Improved approximate pattern matching algorithm with variable length wildcards

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
2016年06期
Page:
687-
Research Field:
Publishing date:

Info

Title:
Improved approximate pattern matching algorithm with variable length wildcards
Author(s):
Wang HaoWang Chi
School of Computer and Information,Hefei University of Technology,Hefei 230009,China
Keywords:
variable length wildcards approximate pattern matching dynamic programming text-pattern reversion
PACS:
TP394.1
DOI:
10.14177/j.cnki.32-1397n.2016.40.06.008
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%.

References:

[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.
[15]黄国林,郭丹,胡学钢.基于通配符和长度约束的近似模式匹配算法[J].计算机应用,2013,33(3):800-805.
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.

Memo

Memo:
-
Last Update: 2016-12-30