Forward linearised tree pattern matching using tree pattern border array

We define a tree pattern border array as a property of linearised trees analogous to border arrays from the string domain. We consider tree patterns with node wildcards and subtree wildcards. Then we use the tree pattern border array in a new forward tree pattern matching algorithm for ordered ranke...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2024-07, Vol.352, p.33-43
Main Authors: Trávníček, Jan, Pecka, Tomáš, Obůrka, Robin, Janoušek, Jan
Format: Article
Language:English
Subjects:
Border array
Morris–Pratt algorithm
Tree linearisation
Tree pattern matching
Tree processing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We define a tree pattern border array as a property of linearised trees analogous to border arrays from the string domain. We consider tree patterns with node wildcards and subtree wildcards. Then we use the tree pattern border array in a new forward tree pattern matching algorithm for ordered ranked trees. The algorithm finds all occurrences of a single linearised tree pattern in a linearised input tree. As with the classical Morris–Pratt algorithm for searching in strings, the tree pattern border array is used to determine shift lengths in the searching phase of the tree pattern matching algorithm. We compare this 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 our new algorithm outperforms other tree pattern matching algorithms in single tree pattern matching.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2024.03.014