On two LZ78-style grammars: Compression bounds and compressed-space computation

Golnaz Badkobeh; Travis Gagie; Shunsuke Inenaga; Tomasz Kociumaka; Dmitry Kosolobov; Simon J. Puglisi

doi:10.1007/978-3-319-67428-5_5

On two LZ78-style grammars: Compression bounds and compressed-space computation

Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov, Simon J. Puglisi

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length n; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor Ω(n^1/3) but is always within a factor (Formula presented). In addition, we show that the standard algorithms using Θ(z) working space to construct the LZD and LZMW parsings, where z is the size of the parsing, work in Ω(n^5/4) time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses O(z log n) space and O(n + zlog²n) time w.h.p.

Original language	English
Title of host publication	String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings
Editors	Rossano Venturini, Gabriele Fici, Marinella Sciortino
Publisher	Springer Verlag
Pages	51-67
Number of pages	17
ISBN (Print)	9783319674278
DOIs	https://doi.org/10.1007/978-3-319-67428-5_5
Publication status	Published - 2017
Event	24th International Symposium on String Processing and Information Retrieval, SPIRE 2017 - Palermo, Italy Duration: Sept 26 2017 → Sept 29 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10508 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	24th International Symposium on String Processing and Information Retrieval, SPIRE 2017
Country/Territory	Italy
City	Palermo
Period	9/26/17 → 9/29/17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-67428-5_5

Cite this

Badkobeh, G., Gagie, T., Inenaga, S., Kociumaka, T., Kosolobov, D., & Puglisi, S. J. (2017). On two LZ78-style grammars: Compression bounds and compressed-space computation. In R. Venturini, G. Fici, & M. Sciortino (Eds.), String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings (pp. 51-67). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10508 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-67428-5_5

On two LZ78-style grammars: Compression bounds and compressed-space computation. / Badkobeh, Golnaz; Gagie, Travis; Inenaga, Shunsuke et al.
String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. ed. / Rossano Venturini; Gabriele Fici; Marinella Sciortino. Springer Verlag, 2017. p. 51-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10508 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Badkobeh, G, Gagie, T, Inenaga, S, Kociumaka, T, Kosolobov, D & Puglisi, SJ 2017, On two LZ78-style grammars: Compression bounds and compressed-space computation. in R Venturini, G Fici & M Sciortino (eds), String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10508 LNCS, Springer Verlag, pp. 51-67, 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017, Palermo, Italy, 9/26/17. https://doi.org/10.1007/978-3-319-67428-5_5

Badkobeh G, Gagie T, Inenaga S, Kociumaka T, Kosolobov D, Puglisi SJ. On two LZ78-style grammars: Compression bounds and compressed-space computation. In Venturini R, Fici G, Sciortino M, editors, String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. Springer Verlag. 2017. p. 51-67. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-67428-5_5

Badkobeh, Golnaz ; Gagie, Travis ; Inenaga, Shunsuke et al. / On two LZ78-style grammars : Compression bounds and compressed-space computation. String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. editor / Rossano Venturini ; Gabriele Fici ; Marinella Sciortino. Springer Verlag, 2017. pp. 51-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dd8cc2f67f564dec936073a5de0eadaa,

title = "On two LZ78-style grammars: Compression bounds and compressed-space computation",

abstract = "We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length n; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor Ω(n1/3) but is always within a factor (Formula presented). In addition, we show that the standard algorithms using Θ(z) working space to construct the LZD and LZMW parsings, where z is the size of the parsing, work in Ω(n5/4) time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses O(z log n) space and O(n + zlog2n) time w.h.p.",

author = "Golnaz Badkobeh and Travis Gagie and Shunsuke Inenaga and Tomasz Kociumaka and Dmitry Kosolobov and Puglisi, {Simon J.}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017 ; Conference date: 26-09-2017 Through 29-09-2017",

year = "2017",

doi = "10.1007/978-3-319-67428-5_5",

language = "English",

isbn = "9783319674278",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "51--67",

editor = "Rossano Venturini and Gabriele Fici and Marinella Sciortino",

booktitle = "String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings",

address = "Germany",

}

TY - GEN

T1 - On two LZ78-style grammars

T2 - 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017

AU - Badkobeh, Golnaz

AU - Gagie, Travis

AU - Inenaga, Shunsuke

AU - Kociumaka, Tomasz

AU - Kosolobov, Dmitry

AU - Puglisi, Simon J.

PY - 2017

Y1 - 2017

N2 - We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length n; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor Ω(n1/3) but is always within a factor (Formula presented). In addition, we show that the standard algorithms using Θ(z) working space to construct the LZD and LZMW parsings, where z is the size of the parsing, work in Ω(n5/4) time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses O(z log n) space and O(n + zlog2n) time w.h.p.

AB - We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length n; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor Ω(n1/3) but is always within a factor (Formula presented). In addition, we show that the standard algorithms using Θ(z) working space to construct the LZD and LZMW parsings, where z is the size of the parsing, work in Ω(n5/4) time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses O(z log n) space and O(n + zlog2n) time w.h.p.

UR - http://www.scopus.com/inward/record.url?scp=85030148563&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85030148563&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-67428-5_5

DO - 10.1007/978-3-319-67428-5_5

M3 - Conference contribution

AN - SCOPUS:85030148563

SN - 9783319674278

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 51

EP - 67

BT - String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings

A2 - Venturini, Rossano

A2 - Fici, Gabriele

A2 - Sciortino, Marinella

PB - Springer Verlag

Y2 - 26 September 2017 through 29 September 2017

ER -

On two LZ78-style grammars: Compression bounds and compressed-space computation

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this