Decompressing a file made by the gzip program at an arbitrary location is in principle impossible, due to the nature of the DEFLATE compression algorithm. Consequently, no existing program can take advantage of parallelism to rapidly decompress large gzip-compressed files. This is an unsatisfactory bottleneck, especially for the analysis of large sequencing data experiments. Here we propose a parallel algorithm and an implementation, pugz, that performs fast and exact decompression of any text file. We show that pugz is an order of magnitude faster than gunzip, and 5x faster than a highly-optimized sequential implementation (libdeflate). We also study the related problem of random access to compressed data. We give simple models and experimental results that shed light on the structure of gzip-compressed files containing DNA sequences. Preliminary results show that random access to sequences within a gzip-compressed FASTQ file is almost always feasible at low compression levels, yet is approximate at higher compression levels.
Previous efforts have aimed to improve compression via better algorithms or hardware acceleration, e.g. in @cite_14 @cite_9 . Efficient decompression has been relatively less studied, except in the following works. A fine-grained hardware-accelerated decompression algorithm achieves a 2x speedup compared to gunzip @cite_6 . A recent unpublished highly-optimized sequential implementation ( libdeflate ) achieves roughly a 3x speedup github.com ebiggers libdeflate . Perhaps the closest work to ours is an attempt to recover corrupted DEFLATE-compressed files @cite_0 @cite_2 . It is proposed that damaged -compressed files containing English text can be partially reconstructed from random locations. However, the bulk of the method hinges on frequency analysis which does not directly translate to files containing DNA, and also settles for lossy reconstruction.
@cite_14 @cite_9 @cite_6 @cite_0 @cite_2
2963235000 2144584185 1978280057 2162839010
Today's exponentially increasing data volumes and the high cost of storage make compression essential for the Big Data industry. Although research has concentrated on efficient compression, fast decompression is critical for analytics queries that repeatedly read compressed data. While decompression can be parallelized somewhat by assigning each data block to a different process, break-through speed-ups require exploiting the massive parallelism of modern multi-core processors and GPUs for data decompression within a block. We propose two new techniques to increase the degree of parallelism during decompression. The first technique exploits the massive parallelism of GPU and SIMD architectures. The second sacrifices some compression efficiency to eliminate data dependencies that limit parallelism during decompression. We evaluate these techniques on the decompressor of the DEFLATE scheme, called Inflate, which is based on LZ77 compression and Huffman encoding. We achieve a 2&#x00D7; speed-up in a head-to-head comparison with several multi core CPU-based libraries, while achieving a 17 energy saving with comparable compression ratios. This paper presents a method for recovering data from files compressed with the DEFLATE algorithm where short segments in the middle of the file have been corrupted, yielding a mix of literal bytes, bytes aligned with literals across the corrupted segment, and co-indexed unknown bytes. An improved reconstruction algorithm based on long byte n-grams increases the proportion of reconstructed bytes by an average of 8.9 absolute across the 21 languages of the Europarl corpus compared to previously-published work, and the proportion of unknown bytes correctly reconstructed by an average of 20.9 absolute, while running in one-twelfth the time on average. Combined with the new recovery method, corrupted segments of 128-4096 bytes in the compressed bit-stream result in reconstructed output which differs from the original file by an average of less than twice the number of bytes represented by the corrupted segment. Both new algorithms are implemented in the trainable open-source ZipRec 1.0 utility program. The JPEG compression method is among the most successful compression schemes since it readily provides good compressed results at a rather high compression ratio. However, the decompressed result of the standard JPEG decompression scheme usually contains some visible artifacts, such as blocking artifacts and Gibbs artifacts (ringing), especially when the compression ratio is rather high. In this paper, a novel artifact reducing approach for the JPEG decompression is proposed via sparse and redundant representations over a learned dictionary. Indeed, an effective two-step algorithm is developed. The first step involves dictionary learning and the second step involves the total variation regularization for decompressed images. Numerical experiments are performed to demonstrate that the proposed method outperforms the total variation and weighted total variation decompression methods in the measure of peak of signal to noise ratio, and structural similarity. Dynapack exploits space-time coherence to compress the consecutive frames of the 3D animations of triangle meshes of constant connectivity. Instead of compressing each frame independently (space-only compression) or compressing the trajectory of each vertex independently (time-only compression), we predict the position of each vertex v of frame f from three of its neighbors in frame f and from the positions of v and of these neighbors in the previous frame (space-time compression). We introduce here two extrapolating spacetime predictors: the ELP extension of the Lorenzo predictor, developed originally for compressing regularly sampled 4D data sets, and the Replica predictor. ELP may be computed using only additions and subtractions of points and is a perfect predictor for portions of the animation undergoing pure translations. The Replica predictor is slightly more expensive to compute, but is a perfect predictor for arbitrary combinations of translations, rotations, and uniform scaling. For the typical 3D animations that we have compressed, the corrections between the actual and predicted value of the vertex coordinates may be compressed using entropy coding down to an average ranging between 1.37 and 2.91 bits, when the quantization used ranges between 7 and 13 bits. In comparison, space-only compression yields a range of 1.90 to 7.19 bits per coordinate and time-only compressions yields a range of 1.77 to 6.91 bits per coordinate. The implementation of the Dynapack compression and decompression is trivial and extremely fast. It perform a sweep through the animation, only accessing two consecutive frames at a time. Therefore, it is particularly well suited for realtime and out-of-core compression, and for streaming decompression.