Fast and flexible string matching by combining bit-parallelism and suffix automata

ABSTRACT

The most important features of a string matching algorithm are its efficiency and its flexibility. Efficiency has traditionally received more attention, while flexibility in the search pattern is becoming a more and more important issue. Most classical string matching algorithms are aimed at quickly finding an exact pattern in a text, being Knuth-Morris-Pratt (KMP) and the Boyer-Moore (BM) family the most famous ones. A recent development uses deterministic "suffix automata" to design new optimal string matching algorithms, e.g. BDM and TurboBDM. Flexibility has been addressed quite separately by the use of "bit-parallelism", which simulates automata in their nondeterministic form by using bits and exploiting the intrinsic parallelism inside the computer word, e.g. the Shift-Or algorithm. Those algorithms are extended to handle classes of characters and errors in the pattern and/or in the text, their drawback being their inability to skip text characters. In this paper we merge bit-parallelism and suffix automata, so that a nondeterministic suffix automaton is simulated using bit-parallelism. The resulting algorithm, called BNDM, obtains the best from both worlds. It is much simpler to implement than BDM and nearly as simple as Shift-Or. It inherits from Shift-Or the ability to handle flexible patterns and from BDM the ability to skip characters. BNDM is 30%-40% faster than BDM and up to 7 times faster than Shift-Or. When compared to the fastest existing algorithms on exact patterns (which belong to the BM family), BNDM is from 20% slower to 3 times faster, depending on the alphabet size. With respect to flexible pattern searching, BNDM is by far the fastest technique to deal with classes of characters and is competitive to search allowing errors. In particular, BNDM seems very adequate for computational biology applications, since it is the fastest algorithm to search on DNA sequences and flexible searching is an important problem in that area. As a theoretical development related to flexible pattern matching, we introduce a new automaton to recognize suffixes of patterns with classes of characters. To the best of our knowledge, this automaton has not been studied before.

REFERENCES

• 1: Karl Abrahamson, Generalized string matching, SIAM Journal on Computing, v.16 n.6, p.1039-1051, December 1, 1987 [doi>10.1137/0216067]
• 2: Ricardo A. Baeza-Yates, Text-Retrieval: Theory and Practice, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92, Volume 1, p.465-476, September 07-11, 1992
• 3: Ricardo Baeza-Yates , Gaston H. Gonnet, A new approach to text searching, Communications of the ACM, v.35 n.10, p.74-82, Oct. 1992 [doi>10.1145/135239.135243]
• 4: Ricardo A. Baeza-Yates , Gaston H. Gonnet, Fast string matching with mismatches, Information and Computation, v.108 n.2, p.187-199, Feb. 1, 1994 [doi>10.1006/inco.1994.1007]
• 5: BAEZA-YATES, R. AND NAVARRO, G. 1999. Faster approximate string matching. <i>Algorithmica 23</i>, 2, 127-158.
• 6: Ricardo A. Baeza-Yates , Chris H. Perleberg, Fast and Practical Approximate String Matching, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.185-192, April 29-May 01, 1992
• 7: BLUMER, A., EHRENFEUCHT, A., AND HAUSSLER, D. 1989. Average sizes of suffix trees and dawgs. <i>Discrete Applied Mathematics 24</i>, 1, 37-45.
• 8: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 9: Maxine Crochemore, Transducers and repetitions, Theoretical Computer Science, v.45 n.1, p.63-86, Sept. 1986
• 10: CROCHEMORE, M., CZUMAJ, A., GASIENIEC, L., JAROMINEK, S., LECROQ, T., PLANDOWSKI, W., AND RYTTER, W. 1993. Fast practical multi-pattern matching. Rapport 93-3, Institut Gaspard Monge, Universiteacute; de Marne la Valleacute;e.
• 11: Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
• 12: CZUMAJ, A., CROCHEMORE, M., GASIENIEC, L., JAROMINEK, S., LECROQ, T., PLANDOWSKI, W., AND RYTTER, W. 1994. Speeding up two string-matching algorithms. <i>Algorithmica 12</i>, 247-267.
• 13: Nadia El-Mabrouk , Maxime Crochemore, Boyer-Moore Strategy to Efficient Approximate String Matching, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.24-38, June 10-12, 1996
• 14: FISCHER, M. J. AND PATERSON, M. 1974. String matching and other products. In R. M. KARP Ed., <i>Proceedings SIAM-AMS Complexity of Computation</i> (Providence, RI, 1974), pp. 113-125.
• 15: HORSPOOL, R.N. 1980. Practical fast searching in strings. <i>Software Practice and Experience 10</i>, 501-506.
• 16: Petteri Jokinen , Jorma Tarhio , Esko Ukkonen, A comparison of approximate string matching algorithms, Software—Practice & Experience, v.26 n.12, p.1439-1458, Dec. 1996 [doi>10.1002/(SICI)1097-024X(199612)26:12<1439::AID-SPE71>3.0.CO;2-1]
• 17: KNUTH, D. E., MORRIS, J. H., AND PRATT, V.R. 1977. Fast pattern matching in strings. <i>SIAM Journal on Computing 6</i>, 1, 323-350.
• 18: LECROQ, T. 1992. <i>Recherches de mot.</i> Ph.D. thesis, Universiteacute; d'Orleacute;ans, France.
• 19: Gene Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM (JACM), v.46 n.3, p.395-415, May 1999 [doi>10.1145/316542.316550]
• 20: NAVARRO, G. 1997. A partial deterministic automaton for approximate string matching. In <i>Proc. of WSP'97</i> (1997), pp. 112-124. Carleton University Press.
• 21: NAVARRO, G. 1998. <i>Approximate Text Searching</i>. Ph.D. thesis, Department of Computer Science, University of Chile. Tech. Report TR/DCC-98-14. ftp://ftp.dcc.uchile.cl/- pub/users/gnavarro/thesis98.ps.gz.
• 22: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 23: NAVARRO, G. 2000b. Nrgrep: a fast and flexible pattern matching tool. Technical Report TR/DCC-2000-3 (Aug.), Dept. of Computer Science, Univ. of Chile. ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/nrgrep.ps.gz.
• 24: Gonzalo Navarro , Ricardo Baeza-Yates, Very fast and simple approximate string matching, Information Processing Letters, v.72 n.1-2, p.65-70, Oct. 29, 1999 [doi>10.1016/S0020-0190(99)00121-0]
• 25: Gonzalo Navarro , Mathieu Raffinot, A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching, Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching, p.14-33, July 20-22, 1998
• 26: Gonzalo Navarro , Mathieu Raffinot, Fast Regular Expression Search, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.198-212, July 19-21, 1999
• 27: Gonzalo Navarro , Mathieu Raffinot, Fast and simple character classes and bounded gaps pattern matching, with application to protein searching, Proceedings of the fifth annual international conference on Computational biology, p.231-240, April 22-25, 2001, Montreal, Quebec, Canada [doi>10.1145/369133.369220]
• 28: PINTER, R.Y. 1985. Efficient string matching with don't care pattern. In A. APOSTOLICO AND Z. GALIL Eds., <i>Combinatorial Algorithms on Words</i>, pp. 11-29. Springer-Verlag, Berlin.
• 29: RAFFINOT, M. 1997a. Asymptotic estimation of the average number of terminal states in dawgs. In <i>Proc. WSP'97</i> (1997), pp. 140-148. Carleton University Press.
• 30: RAFFINOT, M. 1997b. On the multi backward dawg matching algorithm (MultiBDM). In <i>Proc. WSP'97</i> (1997), pp. 149-165. Carleton University Press.
• 31: Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990 [doi>10.1145/79173.79184]
• 32: Jorma Tarhio , Esko Ukkonen, Approximate Boyer-Moore string matching, SIAM Journal on Computing, v.22 n.2, p.243-260, April 1993 [doi>10.1137/0222018]
• 33: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
• 34: WU, S., MANBER, U., AND MYERS, E. 1996. A sub-quadratic algorithm for approximate limited expression matching. <i>Algorithmica 15</i>, 1, 50-67.
• 35: YAO, A. 1979. The complexity of pattern matching for a random string. <i>SIAM J. on Computing 8</i>, 368-387.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory