We study the problem of supporting queries on a string S of length n within a space bounded by the size γ of a string attractor for S. In the paper introducing string attractors it was shown that random access on S can be supported in optimal O(log(n/γ)/ log log n) time within O (γ polylog n) space. In this paper, we extend this result to rank and select queries and provide lower bounds matching our upper bounds on alphabets of polylogarithmic size. Our solutions are given in the form of a space-time trade-off that is more general than the one previously known for grammars and that improves existing bounds on LZ77-compressed text by a log log n time-factor in select queries. We also provide matching lower and upper bounds for partial sum and predecessor queries within attractor-bounded space, and extend our lower bounds to encompass navigation of dictionary-compressed tree representations.

Optimal rank and select queries on dictionary-compressed text / Prezza, N.. - (2019), pp. 1-12. ((Intervento presentato al convegno 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019 tenutosi a Pisa, Italia nel 18-20 giugno 2019 [10.4230/LIPIcs.CPM.2019.4].

Optimal rank and select queries on dictionary-compressed text

Prezza N.
2019

Abstract

We study the problem of supporting queries on a string S of length n within a space bounded by the size γ of a string attractor for S. In the paper introducing string attractors it was shown that random access on S can be supported in optimal O(log(n/γ)/ log log n) time within O (γ polylog n) space. In this paper, we extend this result to rank and select queries and provide lower bounds matching our upper bounds on alphabets of polylogarithmic size. Our solutions are given in the form of a space-time trade-off that is more general than the one previously known for grammars and that improves existing bounds on LZ77-compressed text by a log log n time-factor in select queries. We also provide matching lower and upper bounds for partial sum and predecessor queries within attractor-bounded space, and extend our lower bounds to encompass navigation of dictionary-compressed tree representations.
978-3-95977-103-0
Dictionary compression; Rank; Select; String attractors
Optimal rank and select queries on dictionary-compressed text / Prezza, N.. - (2019), pp. 1-12. ((Intervento presentato al convegno 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019 tenutosi a Pisa, Italia nel 18-20 giugno 2019 [10.4230/LIPIcs.CPM.2019.4].
File in questo prodotto:
File Dimensione Formato  
rank-select.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 469.78 kB
Formato Adobe PDF
469.78 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/194123
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact