Lempel-Ziv (LZ77) parsing is a powerful tool for data compression that has been the subject of intense research in the past 40 years and is now used in popular and widely-used compression software and as part of larger software systems. In this paper we study algorithms to efficiently decompress strings from the LZ parsing that use working memory proportional to the size, z, of the parsing itself, not that of the output string, n, as is the usual case. The only work we are aware of on this problem is recent and due to Bille et al. who describe an algorithm using O(n log δ σ) time and O(z log 1-δ σ) space for any 0 ≤ δ ≤ 1. We provide the first implementation and experimental analysis of Bille et al.'s approach. Our results show that this approach, when implemented as described, is extremely slow in practice compared to the naive decompression algorithm, and uses lots of space. To remedy this we introduce several novel optimizations that drastically improve performance and lead to relevant spacetime tradeoffs in practice on all datasets we tested.

On Lempel-Ziv Decompression in Small Space

PUGLISI, SIMON JOHN
;
ROSSI, MASSIMILIANO
2019-01-01

Abstract

Lempel-Ziv (LZ77) parsing is a powerful tool for data compression that has been the subject of intense research in the past 40 years and is now used in popular and widely-used compression software and as part of larger software systems. In this paper we study algorithms to efficiently decompress strings from the LZ parsing that use working memory proportional to the size, z, of the parsing itself, not that of the output string, n, as is the usual case. The only work we are aware of on this problem is recent and due to Bille et al. who describe an algorithm using O(n log δ σ) time and O(z log 1-δ σ) space for any 0 ≤ δ ≤ 1. We provide the first implementation and experimental analysis of Bille et al.'s approach. Our results show that this approach, when implemented as described, is extremely slow in practice compared to the naive decompression algorithm, and uses lots of space. To remedy this we introduce several novel optimizations that drastically improve performance and lead to relevant spacetime tradeoffs in practice on all datasets we tested.
2019
978-1-7281-0657-1
Lempel Ziv decompression, Mergeable Dictionaries , Data structures , Data compression
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1002163
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact