Prague Stringology Conference 2020
Jan Trávníček, Robin Obůrka, Tomáš Pecka and Jan Janoušek
Forward Linearised Tree Pattern Matching Using Tree Pattern Border Array
| Abstract: |
| We define a tree pattern border array as a property of linearised trees analogous to border arrays from the string domain. We use it to define a new forward tree pattern matching algorithm for ordered trees, which finds all occurrences of a single given linearised tree pattern in a linearised input tree. As with the classical Morris-Pratt algorithm, the tree pattern border array is used to determine shift lengths in the searching phase of the tree pattern matching algorithm. We compare the new algorithm with the best performing previously existing algorithms based on backward linearised tree pattern matching algorithms, (non-)linearised tree pattern matching algorithms using finite tree automata or stringpath matchers. We show that the presented algorithm outperforms these for single tree pattern matching. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |