Faster lyndon factorization algorithms for SLP and LZ78 compressed text

Tomohiro I; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-319-02432-5_21

Faster lyndon factorization algorithms for SLP and LZ78 compressed text

Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

8 Citations (Scopus)

Abstract

We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n and height h that describes w, the first algorithm runs in O(nh(n + log N log n)) time and O(n²) space. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O(s log s) time and space.

Original language	English
Title of host publication	String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings
Publisher	Springer Verlag
Pages	174-185
Number of pages	12
ISBN (Print)	9783319024318
DOIs	https://doi.org/10.1007/978-3-319-02432-5_21
Publication status	Published - 2013
Event	20th International Symposium on String Processing and Information Retrieval, SPIRE 2013 - Jerusalem, Israel Duration: Oct 7 2013 → Oct 9 2013

Publication series

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

Other

Other	20th International Symposium on String Processing and Information Retrieval, SPIRE 2013
Country/Territory	Israel
City	Jerusalem
Period	10/7/13 → 10/9/13

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-02432-5_21

Cite this

I, T., Nakashima, Y., Inenaga, S., Bannai, H., & Takeda, M. (2013). Faster lyndon factorization algorithms for SLP and LZ78 compressed text. In String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings (pp. 174-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8214). Springer Verlag. https://doi.org/10.1007/978-3-319-02432-5_21

Faster lyndon factorization algorithms for SLP and LZ78 compressed text. / I, Tomohiro; Nakashima, Yuto ; Inenaga, Shunsuke et al.
String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings. Springer Verlag, 2013. p. 174-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8214).

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

I, T, Nakashima, Y , Inenaga, S, Bannai, H & Takeda, M 2013, Faster lyndon factorization algorithms for SLP and LZ78 compressed text. in String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8214, Springer Verlag, pp. 174-185, 20th International Symposium on String Processing and Information Retrieval, SPIRE 2013, Jerusalem, Israel, 10/7/13. https://doi.org/10.1007/978-3-319-02432-5_21

I T, Nakashima Y , Inenaga S, Bannai H, Takeda M. Faster lyndon factorization algorithms for SLP and LZ78 compressed text. In String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings. Springer Verlag. 2013. p. 174-185. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-02432-5_21

I, Tomohiro ; Nakashima, Yuto ; Inenaga, Shunsuke et al. / Faster lyndon factorization algorithms for SLP and LZ78 compressed text. String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings. Springer Verlag, 2013. pp. 174-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c8fed2a59f854b54b3d792c93a18a67a,

title = "Faster lyndon factorization algorithms for SLP and LZ78 compressed text",

abstract = "We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n and height h that describes w, the first algorithm runs in O(nh(n + log N log n)) time and O(n2) space. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O(s log s) time and space.",

author = "Tomohiro I and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

year = "2013",

doi = "10.1007/978-3-319-02432-5_21",

language = "English",

isbn = "9783319024318",

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

publisher = "Springer Verlag",

pages = "174--185",

booktitle = "String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings",

address = "Germany",

note = "20th International Symposium on String Processing and Information Retrieval, SPIRE 2013 ; Conference date: 07-10-2013 Through 09-10-2013",

}

TY - GEN

T1 - Faster lyndon factorization algorithms for SLP and LZ78 compressed text

AU - I, Tomohiro

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2013

Y1 - 2013

N2 - We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n and height h that describes w, the first algorithm runs in O(nh(n + log N log n)) time and O(n2) space. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O(s log s) time and space.

AB - We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n and height h that describes w, the first algorithm runs in O(nh(n + log N log n)) time and O(n2) space. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O(s log s) time and space.

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

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

U2 - 10.1007/978-3-319-02432-5_21

DO - 10.1007/978-3-319-02432-5_21

M3 - Conference contribution

AN - SCOPUS:84893901215

SN - 9783319024318

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

SP - 174

EP - 185

BT - String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings

PB - Springer Verlag

T2 - 20th International Symposium on String Processing and Information Retrieval, SPIRE 2013

Y2 - 7 October 2013 through 9 October 2013

ER -

Faster lyndon factorization algorithms for SLP and LZ78 compressed text

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this