Automatic generation of efficient string matching algorithms by generalized partial computation

ABSTRACT

This paper shows that Generalized Partial Computation (GPC) can automatically generate efficient string matching algorithms. GPC is a program transformation method utilizing partial information about input data and auxiliary functions as well as the logical structure of a source program. GPC uses both a classical partial evaluator and an inference engine such as a theorem prover to optimize programs. First, we show that a Boyer-Moore (BM) type pattern matcher without the bad-character heuristic can be generated from a simple non-linear backward matcher by GPC. This sort of problems has already been discussed in the literature using offline partial evaluators. However, there was no proof that every generated matcher runs in the same way as the BM. In this paper we prove that the problem can be solved starting from a simple non-linear pattern matcher as a source program. We also prove that a Knuth-Morris-Pratt (KMP) type linear string matcher can be generated from a naive non-linear forward matcher by GPC.

REFERENCES

• 1: Mads Sig Ager , Olivier Danvy , Henning Korsholm Rohde, On obtaining Knuth, Morris, and Pratt's string matcher by partial evaluation, Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, p.32-46, September 12-14, 2002, Aizu, Japan [doi>10.1145/568173.568177]
• 2: Amtoft, T., Consel, C., Danvy, O. and Malmkjaer, K.: The abstraction and instantiation of string-matching programs, BRICS RS-01-12, Department of Computer Science, University of Aarhus, April 2001.
• 3: 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]
• 4: Richard Cole, Tight Bounds on the Complexity of the Boyer--Moore String Matching Algorithm, SIAM Journal on Computing, v.23 n.5, p.1075-1091, Oct. 1994 [doi>10.1137/S0097539791195543]
• 5: Charles Consel , Olivier Danvy, Partial evaluation of pattern matching in strings, Information Processing Letters, v.30 n.2, p.79-86, January 1989 [doi>10.1016/0020-0190(89)90113-0]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Futamura, Y. and Nogi, K.Generalized partial computation. in Bjørner, D. and Ershov, A. P. and Jones, N. D. (eds), Partial Evaluation and Mixed Computation, 133--151, North-Holland, 1988.
• 8: Yoshihiko Futamura , Kenroku Nogi , Akihiko Takano, Essence of generalized partial computation, Theoretical Computer Science, v.90 n.1, p.61-79, Nov. 1991 [doi>10.1016/0304-3975(91)90299-H]
• 9: Yoshihiko Futamura , Zenjiro Konishi , Robert Glück, Program transformation system based on generalized partial computation, New Generation Computing, v.20 n.1, p.75-99, January 2002 [doi>10.1007/BF03037260]
• 10: Robert Glück , Andrei V. Klimov, Occam's Razor in Metacompuation: the Notion of a Perfect Process Tree, Proceedings of the Third International Workshop on Static Analysis, p.112-123, September 22-24, 1993
• 11: Neil D. Jones, An introduction to partial evaluation, ACM Computing Surveys (CSUR), v.28 n.3, p.480-503, Sept. 1996 [doi>10.1145/243439.243447]
• 12: Knuth, D.E., Morris, J. and Pratt, V.: Fast pattern matching in strings. SIAM Journal on Computing, 6(1973), 325--350.
• 13: Alberto Pettorossi , Maurizio Proietti, Rules and strategies for transforming functional and logic programs, ACM Computing Surveys (CSUR), v.28 n.2, p.360-414, June 1996 [doi>10.1145/234528.234529]
• 14: Sørensen M. H., Glück R., Jones N. D., A positive supercompiler. In: Journal of Functional Programming, 6(6), 1996. 811--838.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Partial evaluation

General Terms:
Algorithms

Keywords:
Boyer-Moore pattern matcher, Knuth-Morris-Pratt pattern matcher, automatic program generation, naive pattern matcher