Access, Rank, and Select in Grammar-compressed Strings

Djamal Belazzougui, Patrick Hagge Cording, Simon J. Puglisi, Yasuo Tabei

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Given a string S of length N on a fixed alphabet of σ symbols, a grammar compressor produces a context-free grammar G of size n that generates S and only S. In this paper we describe data structures to support the following operations on a grammar-compressed string: access(S,i,j) (return substring S[i,j]), rank c (S,i) (return the number of occurrences of symbol c before position i in S), and select c (S,i) (return the position of the ith occurrence of c in S). Our main result for access is a method that requires \O(nlogN) bits of space and \O(logN+m/logσN) time to extract m = j − i + 1 consecutive symbols from S. Alternatively, we can achieve \O(logτN+m/logσN) query time using \O(nτlogτ(N/n)logN) bits of space, matching a lower bound stated by Verbin and Yu for strings where N is polynomially related to n when τ = log ε N. For rank and select we describe data structures of size \O(nσlogN) bits that support the two operations in \O(logN) time. We also extend our other structure to support both operations in \O(logτN) time using \O(nτσlogτ(N/n)logN) bits of space. When τ = log ε N the query time is O(logN/loglogN) and we provide a hardness result showing that significantly improving this would imply a major breakthrough on a hard graph-theoretical problem.
Original languageEnglish
Title of host publicationProceedings of the 23rd Annual European Symposium on Algorithms – ESA 2015
EditorsNikhil Bansal, Irene Finocchi
PublisherSpringer
Publication date2015
Pages142-154
ISBN (Print)978-3-662-48349-7
ISBN (Electronic) 978-3-662-48350-3
DOIs
Publication statusPublished - 2015
Event23rd European Symposium on Algorithms (ESA 2015) - Patras, Greece
Duration: 14 Sep 201516 Sep 2015
Conference number: 23
http://algo2015.upatras.gr/esa/

Conference

Conference23rd European Symposium on Algorithms (ESA 2015)
Number23
CountryGreece
CityPatras
Period14/09/201516/09/2015
Internet address
SeriesLecture Notes in Computer Science
Volume9294
ISSN0302-9743

Cite this

Belazzougui, D., Cording, P. H., Puglisi, S. J., & Tabei, Y. (2015). Access, Rank, and Select in Grammar-compressed Strings. In N. Bansal, & I. Finocchi (Eds.), Proceedings of the 23rd Annual European Symposium on Algorithms – ESA 2015 (pp. 142-154). Springer. Lecture Notes in Computer Science, Vol.. 9294 https://doi.org/10.1007/978-3-662-48350-3_13