Bookmarks in Grammar-Compressed Strings

Patrick Hagge Cording, Pawel Gawrychowski, Oren Weimann

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

Abstract

We consider the problem of storing a grammar of size n compressing a string of size N, and a set of positions {i1, . . . , i } (bookmarks) such that any substring of length l crossing one of the positions can be decompressed in O(l) time. Our solution uses space O((n + b) max{1, log* n − log*( n/b + b/n)}). Existing solutions for the bookmarking problem either require more space or a super-constant “kick-off” time to start the decompression.
Original languageEnglish
Title of host publicationProceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016)
EditorsShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
PublisherSpringer
Publication date2016
Pages153-159
ISBN (Print)978-3-319-46048-2
ISBN (Electronic)978-3-319-46049-9
DOIs
Publication statusPublished - 2016
Event23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016) - Beppu, Japan
Duration: 18 Oct 201620 Oct 2016
Conference number: 23
https://sites.google.com/site/spire2016jp/

Conference

Conference23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016)
Number23
CountryJapan
CityBeppu
Period18/10/201620/10/2016
Internet address
SeriesLecture Notes in Computer Science
Volume9954
ISSN0302-9743

Cite this

Cording, P. H., Gawrychowski, P., & Weimann, O. (2016). Bookmarks in Grammar-Compressed Strings. In S. Inenaga, K. Sadakane, & T. Sakai (Eds.), Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016) (pp. 153-159). Springer. Lecture Notes in Computer Science, Vol.. 9954 https://doi.org/10.1007/978-3-319-46049-9_15