Abstract
We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are computed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley, Reading (2006)
Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett. 12(5), 244–250 (1981)
Downey, P.J., Sethi, R., Tarjan, R.E.: Variations on the common subexpression problem. J. ACM 27, 758–771 (1980)
Dubiner, M., Galil, Z., Magen, E.: Faster tree pattern matching. J. ACM 41, 205–213 (1994)
Flajolet, P., Sipala, P., Steyaert, J.M.: Analytic variations on the common subexpression problem. In: Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming, pp. 220–234. Springer-Verlag New York, Inc., New York (1990)
Flouri, T., Janoušek, J., Melichar, B.: Subtree matching by pushdown automata. Computer Science and Information Systems/ComSIS 7(2), 331–357 (2010)
Grossi, R.: On finding common subtrees. Theor. Comput. Sci. 108(2), 345–356 (1993)
Hoffmann, C.M., O’Donnell, M.J.: Pattern matching in trees. J. ACM 29, 68–95 (1982)
Janousek, J.: String suffix automata and subtree pushdown automata. In: Holub, J., Zdárek, J. (eds.) Stringology. pp. 160–172. Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague (2009)
Karp, R.M., Miller, R.E., Rosenberg, A.L.: Rapid identification of repeated patterns in strings, trees and arrays. In: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, STOC 1972, pp. 125–136. ACM, New York (1972)
Kosaraju, S.R.: Efficient tree pattern matching. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 178–183. IEEE Computer Society, Washington, DC (1989)
Kuboyama, T.: Matching and Learning in Trees. Ph.D. thesis, University of Tokyo (2007)
Mauri, G., Pavesi, G.: Algorithms for pattern matching and discovery in rna secondary structure. Theor. Comput. Sci. 335, 29–51 (2005)
Melichar, B.: Arbology: Trees and pushdown automata. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 32–49. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Christou, M. et al. (2011). Computing All Subtree Repeats in Ordered Ranked Trees. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds) String Processing and Information Retrieval. SPIRE 2011. Lecture Notes in Computer Science, vol 7024. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24583-1_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-24583-1_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24582-4
Online ISBN: 978-3-642-24583-1
eBook Packages: Computer ScienceComputer Science (R0)