Computer Science ›› 2016, Vol. 43 ›› Issue (4): 279-283.doi: 10.11896/j.issn.1002-137X.2016.04.057

Previous Articles     Next Articles

Models for Pattern Matching with Wildcards and Length Constraints

WANG Hao, WANG Hai-ping and WU Xin-dong   

  • Online:2018-12-01 Published:2018-12-01

Abstract: For the problem of pattern matching with wildcards and length constraints (PMWL),the patterns are composed of a sequence of sub-patterns,where any two adjacent sub-patterns with flexible gaps are in a specified range of the text.Existing work includes a heuristic strategy and its completeness analysis with constraints,but the PMWL problem still needs systematic studies.We drew on the experience of constraint satisfaction problems(CSPs) and set up a 3-tuple model consisting of variables,domains and constraints.We then derived formal descriptions for the basic concepts and properties.Also,a tree-based matching algorithm was presented to solve the PMWL problem under certain conditions.

Key words: Length constraints,Wildcards,Matcing model,Pattern matching

[1] Fischer M J,Paterson M S.String matching and other products[R].Cambridge,MA:Massachusetts Institute of Technology ,1974
[2] Manber U,Baeza-Yates R.An Algorithm for String Matching with a Sequence of Don’t cares[J].Information Processing Letters,1991,37(3):133-136
[3] Califf M E,Mooney R J.Bottom-up Relational Learning of Pattern Matching Rules for Information Extraction[J].Journal of Machine Learning Research,2003,4(6):177-210
[4] Guo Dan,Hu Xue-gang,Xie Fei,et al.Pattern Matching withWildcards and Gap-length Constraints Based on a Centrality-degree Graph[J].Applied Intelligence,2013,39:57-74
[5] Dahiya A,Garg D.Maximal pattern matching with flexible wildcard gaps and one-off constraint[C]∥International Conference on Advances in Computing,Communications and Informatics.Arras,France,2014:1107-1112
[6] Wu Xin-dong,Qiang Ji-peng,Xie Fei.Pattern Matching with Fle-xible Wildcards[J].Journal of Computer Science and Technology,2014,29(5):740-750
[7] Xiang Tai-ning,Guo Dan,Wang Hai-ping,et al.CharacteristicAnalysis of Pattern Matching with Wildcards Problem and its Solution Space[J].Computer Science,2014,41(9):269-273(in Chinese) 项泰宁,郭丹,王海平,等.带通配符的模式匹配问题及其解空间特征分析[J].计算机科学,2014,41(9):269-273
[8] Chen Gong,Wu Xin-dong,Zhu Xing-quan,et al.Efficient string matching with wildcards and length constraints[J].Knowledge and Information Systems,2006,10(4):399-419
[9] Qiang Ji-peng,Xie Fei,Gao Jun,et al.Pattern Matching withArbitrary-length Wildcards[J].Acta Automatica Sinica,2014,40(11):2499-2511(in Chinese) 强继朋,谢飞,高隽,等.带任意长度通配符的模式匹配[J].自动化学报,2014,40(11):2499-2511
[10] Min Fan,Wu Xin-dong,Lu Zhen-yu.Pattern matching with independent wildcard gaps[C]∥Proceedings of the 8th IEEE International Conference on Dependable,Autonomic and Secure Computing.2009:194-199
[11] Wu You-xi,Liu Ya-wei,Guo Lei,et al.Subnettrees for StrictPattern Matching with General Gaps and Length Constraints[J].Journal of Software,2013,24(5):915-932(in Chinese) 武优西,刘亚伟,郭磊,等.子网树求解一般间隙和长度约束严格模式匹配[J].软件学报,2013,24(5):915-932
[12] Brailsford S C,Potts C N,Smith B M.Constraint satisfaction problems:Algorithms and applications[J].European Journal of Operational Research,1999,119:557-581
[13] Bala S.Regular language matching and other decidable cases ofthe satisfiability problem for constraints between regular open terms[J].Theory of Computing Systems,2004,39:596-607
[14] Kucherov G,Rusinowitch M.Matching a set of strings with va-riable length don’t cares[C]∥ Proceedings of the 6th sympo-sium on Combinatorial Pattern Matching.1995:230-247
[15] Kalai A.Efficient pattern-matching with don’t cares[C]∥Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms.2002:655-656
[16] Allauzen C,Raffinot M.Factor oracle of a set of words:Technical Report 99-11[R].Institut Gaspard-Monge,1999
[17] Wang Hai-ping,Hu Xue-gang,Xie Fei,et al.Impact of Pattern Feature on Pattern Matching Problem with Wildcards and Length Constraints[J].Pattern Recognition and Artificial Intelligence,2012,25(6):1013-1021(in Chinese) 王海平,胡学钢,谢飞,等.模式特征对带有通配符和长度约束的模式匹配问题的影响[J].模式识别与人工智能,2012,25(6):1013-1021
[18] Morgante M,Policriti A,Vitacolonna N,et al.Structured motifs search[J].Journal of Computational Biology,2005,12(8):1065-1082
[19] Initiative T A G,Copenhaver G P.Arabidopsis Genome Initiative.Analysis of the genome sequence of the flowering plant Ara-bidopsis thaliana[J].Nature,2002,408(6814):796-815

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!