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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.