Abstract
The tree pattern matching problem is, given two labeled trees P and T, respectively called pattern tree and target tree, to find all occurrences of P within T. Many studies have been undertaken on this problem for both the cases of ordered and unordered trees. To realize flexible matching, a kind of variable-length-don’t-care’s (VLDC’s) have been introduced. In particular, the path-VLDC’s appear in XPath, a language for addressing parts of an XML document. In this paper, we introduce horizontal VLDC’s, each matches a sequence of trees whose root nodes are consecutive siblings in ordered trees. We address the tree pattern matching problem for patterns with horizontal VLDC’s. In our setting, the target tree is given as a tagged sequence such as XML data stream. We present an algorithm that solves the problem in O(mn) time using O(mh) space, where m and n are the sizes of P and T, respectively, and h is the height of T. We adopt the bit-parallel technique to obtain a practically fast algorithm.
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
Amoth, T.R., Cull, P., Tadepalli, P.: Exact learning of tree patterns from queries and counterexamples. In: Proceedings of COLT 1998, pp. 175–186 (1998)
Angluin, D.: Finding patterns common to a set of strings. J. Comput. Sys. Sci. 21, 46–62 (1980)
Chauve, C.: Tree pattern matching with a more general notion of occurrence of the pattern. Inform. Process. Lett. 82, 197–201 (2002)
Cole, R., Hariharan, R.: Tree pattern matching and subset matching in randomized O(n log3 n)-time. In: STOC 1997, pp. 66–75 (1997)
Cole, R., Hariharan, R., Indyk, P.: Tree pattern matching and subset matching in deterministic O(n logn)-time. In: SODA 1999, pp. 245–254 (1999)
Dubliner, M., Galil, Z., Magen, E.: Faster tree pattern matching. J. ACM 41(2), 205–213 (1994)
Jan Bex, F.N.G., Maneth, S.: A formal model for an expressive fragment of xslt. In: Palamidessi, C., Moniz Pereira, L., Lloyd, J.W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Sagiv, Y., Stuckey, P.J. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 1137–1151. Springer, Heidelberg (2000)
Hoffmann, C.M., O’Donnell, M.J.: Pattern matching in trees. J. ACM 29(1), 68–95 (1982)
Kilpeläinen, P.: Tree Matching Problems with Applications to Structured Text Databases. PhD thesis, Dept. of Computer Science, University of Helsinki (1992)
Kilpeläinen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM J. Comput. 24(2), 340–356 (1995)
Kosaraju, S.R.: Efficient tree pattern matching. In: FOCS 1989, pp. 178–183. IEEE Comput. Soc. Press, Los Alamitos (1989)
Luccio, F., Pagli, L.: An efficient algorithm for some tree matching problems. Inform. Process. Lett. 39(1), 51–57 (1991)
Luccio, F., Pagli, L.: Approximate matching for two families of trees. Information and Computation 123(1), 111–120 (1995)
Murata, M.: Transformation of documents and schemas by patterns and contextual conditions. In: Nicholas, C., Wood, D. (eds.) PODDP 1996 and PODP 1996. LNCS, vol. 1293, pp. 153–169. Springer, Heidelberg (1997)
Murata, M.: Data model for document transformation and assembly (extended abstract), pp. 140–152 (1998)
Navarro, G., Raffinot, M.: Flexible pattern matching in strings: Practical on-line search algorithms for texts and biological sequences. Cambridge University Press, Cambridge (2002)
Nivat, M., Ait-Kaci, H.: On recognizable sets and tree automata. Resolution of Equations in Algebraic Structres (1989)
Shoudai, T., Uchida, T., Miyahara, T.: Polynomial time algorithms for finding unordered tree patterns with internal variables. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 335–346. Springer, Heidelberg (2001)
Takahashi, M.: Generalizations of regular sets and their application to a study of context-free languages. Information and Control 27, 1–36 (1975)
Zhang, K., Shasha, D., Wang, J.T.L.: Approximate tree matching in the presence of variable length don’t cares. J. Algorithms 16(1), 33–66 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tsuji, H., Ishino, A., Takeda, M. (2005). A Bit-Parallel Tree Matching Algorithm for Patterns with Horizontal VLDC’s. In: Consens, M., Navarro, G. (eds) String Processing and Information Retrieval. SPIRE 2005. Lecture Notes in Computer Science, vol 3772. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11575832_43
Download citation
DOI: https://doi.org/10.1007/11575832_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29740-6
Online ISBN: 978-3-540-32241-2
eBook Packages: Computer ScienceComputer Science (R0)