Bit-Parallel Tree Pattern Matching Algorithms for Trees with Restricted Labels

摘要

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. In general, it is more difficult to design an efficient algorithm for unordered trees than for ordered trees. In this paper, we will consider a pattern tree P with non-recursive labels. Then we first introduce a new problem called the pseudo-tree pattern matching problem, and show an efficient bit-parallel algorithm which finds out all pseud-occurrences of P in T. Our algorithm runs in linear time if a pattern tree P is small. Furthermore, we extend our algorithms to a tree pattern matching algorithm.