Tree template matching in unranked ordered trees

Michalis Christou, Tomáš Flouri, Costas S. Iliopoulos, Jan Janoušek, Bořivoj Melichar, Solon P. Pissis*, Jan Žd'Árek

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider the problem of tree template matching, a type of tree pattern matching, where the tree templates have some of their leaves denoted as "don't care", and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem for unranked ordered trees to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix bar notation, and then propose a table-driven algorithm to solve it. The proposed algorithm is divided into two phases: the preprocessing and the searching phase. The tree template is preprocessed once, and the searching phase can be applied to many subject trees, without the need of preprocessing the tree template again. Although we prove that the space required for preprocessing is exponential in the size of the tree template in the worst case, we show that for a specific class of tree templates, the space required is linear in the size of the tree template. The time for the searching phase is linear in the size of the subject tree in the worst case. Thus, the algorithm is asymptotically optimal when one needs to search for a given tree template, of constant to logarithmic size, in many subject trees.

Original languageEnglish
Pages (from-to)51-60
Number of pages10
JournalJournal of Discrete Algorithms
Volume20
DOIs
Publication statusPublished - 1 May 2013
Externally publishedYes

Keywords

  • Algorithms on strings
  • Tree pattern matching
  • Tree template matching

Fingerprint

Dive into the research topics of 'Tree template matching in unranked ordered trees'. Together they form a unique fingerprint.

Cite this