Backward Linearised Tree Pattern Matching

摘要: We present a new backward tree pattern matching algorithm for ordered trees. The finds all occurrences of single given which match an input tree. It makes use linearisations both the and preserves properties advantages standard string approaches. number symbol comparisons in can be sublinear size As case matching, bad character shift table used by is linear alphabet. compare with best performing previously existing algorithms based on (non-linearised) using finite automata or stringpath matchers show that it outperforms these matching.