Approximate multi-pattern matching is an important issue that is widely and frequently utilized, when the pattern contains variable-length wildcards. In this paper, two suffix array-based algorithms have been proposed to solve this problem. Suffix array is an efficient data structure for exact string matching in existing studies, as well as for approximate pattern matching and multi-pattern matching. An algorithm called MMSA-S is for the short exact characters in a pattern by dynamic programming, while another algorithm called MMSA-L deals with the long exact characters by the edit distance method. Experimental results of Pizza & Chili corpus demonstrate that these two newly proposed algorithms, in most cases, are more time-efficient than the state-of-the-art comparison algorithms.
NavarroG., A guided tour to approximate string matching, ACM computing surveys (CSUR)33(1) (2001), 31–88.
2.
GogS.KärkkäinenJ.KempaD.PetriM. and PuglisiS.J., Fixed Block Compression Boosting in FM-Indexes: Theory and Practice, Algorithmica81(4) (2019), 1370–1391.
3.
NavarroG.Baeza-YatesR.A.SutinenE. and TarhioJ., Indexing methods for approximate string matching, IEEE Data Eng. Bull.24(4) (2001), 19–27.
4.
HonW.K.LamT.W.ShahR.ThankachanS.V.TingH.F. and YangY., Dictionary matching with a bounded gap in pattern or in text, Algorithmica80(2) (2018), 698–713.
5.
RahmanM.S.IliopoulosC.S.LeeI.MohamedM. and SmythW.F., Finding patterns with variable length gaps or don’t cares, In International Computing and Combinatorics Conference, Springer, Berlin, Heidelberg, 2006, pp. 146–155.
6.
AkutsuT., Approximate string matching with variable length don’t care characters, Ieice Transactions On Information And Systems E Series D79 (1996), 1353–1354.
7.
FischerM.J. and PatersonM.S., String-Matching and Other Products (No. MAC-TM-41), Massachusetts Inst Of Tech Cambridge Project Mac, 1974.
8.
KnuthD.E., Jr.MorrisJ.H. and PrattV.R., Fast pattern matching in strings, SIAM Journal on Computing6(2) (1977), 323–350.
9.
AhoA.V. and CorasickM.J., Efficient string matching: an aid to bibliographic search, Communications of the ACM18(6) (1975), 333–340.
10.
Commentz-WalterB., A string matching algorithm fast on the average, In International Colloquium on Automata, Languages, and Programming, Springer, Berlin, Heidelberg, 1979, pp. 118–132.
11.
WuS. and ManberU., A fast algorithm for multi-pattern searching, University of Arizona. Department of Computer Science, 1994, pp. 1–11.
12.
ChiuS.Y.HonW.K.ShahR. et al., I/O-efficient compressed text indexes: From theory to practice, 2010 Data Compression Conference, IEEE, 2010, pp. 426–434.
13.
LiH. and HomerN., A survey of sequence alignment algorithms for next-generation sequencing, Briefings in Bioinformatics11(5) (2010), 473–483.
14.
ClarkC.R. and SchimmelD.E., Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns, International Conference on Field Programmable Logic and Applications. Springer, Berlin, Heidelberg, 2003, pp. 956–959.
15.
ManberU. and MyersG., Suffix arrays: a new method for on-line string searches, Journal on Computing22(5) (1993), 935–948.
16.
MinF.WuX. and LuZ., Pattern matching with independent wildcard gaps, In 2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing, IEEE, 2009, pp. 194–199.
17.
ZhangM.ZhangY. and HuL., A faster algorithm for matching a set of patterns with variable length don’t cares, Information Processing Letters110(6) (2010), 216–220.
18.
GuoD.HongX.L.HuX.G.GaoJ.LiuY.L.WuG.Q. and WuX., A bit-parallel algorithm for sequential pattern matching with wildcards, Cybernetics and Systems42(6) (2011), 382–401.
19.
ColeR. and HariharanR., Verifying candidate matches in sparse and wildcard matching, In Proc. the 34th Annual ACM Sym-posium on Theory of Computing, 2002, pp. 592–601.
20.
ZhuX. and WuX., Mining complex patterns across sequences with gap requirements, In proc. the 20th Int. Joint Conf. Artificial intelligence, 2007, pp. 2934–2940.
21.
HaapasaloT.SilvastiP.SippuS. and Soisalon-SoininenE., Online dictionary matching with variable-length gaps, In: Proceedings of the 10th International Symposium, SEA Kolimpari, Chania, Crete, Greece. Berlin Heidelberg: Springer, 2011, 76–87.
22.
BilleP.GørtzI.L.VildhøjH.W. et al., String matching with variable length gaps, Theoretical Computer Science443(20) (2012), 25–34.
23.
RaffinotM., On the multi backward dawg matching algorithm (MultiBDM), In Proceedings of the 4th South American Workshop on String Processing Carleton, University Press, 1997, pp. 149–165.
24.
CrochemoreM.CzumajA.GasieniecL.LecroqT.PlandowskiW. and RytterW., Fast practical multi-pattern matching, Information Processing Letters71(3-4) (1999), 107–113.
25.
ZhouZ.ZhangT.ChowS.S.ZhangY. and ZhangK., Efficient authenticated multi-pattern matching, In Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security, ACM, 2016, pp. 593–604.
26.
MuthR. and ManberU., Approximate multiple string search, In Annual Symposium on Combinatorial Pattern Matching Springer, Berlin, Heidelberg, 1996, pp. 75–86.
27.
Baeza-YatesR. and NavarroG., Multiple approximate string matching, In Workshop on Algorithms and Data Structures, Springer, Berlin, Heidelberg, 1997, pp. 174–184.
28.
KulekciM.O., Tara: An algorithm for fast searching of multiple patterns on text files, In 2007 22nd international symposium on computer and information sciences, IEEE, 2007, pp. 1–6.
29.
ZhangM.ZhangY.TangJ. and BaiX., Multi-pattern Matching with Wildcards, JSW6(12) (2011), 2391–2398.
30.
BiswasS.GangulyA.ShahR. and ThankachanS.V., Ranked document retrieval for multiple patterns, Theoretical Computer Science746 (2018), 98–111.
31.
FredkinE., Trie memory, Communications of the ACM3(9) (1960), 490–499.
32.
WeinerP., Linear pattern matching algorithm, 14th Annual IEEE Symposium on Switching and Automata Theory, 1973, pp. 1–11.
33.
ChattarajA. and ParidaL., An inexact-suffix-tree-based algorithm for detecting extensible patterns, Theoretical Computer Science335(1) (2005), 3–14.
34.
UkkonenE., Maximal and minimal representations of gapped and non-gapped motifs of a string, Theoretical Computer Science410(43) (2009), 4341–4349.
35.
BilleP.GørtzI.L. et al., String indexing for patterns with wildcards, Theory of Computing Systems55(1) (2014), 41–60.
36.
RahmanM.S.IliopoulosC.S.LeeI.MohamedM. and SmythW.F., Finding patterns with variable length gaps or don’t cares, In International Computing and Combinatorics Conference, Springer, Berlin, Heidelberg, 2006, pp. 146–155.
37.
ShresthaA.M.S.FrithM.C. and HortonP., A bioinformatician’s guide to the forefront of suffix array construction algorithms, Briefings in bioinformatics15(2) (2014), 138–154.
38.
NongG.ZhangS. and ChanW.H., Two efficient algorithms for linear time suffix array construction, IEEE Transactions on Computers60(10) (2011), 1471-1484.
39.
ThankachanS.V.ApostolicoA.AluruS., A Provably Efficient Algorithm for the k-Mismatch Average Common Substring Problem, Journal of Computational Biology (6) (2016), 472–482.
40.
HonW.K.LamT.W.ShahR.ThankachanS.V. and YangY., Dictionary matching with a bounded gap in pattern or in text, Algorithmica80(6) (2017), 1–16.
41.
LiuN.XieF. and WuX., Multi-pattern matching with variable-length wildcards using suffix tree, Pattern Analysis and Applications21(4) (2018), 1151–1165.
42.
UkkonenE., On-line construction of suffix trees, Algorithmica14(3) (1995), 249–260.
43.
SalmelaL.TarhioJ. and KytöjokiJ., Multipattern string matching with q-grams, Journal of Experimental Algorithmics (JEA)11 (2007), 1.
44.
UkkonenE., Approximate string-matching with q-grams and maximal matches, Theoretical computer science92(1) (1992), 191–211.
45.
Arınİ.ErpamM.K. and SaygınY., I-TWEC: Interactive clustering tool for Twitter, Expert Systems with Applications96 (2018), 1–13.
