The tree matching problem is to find all occurrences of a pattern tree P in a target tree T. A pattern tree P matches a target tree T at node v if there exists a one-to-one map from the nodes of P into the nodes of T such that: (1) the root of P maps to v, (2) if x maps to y, then x and y have the same label, i.e., label(x) = label(y), and (3) if x maps to y and x is not a leaf, then the ith child of x maps to the ith child of y. (In particular, the outdegree of y is no less than the outdegree of x.)
Published in Chapter:
A New Algorithm for Subset Matching Problem Based on Set-String Transformation
Yangjun Chen (University of Winnipeg, Canada)
Copyright: © 2009
|Pages: 9
DOI: 10.4018/978-1-59904-845-1.ch080
Abstract
In computer engineering, a number of programming tasks involve a special problem, the so-called tree matching problem (Cole & Hariharan, 1997), as a crucial step, such as the design of interpreters for nonprocedural programming languages, automatic implementation of abstract data types, code optimization in compilers, symbolic computation, context searching in structure editors and automatic theorem proving. Recently, it has been shown that this problem can be transformed in linear time to another problem, the so called subset matching problem (Cole & Hariharan, 2002, 2003), which is to find all occurrences of a pattern string p of length m in a text string t of length n, where each pattern and text position is a set of characters drawn from some alphabet S. The pattern is said to occur at text position i if the set p[j] is a subset of the set t[i + j - 1], for all j (1 = j = m). This is a generalization of the ordinary string matching and is of interest since an efficient algorithm for this problem implies an efficient solution to the tree matching problem. In addition, as shown in (Indyk, 1997), this problem can also be used to solve general string matching and counting matching (Muthukrishan, 1997; Muthukrishan & Palem, 1994), and enables us to design efficient algorithms for several geometric pattern matching problems. In this article, we propose a new algorithm on this issue, which needs only O(n + m) time in the case that the size of S is small and O(n + m·n0.5) time on average in general cases.