On-line suffix tree construction with reduced branching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10100613" target="_blank" >RIV/00216208:11320/12:10100613 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S1570866712000159" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1570866712000159</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

On-line suffix tree construction with reduced branching

Popis výsledku v původním jazyce

Classical suffix tree construction algorithms by McCreight and Ukkonen spend most of the time looking up the right branch to follow from the current node. However, not all these slow branching operations are necessary. A significant portion of them is used for implicit suffix link simulation and can be avoided by replacing the traditional top-down descent with bottom-up climbing. We describe the bottom-up approach and analyze its costs and benefits. An experimental evaluation on two standard data corpora shows that bottom-up climbing removes forty to sixty six percent of branching operations and consequently saves twenty one to thirty two percent of construction time. However, a theoretical analysis of the worst-case behavior reveals that the time complexity of the bottom-up approach is superlinear. This is remedied by a combination of both approaches that removes nearly as many branching operations as the bottom-up climb, but still runs in linear time like the top-down descent.

Název v anglickém jazyce

On-line suffix tree construction with reduced branching

Popis výsledku anglicky

Classical suffix tree construction algorithms by McCreight and Ukkonen spend most of the time looking up the right branch to follow from the current node. However, not all these slow branching operations are necessary. A significant portion of them is used for implicit suffix link simulation and can be avoided by replacing the traditional top-down descent with bottom-up climbing. We describe the bottom-up approach and analyze its costs and benefits. An experimental evaluation on two standard data corpora shows that bottom-up climbing removes forty to sixty six percent of branching operations and consequently saves twenty one to thirty two percent of construction time. However, a theoretical analysis of the worst-case behavior reveals that the time complexity of the bottom-up approach is superlinear. This is remedied by a combination of both approaches that removes nearly as many branching operations as the bottom-up climb, but still runs in linear time like the top-down descent.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

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

Journal of Discrete Algorithms

ISSN

1570-8667

e-ISSN

—

Svazek periodika

12

Číslo periodika v rámci svazku

April

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

48-60

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—