On modification of Boyer-Moore-horspool's algorithm for tree pattern matching in linearised trees
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F20%3A00341542" target="_blank" >RIV/68407700:21240/20:00341542 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.tcs.2020.04.027" target="_blank" >https://doi.org/10.1016/j.tcs.2020.04.027</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2020.04.027" target="_blank" >10.1016/j.tcs.2020.04.027</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On modification of Boyer-Moore-horspool's algorithm for tree pattern matching in linearised trees
Popis výsledku v původním jazyce
Tree pattern matching on ordered trees is an important problem in Computer Science. Ordered trees can be represented as strings with additional properties via various linearisations. We present a backward tree pattern matching algorithm for ordered trees for various linear representations of trees and tree patterns. The algorithm adaptations find all occurrences of a single given tree pattern which match an input tree regardless of the chosen linearisation. The algorithms preserve the properties and advantages of standard backward string pattern matching using Boyer-Moore-Horspool's bad character shift heuristics. The number of symbol comparisons in the backward tree pattern matching can be sublinear in the size of the input tree. As in the case of the string version of Boyer-Moore-Horspool's matching algorithm, the size of the bad character shift table used by the algorithm is linear in the size of the alphabet. We compare the algorithm adaptations with the algorithm using originally chosen linear representation and with the best performing previously existing algorithms based on (non-linearised) tree pattern matching using finite tree automata or stringpath matchers. We show that the presented backward tree pattern matching algorithms outperform the non-linearising ones for single pattern matching and they perform among themselves comparably. (C) 2020 Elsevier B.V. All rights reserved.
Název v anglickém jazyce
On modification of Boyer-Moore-horspool's algorithm for tree pattern matching in linearised trees
Popis výsledku anglicky
Tree pattern matching on ordered trees is an important problem in Computer Science. Ordered trees can be represented as strings with additional properties via various linearisations. We present a backward tree pattern matching algorithm for ordered trees for various linear representations of trees and tree patterns. The algorithm adaptations find all occurrences of a single given tree pattern which match an input tree regardless of the chosen linearisation. The algorithms preserve the properties and advantages of standard backward string pattern matching using Boyer-Moore-Horspool's bad character shift heuristics. The number of symbol comparisons in the backward tree pattern matching can be sublinear in the size of the input tree. As in the case of the string version of Boyer-Moore-Horspool's matching algorithm, the size of the bad character shift table used by the algorithm is linear in the size of the alphabet. We compare the algorithm adaptations with the algorithm using originally chosen linear representation and with the best performing previously existing algorithms based on (non-linearised) tree pattern matching using finite tree automata or stringpath matchers. We show that the presented backward tree pattern matching algorithms outperform the non-linearising ones for single pattern matching and they perform among themselves comparably. (C) 2020 Elsevier B.V. All rights reserved.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
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)
Ostatní
Rok uplatnění
2020
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ů
Údaje specifické pro druh výsledku
Název periodika
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
1879-2294
Svazek periodika
830
Číslo periodika v rámci svazku
August
Stát vydavatele periodika
GB - Spojené království Velké Británie a Severního Irska
Počet stran výsledku
31
Strana od-do
60-90
Kód UT WoS článku
000534685500004
EID výsledku v databázi Scopus
2-s2.0-85084422321