TY - GEN

T1 - Converting SLP to LZ78 in almost linear time

AU - Bannai, Hideo

AU - Gawrychowski, Paweł

AU - Inenaga, Shunsuke

AU - Takeda, Masayuki

PY - 2013

Y1 - 2013

N2 - Given a straight line program of size n, we are interested in constructing the LZ78 factorization of the corresponding text. We show how to perform such conversion in O(n + m log m) time, where m is the number of LZ78 codewords. This improves on the previously known O(n√N + m log N) solution [Bannai et al., SPIRE 2012]. The main tool in our algorithm is a data structure which allows us to efficiently operate on labels of the paths in a growing trie, and a certain method of recompressing the parse whenever it leads to decreasing its size.

AB - Given a straight line program of size n, we are interested in constructing the LZ78 factorization of the corresponding text. We show how to perform such conversion in O(n + m log m) time, where m is the number of LZ78 codewords. This improves on the previously known O(n√N + m log N) solution [Bannai et al., SPIRE 2012]. The main tool in our algorithm is a data structure which allows us to efficiently operate on labels of the paths in a growing trie, and a certain method of recompressing the parse whenever it leads to decreasing its size.

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

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

U2 - 10.1007/978-3-642-38905-4_6

DO - 10.1007/978-3-642-38905-4_6

M3 - Conference contribution

AN - SCOPUS:84884303892

SN - 9783642389047

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

SP - 38

EP - 49

BT - Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings

T2 - 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013

Y2 - 17 June 2013 through 19 June 2013

ER -