2011/09/19 by Gagie, Travis, Gawrychowski, Paweł, Kärkkäinen, Juha +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1109.3954
To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on grammars. In this paper we show how, given a straight-line program with r rules for a string (S [1..n]) whose LZ77 parse consists of z phrases, we can store a self-index for S in \Ohr + z log log n space such that, given a pattern (P [1..m]), we can list the \occ occurrences of P in S in \Ohm2 + \occ log log n time. If the straight-line program is balanced and we accept a small probability of building a faulty index, then we can reduce the \Ohm2 term to \Ohm log m. All previous self-indexes are larger or slower in the worst case.