Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Decompressing Lempel-Ziv compressed text

Abstract: 

We consider the problem of decompressing the Lempel--Ziv 77 representation of a string $S$ of length $n$ using a working space as close as possible to the size $z$ of the input. The folklore solution for the problem runs in $O(n)$ time but requires random access to the whole decompressed text. Another folklore solution is to convert LZ77 into a grammar of size $O(z\log(n/z))$ and then stream $S$ in linear time. In this paper, we show that $O(n)$ time and $O(z)$ working space can be achieved for constant-size alphabets. On general alphabets of size $\sigma$, we describe (i) a trade-off achieving $O(n\log^\delta \sigma)$ time and $O(z\log^{1-\delta}\sigma)$ space for any $0\leq \delta\leq 1$, and (ii) a solution achieving $O(n)$ time and $O(z\log\log (n/z))$ space. The latter solution, in particular, dominates both folklore algorithms for the problem. Our solutions can, more generally, extract any specified subsequence of $S$ with little overheads on top of the linear running time and working space. As an immediate corollary, we show that our techniques yield improved results for pattern matching problems on LZ77-compressed text.

up
0 users have voted:

Paper Details

Authors:
Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gortz, Nicola Prezza
Submitted On:
24 April 2020 - 12:40pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Travis Gagie
Session:
Session 5
Document Year:
2020
Cite

Document Files

DCC '20 slides for Travis Gagie (embedded audio files)

(61)

Subscribe

[1] Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gortz, Nicola Prezza, "Decompressing Lempel-Ziv compressed text", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5090. Accessed: Jul. 10, 2020.
@article{5090-20,
url = {http://sigport.org/5090},
author = {Philip Bille; Mikko Berggren Ettienne; Travis Gagie; Inge Li Gortz; Nicola Prezza },
publisher = {IEEE SigPort},
title = {Decompressing Lempel-Ziv compressed text},
year = {2020} }
TY - EJOUR
T1 - Decompressing Lempel-Ziv compressed text
AU - Philip Bille; Mikko Berggren Ettienne; Travis Gagie; Inge Li Gortz; Nicola Prezza
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5090
ER -
Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gortz, Nicola Prezza. (2020). Decompressing Lempel-Ziv compressed text. IEEE SigPort. http://sigport.org/5090
Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gortz, Nicola Prezza, 2020. Decompressing Lempel-Ziv compressed text. Available at: http://sigport.org/5090.
Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gortz, Nicola Prezza. (2020). "Decompressing Lempel-Ziv compressed text." Web.
1. Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gortz, Nicola Prezza. Decompressing Lempel-Ziv compressed text [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5090