On modification of Boyer-Moore-horspool's algorithm for tree pattern matching in linearised trees
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On modification of Boyer-Moore-horspool's algorithm for tree pattern matching in linearised trees
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
1879-2294
Volume of the periodical
830
Issue of the periodical within the volume
August
Country of publishing house
GB - UNITED KINGDOM
Number of pages
31
Pages from-to
60-90
UT code for WoS article
000534685500004
EID of the result in the Scopus database
2-s2.0-85084422321