Artículo de revista
Fast compressed self-indexes with deterministic linear-Time construction
Fecha
2017Registro en:
Leibniz International Proceedings in Informatics, LIPIcs, Volumen 92, 2017
18688969
10.4230/LIPIcs.ISAAC.2017.57
Autor
Munro, J. Ian
Navarro, Gonzalo
Nekrich, Yakov
Institución
Resumen
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.