License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2019.4
URN: urn:nbn:de:0030-drops-104756
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10475/
Go to the corresponding LIPIcs Volume Portal

Prezza, Nicola

Optimal Rank and Select Queries on Dictionary-Compressed Text

pdf-format:
LIPIcs-CPM-2019-4.pdf (0.5 MB)

Abstract

We study the problem of supporting queries on a string S of length n within a space bounded by the size gamma 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/gamma)/log log n) time within O(gamma 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.

BibTeX - Entry

@InProceedings{prezza:LIPIcs:2019:10475,
  author =	{Nicola Prezza},
  title =	{{Optimal Rank and Select Queries on Dictionary-Compressed Text}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Nadia Pisanti and Solon P. Pissis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10475},
  URN =		{urn:nbn:de:0030-drops-104756},
  doi =		{10.4230/LIPIcs.CPM.2019.4},
  annote =	{Keywords: Rank, Select, Dictionary compression, String Attractors}
}

Keywords: Rank, Select, Dictionary compression, String Attractors
Collection: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Issue Date: 2019
Date of publication: 06.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI