Grammar compressed sequences with rank/select support
Author
dc.contributor.author
Ordonez, Alberto
Author
dc.contributor.author
Navarro, Gonzalo
Author
dc.contributor.author
Brisaboa, Nieves R.
Admission date
dc.date.accessioned
2018-05-22T20:10:42Z
Available date
dc.date.available
2018-05-22T20:10:42Z
Publication date
dc.date.issued
2017
Cita de ítem
dc.identifier.citation
Journal of Discrete Algorithms 43(2017)54–71
es_ES
Identifier
dc.identifier.other
10.1016/j.jda.2016.10.001
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/148037
Abstract
dc.description.abstract
Sequence representations supporting not only direct access to their symbols, but also rank/select operations, are a fundamental building block in many compressed data structures. Several recent applications need to represent highly repetitive sequences, and classical statistical compression proves ineffective. We introduce, instead, grammar-based representations for repetitive sequences, which use up to 6% of the space needed by statistically compressed representations, and support direct access and rank/select operations within tens of microseconds. We demonstrate the impact of our structures in text indexing applications. (C) 2016 Elsevier B.V. All rights reserved.
es_ES
Patrocinador
dc.description.sponsorship
European Union, 690941 / FONDECYT, Chile, 1-140796 /
CDTI EXP, 000645663/ITC-20133062 /
Xunta de Galicia (PGE), GRC2013/053 / Xunta de Galicia (FEDER), GRC2013/053 /
MICINN (PGE), TIN2009-14560-C03-02, TIN2010-21246-C02-01, TIN2013-46238-C4-3-R, TIN2013-47090-C3-3-P,
AP2010-6038 / MICINN (FEDER), TIN2009-14560-C03-02, TIN2010-21246-C02-01,
TIN2013-46238-C4-3-R,
TIN2013-47090-C3-3-P,
AP2010-6038