Fast compressed self-indexes with deterministic linear-Time construction

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.