Multipattern string matching with q-grams

ABSTRACT

We present three algorithms for exact string matching of multiple patterns. Our algorithms are filtering methods, which apply q-grams and bit parallelism. We ran extensive experiments with them and compared them with various versions of earlier algorithms, e.g., different trie implementations of the Aho--Corasick algorithm. All of our algorithms appeared to be substantially faster than earlier solutions for sets of 1,000--10,000 patterns and the good performance of two of them continues to 100,000 patterns. The gain is because of the improved filtering efficiency caused by q-grams.

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: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 3: R. A. Baeza-Yates, Improved string searching, Software—Practice & Experience, v.19 n.3, p.257-271, March 1989 [doi>10.1002/spe.4380190305]
• 4: 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]
• 5: 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]
• 6: Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
• 7: Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
• 8: Mike Fisk , George Varghese, Fast Content-Based Packet Handling for Intrusion Detection, University of California at San Diego, La Jolla, CA, 2001
• 9: Kimmo Fredriksson, Faster String Matching with Super-Alphabets, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.44-57, September 11-13, 2002
• 10: Fredriksson, K. and Grabowski, S. 2005. Practical and optimal string matching. In Proceedings of 12th Symposium on String Processing and Information Retrieval (SPIRE'05). Lecture Notes in Computer Science, vol. 3772. Springer-Verlag, Berlin.
• 11: Gum, B. and Lipton, R. 2001. Cheaper by the dozen: Batched algorithms. In Proceedings of the 1st SIAM International Conference on Data Mining.
• 12: Horspool, N. 1980. Practical fast searching in strings. Softw. Pract. Exper. 10, 501--506.
• 13: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 14: Kim, S. and Kim, Y. 1999. A fast multiple string-pattern matching algorithm. In Proceedings of 17th AoM/IAoM Conference on Computer Science.
• 15: Markatos, E. P., Antonatos, S., Polychronakis, M., and Anagnostakis, K. G. 2002. Exclusion-based signature matching for intrusion detection. In Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN). ACTA Press. Calgary, AB, Canada, 146--152.
• 16: Robert Muth , Udi Manber, Approximate Multiple Strings Search, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.75-86, June 10-12, 1996
• 17: Gonzalo Navarro , Mathieu Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata, Journal of Experimental Algorithmics (JEA), 5, p.4-es, 2000 [doi>10.1145/351827.384246]
• 18: Gonzalo Navarro , Mathieu Raffinot, Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences, Cambridge University Press, New York, NY, 2002
• 19: Peltola, H. and Tarhio, J. 2003. Alternative algorithms for bit-parallel string matching. In Proceedings of 10th Symposium on String Processing and Information Retrieval (SPIRE'03). Lecture Notes in Computer Science, vol. 2857. Springer-Verlag, Berlin. 80--94.
• 20: Ping, L., Jian-long, T., and Yan-bing, L. 2005. A partition-based efficient algorithm for large scale multiple-strings matching. In Proceedings of 12th Symposium on String Processing and Information Retrieval (SPIRE'05). Lecture Notes in Computer Science, vol. 3772. Springer-Verlag, Berlin.
• 21: Tuck, N., Sherwood, T., Calder, B., and Varghese, G. 2004. Deterministic memory-efficient string matching algorithms for intrusion detection. In Proceedings of the IEEE Infocom Conference.
• 22: Wu, S. and Manber, U. 1992a. Agrep---a fast approximate pattern-matching tool. In Proceedings of the Usenix Winter 1992 Technical Conference. 153--162.
• 23: 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]
• 24: Wu, S. and Manber, U. 1994. A fast algorithm for multi-pattern searching. Tech. Rep. TR-94-17, Department of Computer Science. University of Arizona, Tucson, Arizona.
• 25: Rui Feng Zhu , Tadao Takaoka, A technique for two-dimensional pattern matching, Communications of the ACM, v.32 n.9, p.1110-1120, Sept. 1989 [doi>10.1145/66451.66459]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms

Keywords:
Content scanning, intrusion detection, multiple string matching