Introducing Cuts Into a Top-Down Process for Checking Tree Inclusion

摘要

By the ordered tree inclusion we will check whether a pattern tree P can be included in a target tree T, where the order of siblings in both P and T matters. This problem has many applications in practice, such as retrieval of documents, data mining, and RNA structure matching. In this paper, we propose an efficient algorithm for this problem. Its time complexity is bounded by O(vertical bar T vertical bar.min{h(P), vertical bar leaves(P)vertical bar}, with O(vertical bar T vertical bar + vertical bar P vertical bar) space being used, where h(P) (h(T)) represents the height of P (resp., T) and leaves (P) stands for the set of the leaves of P. Up to now the best algorithm for this problem needs Theta(vertical bar T vertical bar.vertical bar leaves(P)vertical bar) time and O(vertical bar P vertical bar + vertical bar T vertical bar) space. Extensive experiments have been done, which show that the new algorithm can perform much better than the existing ones in practice.