More Efficient Bottom-Up Multi-Pattern Matching in Trees
NEW YORK UNIV NY COURANT INST OF MATHEMATICAL SCIENCES
Pagination or Media Count:
Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for general purpose pattern matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chases bottom-up algorithm for pattern preprocessing. A preliminary implementation of our algorithm runs ten times faster than Chases implementation on the hardest problem instances. Our preprocessing algorithm has the advantage of being online with respect to pattern additions and deletions. It also adapts to favorable input instances, and on Hoffmann and ODonnells class of Simple Patterns, it performs better than their special purpose algorithm tailored to this class. We show how to modify our algorithm using a new decomposition method to obtain a spacetime tradeoff. Finally, we trade a log factor in time for a linear space bottom-up pattern matching algorithm that handles a wide subclass of Hoffmann and ODonnells Simple Patterns.
- Theoretical Mathematics
- Manufacturing and Industrial Engineering and Control of Production Systems