A Simple Tree Pattern-Matching Algorithm

Abstract

Tree pattern matching occurs as a crucial step in a number of programming tasks. We propose a new al- gorithm to solve the tree pattern-matching problem. The algorithm may be viewed as an extension of the Knuth- Morris-Pratt string-matching algorithm to the tree pattern- matching problem. In the new algorithm, the times of each node in the subject tree needs to be traversed is bounded by their level. Therefore, the time complexity of the simple tree pattern-matching is bounded by O(n log n), where n is the number of nodes in the subject tree. The worst case occurs when the frequency of the same content of the pat- tern's root in the subject tree is high. But we need an extra preprocessing time of the pattern. The time complexity of the pattern preprocessing is bounded by O(mlogm), where m is the number of nodes in the pattern. The worst case occurs similarly when the frequency of the same content of the root in the pattern is high. By using indirection, the space complexity will be down to O(n + m).