Fast compressed self-indexes with deterministic linear-Time construction
Author
dc.contributor.author
Munro, J. Ian
Author
dc.contributor.author
Navarro, Gonzalo
Author
dc.contributor.author
Nekrich, Yakov
Admission date
dc.date.accessioned
2019-05-29T13:41:23Z
Available date
dc.date.available
2019-05-29T13:41:23Z
Publication date
dc.date.issued
2017
Cita de ítem
dc.identifier.citation
Leibniz International Proceedings in Informatics, LIPIcs, Volumen 92, 2017
Identifier
dc.identifier.issn
18688969
Identifier
dc.identifier.other
10.4230/LIPIcs.ISAAC.2017.57
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/169129
Abstract
dc.description.abstract
We introduce a compressed suffix array representation that, on a textTof lengthnover analphabet of sizeσ, can be built inO(n)deterministic time, withinO(nlogσ)bits of workingspace, and counts the number of occurrences of any patternPinTin timeO(|P|+ log logwσ)ona RAM machine ofw= Ω(logn)-bit words. This new index outperforms all the other compressedindexes that can be built in linear deterministic time, and some others. The only faster indexescan be built in linear time only in expectation, or requireΘ(nlogn)bits. We also show that, byusingO(nlogσ)bits, we can build in linear time an index that counts in timeO(|P|/logσn+logn(log logn)2), which is RAM-optimal forw= Θ(logn)and sufficiently long patterns.
Lenguage
dc.language.iso
en
Publisher
dc.publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing