Yangjun Chen (University of Winnipeg, Canada)

DOI: 10.4018/978-1-59904-845-1.ch080

Chapter Preview

TopThe 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].

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).

Search this Book:

Reset