Journal
ALGORITHMICA
Volume 80, Issue 7, Pages 2048-2081Publisher
SPRINGER
DOI: 10.1007/s00453-017-0333-1
Keywords
Lempel-Ziv; Lossless compression; Succinct suffix trees
Funding
- CREST, JST
- Grants-in-Aid for Scientific Research [16K16009, 16H02870] Funding Source: KAKEN
Ask authors/readers for more resources
We show that both the Lempel-Ziv-77 and the Lempel-Ziv-78 factorization of a text of length n on an integer alphabet of size sigma can be computed in O(n) time with either O(n lg sigma) bits of working space, or (1 + epsilon) n lg n + O(n) bits (for a constant epsilon > 0) of working space (including the space for the output, but not the text).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
