Show simple item record

Authordc.contributor.authorNavarro, Gonzalo 
Authordc.contributor.authorPrezza, Nicola 
Admission datedc.date.accessioned2019-05-31T15:34:01Z
Available datedc.date.available2019-05-31T15:34:01Z
Publication datedc.date.issued2019
Cita de ítemdc.identifier.citationTheoretical Computer Science 762 (2019) 41–50
Identifierdc.identifier.issn03043975
Identifierdc.identifier.other10.1016/j.tcs.2018.09.007
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/169701
Abstractdc.description.abstractThe rise of repetitive datasets has lately generated a lot of interest in compressed self-indexes based on dictionary compression, a rich and heterogeneous family of techniques that exploits text repetitions in different ways. For each such compression scheme, several different indexing solutions have been proposed in the last two decades. To date, the fastest indexes for repetitive texts are based on the run-length compressed Burrows-Wheeler transform (BWT) and on the Compact Directed Acyclic Word Graph (CDAWG). The most space-efficient indexes, on the other hand, are based on the Lempel-Ziv parsing and on grammar compression. Indexes for more universal schemes such as collage systems and macro schemes have not yet been proposed. Very recently, Kempa and Prezza [STOC 2018] showed that all dictionary compressors can be interpreted as approximation algorithms for the smallest string attractor, that is, a set of text positions capturing all distinct substrings. Starting from this observation, in this paper we develop the first universal compressed self-index, that is, the first indexing data structure based on string attractors, which can therefore be built on top of any dictionary-compressed text representation. Let gamma be the size of a string attractor for a text of length n. From known reductions, gamma can be chosen to be asymptotically equal to any repetitiveness measure: number of runs in the BWT, size of the CDAWG, number of Lempel-Ziv phrases, number of rules in a grammar or collage system, size of a macro scheme. Our index takes O(gamma lg(n/gamma)) words of space and supports locating the occ occurrences of any pattern of length m in O(mlgn + occlg(epsilon)n) time, for any constant epsilon > 0. This is, in particular, the first index for general macro schemes and collage systems. Our result shows that the relation between indexing and compression is much deeper than what was previously thought: the simple property standing at the core of all dictionary compressors is sufficient to support fast indexed queries.
Lenguagedc.language.isoen
Publisherdc.publisherElsevier
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
Sourcedc.sourceTheoretical Computer Science
Keywordsdc.subjectCompressed indexes
Keywordsdc.subjectRepetitive sequences
Keywordsdc.subjectString attractors
Títulodc.titleUniversal compressed text indexing
Document typedc.typeArtículo de revista
Catalogueruchile.catalogadorlaj
Indexationuchile.indexArtículo de publicación SCOPUS
uchile.cosechauchile.cosechaSI


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile