Bookmarks in Grammar-Compressed Strings

Patrick Hagge Cording; Pawel Gawrychowski; Oren Weimann

doi:10.1007/978-3-319-46049-9_15

Bookmarks in Grammar-Compressed Strings

Patrick Hagge Cording, Pawel Gawrychowski, Oren Weimann

Department of Applied Mathematics and Computer Science

University of Haifa

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016)
Editors	Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Publisher	Springer
Publication date	2016
Pages	153-159
ISBN (Print)	978-3-319-46048-2
ISBN (Electronic)	978-3-319-46049-9
DOIs	https://doi.org/10.1007/978-3-319-46049-9_15
Publication status	Published - 2016
Event	23rd International Symposium on String Processing and Information Retrieval - Beppu, Japan Duration: 18 Oct 2016 → 20 Oct 2016 Conference number: 23 https://sites.google.com/site/spire2016jp/

Conference

Conference	23rd International Symposium on String Processing and Information Retrieval
Number	23
Country/Territory	Japan
City	Beppu
Period	18/10/2016 → 20/10/2016
Internet address	https://sites.google.com/site/spire2016jp/

Series	Lecture Notes in Computer Science
Volume	9954
ISSN	0302-9743

Access to Document

10.1007/978-3-319-46049-9_15

OpenUrl availability

Full text

Cite this

@inproceedings{4cd13e0e17b54a2c90da2a58aa07ab43,

title = "Bookmarks in Grammar-Compressed Strings",

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.",

author = "Cording, {Patrick Hagge} and Pawel Gawrychowski and Oren Weimann",

year = "2016",

doi = "10.1007/978-3-319-46049-9_15",

language = "English",

isbn = "978-3-319-46048-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "153--159",

editor = "Inenaga, {Shunsuke } and Sadakane, {Kunihiko } and Sakai, {Tetsuya }",

booktitle = "Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016)",

note = "23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 ; Conference date: 18-10-2016 Through 20-10-2016",

url = "https://sites.google.com/site/spire2016jp/",

}

Cording, PH, 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). Springer, Lecture Notes in Computer Science, vol. 9954, pp. 153-159, 23rd International Symposium on String Processing and Information Retrieval, Beppu, Japan, 18/10/2016. https://doi.org/10.1007/978-3-319-46049-9_15

Bookmarks in Grammar-Compressed Strings. / Cording, Patrick Hagge; Gawrychowski, Pawel; Weimann, Oren.
Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016). ed. / Shunsuke Inenaga; Kunihiko Sadakane; Tetsuya Sakai. Springer, 2016. p. 153-159 (Lecture Notes in Computer Science, Vol. 9954).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Bookmarks in Grammar-Compressed Strings

AU - Cording, Patrick Hagge

AU - Gawrychowski, Pawel

AU - Weimann, Oren

N1 - Conference code: 23

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-46049-9_15

DO - 10.1007/978-3-319-46049-9_15

M3 - Article in proceedings

SN - 978-3-319-46048-2

T3 - Lecture Notes in Computer Science

SP - 153

EP - 159

BT - Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016)

A2 - Inenaga, Shunsuke

A2 - Sadakane, Kunihiko

A2 - Sakai, Tetsuya

PB - Springer

T2 - 23rd International Symposium on String Processing and Information Retrieval

Y2 - 18 October 2016 through 20 October 2016

ER -

Bookmarks in Grammar-Compressed Strings

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this