Forward linearised tree pattern matching using tree pattern border array

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00375772" target="_blank" >RIV/68407700:21240/24:00375772 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.dam.2024.03.014" target="_blank" >https://doi.org/10.1016/j.dam.2024.03.014</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2024.03.014" target="_blank" >10.1016/j.dam.2024.03.014</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Forward linearised tree pattern matching using tree pattern border array

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Forward linearised tree pattern matching using tree pattern border array

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Svazek periodika

352

Číslo periodika v rámci svazku

July

Stát vydavatele periodika

AT - Rakouská republika

Počet stran výsledku

11

Strana od-do

33-43

Kód UT WoS článku

001223885500001

EID výsledku v databázi Scopus

2-s2.0-85189432321