The following tree pattern matching problem is considered: Given two unordered labeled trees P and T, find all occurrences of P in T. Here P and T are called a pattern tree and a target tree, respectively. We first introduce a new problem called the pseudo-tree pattern matching problem. Then we show two efficient bit-parallel algorithms for the pseudo-tree pattern matching problem. One runs in O(L{sub}p·n·l·[h/W]) time and O(n·l·[h/W]) space, and another one runs in O((L{sub}p·n+h·2{sup}l)·[(h·l)/W]) time and O((n+h·2{sup}l)·[(h·l)/W]) space, where n is the number of nodes in T, h and l are the height of P and the number of leaves of P, respectively, and W is the length of a computer-word. The parameter L{sub}p, called a recursive level of P, is defined to be the number of occurrences of the same label on a path from the root to a leaf. Hence we have L{sub}p≤h. Finally, we give an algorithm to extract all occurrences from pseud-occurrences in O(n·L{sub}p·l{sup}(3/2)) time and O(n·L{sub}p·l) space.
展开▼
