Mostrar o rexistro simple do ítem
Grammar compressed sequences with rank/select support
dc.contributor.author | Ordóñez, Alberto | |
dc.contributor.author | Navarro, Gonzalo | |
dc.contributor.author | Brisaboa, Nieves R. | |
dc.date.accessioned | 2017-02-27T17:16:43Z | |
dc.date.issued | 2016-10-14 | |
dc.identifier.citation | Alberto Ordóñez, Gonzalo Navarro, Nieves R. Brisaboa, Grammar compressed sequences with rank/select support, Journal of Discrete Algorithms, Available online 14 October 2016, ISSN 1570-8667, http://dx.doi.org/10.1016/j.jda.2016.10.001. | es_ES |
dc.identifier.issn | 1570-8667 | |
dc.identifier.issn | 1570-8675 | |
dc.identifier.uri | http://hdl.handle.net/2183/18191 | |
dc.description | An early partial version of this paper appeared in Proc. SPIRE 2014: G. Navarro, A. Ordóñez Grammar compressed sequences with rank/select support, Proc. 21st International Symposium on String Processing and Information Retrieval, LNCS, SPIRE, vol. 8799 (2014), pp. 31–44 | es_ES |
dc.description | The final publication is available at Springer via http://dx.doi.org/10.1016/j.jda.2016.10.001 | es_ES |
dc.description.abstract | [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. | es_ES |
dc.description.sponsorship | Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 140796 | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; 00645663/ITC-20133062 | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; TIN2009-14560-C03-02 | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; TIN2010-21246-C02-01 | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; TIN2013-46238-C4-3-R | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; TIN2013-47090-C3-3-P | es_ES |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad; AP2010-6038 | es_ES |
dc.description.sponsorship | Xunta de Galicia; GRC2013/053 | es_ES |
dc.language.iso | eng | es_ES |
dc.publisher | Elsevier BV | es_ES |
dc.relation | info:eu-repo/grantAgreement/EC/H2020/690941 | |
dc.relation.uri | http://www.sciencedirect.com/science/article/pii/S157086671630034X?np=y&npKey=3f1c328b4e3e50d868dc16ee1923ba301c2a53b77745f7b638604b7fcfef3c9e | es_ES |
dc.rights | Atribución-NoComercial-SinDerivadas 3.0 España | es_ES |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/es/ | * |
dc.subject | Grammar compression | es_ES |
dc.subject | Repetitive sequences | es_ES |
dc.subject | Text indexing | es_ES |
dc.title | Grammar compressed sequences with rank/select support | es_ES |
dc.type | info:eu-repo/semantics/article | es_ES |
dc.rights.access | info:eu-repo/semantics/embargoedAccess | es_ES |
dc.date.embargoEndDate | 2018-10-14 | es_ES |
dc.date.embargoLift | 2018-10-14 | |
UDC.journalTitle | Journal of Discrete Algorithms | es_ES |
dc.identifier.doi | 10.1016/j.jda.2016.10.001 |
Ficheiros no ítem
Este ítem aparece na(s) seguinte(s) colección(s)
-
GI-LBD - Artigos [51]
-
OpenAIRE [357]