Massively Parallel LZ77 Compression and Decompression on the GPU
Parallelizing data compression algorithms is difficult because algorithms like LZ77 have iterative dependencies that cannot easily be circumvented. Previous computation steps directly impact later steps in the algorithm, and parallelizing those dependent steps can prove difficult. My solution is to express both the encoding and decoding portions of LZ77 in terms of prefix sums, union-find operations, and other parallelizable computations. The results show that this methodology is effective in improving throughput. Compared to codes from the literature, my CUDA implementation is an order of magnitude faster but tends to have a lower compression ratio.
Parallelized LZ77, Lossless parallel compression and decompression
Wesley, K. (2022). <i>Massively parallel LZ77 compression and decompression on the GPU</i> (Unpublished thesis). Texas State University, San Marcos, Texas.