Name
Abstract | ||
|---|---|---|
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 root 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-38905-4_6 | COMBINATORIAL PATTERN MATCHING |
Field | DocType | Volume |
Binary logarithm,Discrete mathematics,Data structure,Combinatorics,Computer science,Factorization,Binary search algorithm,Time complexity,Trie,Straight-line program | Conference | 7922 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.42 |
References | Authors | |
26 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hideo Bannai | 1 | 620 | 79.87 |
| Pawel Gawrychowski | 2 | 226 | 46.74 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Masayuki Takeda | 4 | 902 | 79.24 |