BuST-Bundled Suffix Trees

We introduce a data structure, the Bundled Suffix Tree (BuST), that is a generalization of a Suffix Tree (ST). To build a BuST we use an alphabet Σ together with a non-transitive relation ≈ among its letters. Following the path of a substring β within a BuST, constructed over a text α of lengt...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bortolussi, Luca, Fabris, Franceso, Policriti, Alberto
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2006
Materias:
Ciencias Informáticas
data structure
linear time
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/24377
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-24377
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
data structure
linear time
spellingShingle Ciencias Informáticas
data structure
linear time
Bortolussi, Luca
Fabris, Franceso
Policriti, Alberto
BuST-Bundled Suffix Trees
topic_facet Ciencias Informáticas
data structure
linear time
description We introduce a data structure, the Bundled Suffix Tree (BuST), that is a generalization of a Suffix Tree (ST). To build a BuST we use an alphabet Σ together with a non-transitive relation ≈ among its letters. Following the path of a substring β within a BuST, constructed over a text α of length n, not only the positions of the exact occurrences of β in α are found (as in a ST), but also the positions of all the substrings β<sub> 1</sub> , β <sub>2</sub> , β<sub> 3</sub> , . . . that are related with β via the relation ≈ among the characters of Σ , for example strings at a certain ”distance” from β . A BuST contains O(n<sup>1+δ</sup> ) additional nodes (δ < 1) in probability, and is constructed in O(n<sup>1+δ</sup> ) steps. In the worst case it contains O(n<sup>2</sup>) nodes.
format Objeto de conferencia
Objeto de conferencia
author Bortolussi, Luca
Fabris, Franceso
Policriti, Alberto
author_facet Bortolussi, Luca
Fabris, Franceso
Policriti, Alberto
author_sort Bortolussi, Luca
title BuST-Bundled Suffix Trees
title_short BuST-Bundled Suffix Trees
title_full BuST-Bundled Suffix Trees
title_fullStr BuST-Bundled Suffix Trees
title_full_unstemmed BuST-Bundled Suffix Trees
title_sort bust-bundled suffix trees
publishDate 2006
url http://sedici.unlp.edu.ar/handle/10915/24377
work_keys_str_mv AT bortolussiluca bustbundledsuffixtrees
AT fabrisfranceso bustbundledsuffixtrees
AT policritialberto bustbundledsuffixtrees
bdutipo_str Repositorios
_version_ 1764820467046154241

Ejemplares similares