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.
TopBackground
The subset matching problem was defined in Cole and Hariharan (1997) and shown also in Cole and Hariharan (1997) and its improved version (Cole and Hariharan, 2003) that the well-known tree pattern matching problem can be linearly reduced to this problem. Formally, the text t is a string of length n and the pattern p is a string of length m. Each text position t[i] and each pattern position p[j] is a set of characters (not a single character), taken from a certain alphabet Σ. Strings, in which each location is a set of characters, will be called set-strings to distinguish them from ordinary strings. Pattern p is said to match text t at position i if p[j] ⊆ t[i + j - 1], for all j (1 ≤ j ≤ m). As an example, consider the set-strings t and p shown in Figure 1.
Figure 1(a) shows a matching case, by which we have p[j] ⊆ t[i + j - 1] for i = 1, and j = 1, 2, 3, while Figure 1(b) illustrates an unmatching case since for i = 2 we have p[2] ⊄ t[i + 2 - 1].
Key Terms in this Chapter
Subset Matching: The subset matching problem 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 problem.
Suffix Tree: A suffix tree is a trie over all the suffices of a string.
Set-String Transformation: The set-string transformation for a given subset matching is to transform the text set-string t and the pattern set-string p into two different strings t’ and p’ so that p has matches in t if and only if p’ has matches in t’.
Tree Matching: 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.)
Tree: A tree is a graph, in which each node may have more one child nodes, but only one parent.
Trie: A trie for a set of strings is a type of digit search tree over a finite alphabet S. In the trie, each edge represnts a symbol from S, and sibling edges must represent distinct symbols. In addition, each path from the root to a leaf node forms a prefix of a string, which differs the string from the others.
String Matching: A string matching problem is to find all the occurrences of a pattern string (a sequence of characters) in a text string (another sequence of characters).