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 -