Pattern Matching with Flexible Wildcards
作者： Xindong Wu , Ji-Peng Qiang , Fei Xie
DOI: 10.1007/S11390-014-1464-3
关键词:
摘要: Pattern matching with wildcards (PMW) has great theoretical and practical significance in bioinformatics, information retrieval, pattern mining. Due to the uncertainty of wildcards, not only is number all matches exponential respect maximal gap flexibility length, but positions PMW are also hard choose. The objective count one by computationally infeasible. Therefore, rather than solving generic problem, many research efforts have further defined new problems within according different application backgrounds. To break through limitations either fixing or allowing an unbounded flexible (PMFW) allows users control ranges wildcards. In this paper, we provide a survey on state-of-the-art algorithms for PMFW, detailed analyses comparisons, discuss challenges opportunities PMFW applications.
springer.com
sci-hub.se 参考文章(49)
Peter Clifford, Raphaël Clifford, Simple deterministic wildcard matching Information Processing Letters. ,vol. 101, pp. 53- 54 ,(2007) , 10.1016/J.IPL.2006.08.002
Haiping Wang, Fei Xie, Xuegang Hu, Peipei Li, Xindong Wu, Pattern Matching with Flexible Wildcards and Recurring Characters granular computing. pp. 782- 786 ,(2010) , 10.1109/GRC.2010.156
Minghua Zhang, Ben Kao, David W. Cheung, Kevin Y. Yip, Mining periodic patterns with gap requirement from sequences Proceedings of the 2005 ACM SIGMOD international conference on Management of data - SIGMOD '05. pp. 623- 633 ,(2005) , 10.1145/1066157.1066228
Tatsuya Akutsu, Approximate string matching with don't care characters Information Processing Letters. ,vol. 55, pp. 235- 239 ,(1995) , 10.1016/0020-0190(95)00111-O
Meng Zhang, Yi Zhang, Liang Hu, A faster algorithm for matching a set of patterns with variable length don't cares Information Processing Letters. ,vol. 110, pp. 216- 220 ,(2010) , 10.1016/J.IPL.2009.12.007
Wei You, Dominique Fontaine, Jean-Paul Barthès, An automatic keyphrase extraction system for scientific documents Knowledge and Information Systems. ,vol. 34, pp. 691- 724 ,(2013) , 10.1007/S10115-012-0480-2
Adam Kalai, Efficient pattern-matching with don't cares symposium on discrete algorithms. pp. 655- 656 ,(2002) , 10.5555/545381.545468
Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein, Dictionary matching and indexing with errors and don't cares symposium on the theory of computing. pp. 91- 100 ,(2004) , 10.1145/1007352.1007374
Gonzalo Navarro, Mathieu Raffinot, Fast and simple character classes and bounded gaps pattern matching, with application to protein searching research in computational molecular biology. pp. 231- 240 ,(2001) , 10.1145/369133.369220
Dan Guo, Xuegang Hu, Fei Xie, Xindong Wu, Pattern matching with wildcards and gap-length constraints based on a centrality-degree graph Applied Intelligence. ,vol. 39, pp. 57- 74 ,(2013) , 10.1007/S10489-012-0394-4