A Full and Linear Index of a Tree for Tree Patterns

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F14%3A00219874" target="_blank" >RIV/68407700:21240/14:00219874 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-09704-6_18" target="_blank" >http://dx.doi.org/10.1007/978-3-319-09704-6_18</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-09704-6_18" target="_blank" >10.1007/978-3-319-09704-6_18</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Full and Linear Index of a Tree for Tree Patterns

Popis výsledku v původním jazyce

A new and simple method of indexing a tree for tree patterns is presented. A tree pattern is a tree whose leaves can be labelled by a special symbol S, which serves as a placeholder for any subtree. Given a subject tree T with n nodes, the tree is preprocessed and an index, which consists of a standard string compact suffix automaton and a subtree jump table, is constructed. The number of distinct tree patterns which match the tree is O(2n), and the size of the index is O(n). The searching phase uses the index, reads an input tree pattern P of size m and computes the list of positions of all occurrences of the pattern P in the tree T . For an input tree pattern P in linear prefix notation pref(P) = P1SP2S . . . SPk, k 1, the searching is performed in time O(m+k Pi=1 |occ(Pi)|)), where occ(Pi) is the set of all occurrences of Pi in pref(T ).

Název v anglickém jazyce

A Full and Linear Index of a Tree for Tree Patterns

Popis výsledku anglicky

A new and simple method of indexing a tree for tree patterns is presented. A tree pattern is a tree whose leaves can be labelled by a special symbol S, which serves as a placeholder for any subtree. Given a subject tree T with n nodes, the tree is preprocessed and an index, which consists of a standard string compact suffix automaton and a subtree jump table, is constructed. The number of distinct tree patterns which match the tree is O(2n), and the size of the index is O(n). The searching phase uses the index, reads an input tree pattern P of size m and computes the list of positions of all occurrences of the pattern P in the tree T . For an input tree pattern P in linear prefix notation pref(P) = P1SP2S . . . SPk, k 1, the searching is performed in time O(m+k Pi=1 |occ(Pi)|)), where occ(Pi) is the set of all occurrences of Pi in pref(T ).

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2014

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 statě ve sborníku

DCFS 2014: Proceedings of the 16th International Workshop on Descriptional Complexity of Formal Systems

ISBN

978-3-319-09703-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

198-209

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Turku

Datum konání akce

5. 8. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000343868700018