A Four Russians algorithm for regular expression pattern matching

ABSTRACT

Given a regular expression R of length P and a word A of length N, the membership problem is to determine if A is in the language denoted by R. An O(PN/lgN) time algorithm is presented that is based on a lgN speedup of the standard O(PN) time simulation of R's nonderministic finite automaton on A using a combination of the node-listing and “Four-Russians” paradigms. This result places a new worst-case upper bound on regular expression pattern matching. Moreover, in practice the method provides an implementation that is faster than existing software for small regular expressions.

REFERENCES

• 1: Ano, A. V. Pattern matching in strings. In R. Book, ed. In Formal Language Theory. Academic Press, Orlando, Fla., 1980.
• 2: Ano, A. V., HOPCROVT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1975.
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: ARLAZAROV, V. L., DINIC, E. A., KRONROD, M. A., AND FARADZEV, I. A. On economic construction of the transitive closure of a directed graph. Dokl. Acad. Nauk SSSR 194 (1970), 487-488 (in Russian). English translation in Soz'iet Math. Dokl. 11 (1975), 1209-1210.
• 5: GALIL, Z. Open problems in stringology. A. Apostolico and Z. Galil, eds. In Combinatorzal Algorithms on Words. Springer-Verlag, New York, 1985, pp. 1-8.
• 6: HECHT, M. S., AND ULLMAN, J. D. A simple algorithm for global flow analysis programs. SIAM J. Comput. 4, 4 (1975), 519-532.
• 7: K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
• 8: MASEK, W. J., AND PATERSON, M.S. A faster algorithm for computing string-edit distances. J. Comput. Syst. Sci. 20, } (1980), 18-31.
• 9: MASEK, W. J., AND PATERSON, M. S. How to compute string-edit distances quickly. D. Sankoff and j. B. Kruskal, eds. In Time Warps, String Edzts, and Macromolecules: The Theoly and Practice of Sequence Comparison. Addison-Wesley, Reading, Mass., 1983, pp. 337-349.
• 10: MILLER. W. Efficient searching of biosequence databases. Tech. Rep. CS-88-34, Dept. Comput. Sci., The Pennsylvania State Univ., University Park, Pa, I988.
• 11: MYERS, E. W., AND MILLER, W. Approximate matching of regular expressions. Bull. Math. Biol. 51, 1 (1989), 5-37.
• 12: Thomas J. Pennello, Very fast LR parsing, ACM SIGPLAN Notices, v.21 n.7, p.145-151, July 1986
• 13: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 14: Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968 [doi>10.1145/363347.363387]
• 15: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 16: WAGNER, e. A., AND SEIFERAS, J.I. Correcting counter-automaton-recognizable languages. SIAM. J. Comput. 7, 3 (1978), 357-375.

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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.5 PATTERN RECOGNITION
      I.5.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
Four Russians paradigm, finite automaton, node listing, regular expression