Towards Clean Reversible Lossless Compression

Zip and unzip are everyday tools in today’s digital world. Since they are inherently inverse to each other, they are ideal for studying reversible computing methods on real-world problems. In this work-in-progress study, we take steps to develop a reversible zip tool. As a proof of concept, we designed clean (garbage-free) reversible versions of two algorithms, which are officially recognized by the zip-specification. Our design goal was not merely to achieve reversibility, but rather to maintain the asymptotic complexity of the irreversible counterparts. Because of their efficiency and different approaches to compression, we chose the dictionary-based Lempel–Ziv–Welch Compression (LZW) and the transformation-based Burrows–Wheeler Transform (BWT). As part of the challenge, we found a way to zero-clear the LZW dictionary and reversibly sort rotations for BWT. We have successfully created clean reversible versions of both algorithms and fully implemented and tested them in the reversible language Janus. Our reversible LZW has a worst-case runtime of Θ(n), just like the most efficient irreversible version. Our reversible BWT is, in the worst case, a factor n² slower than the most efficient irreversible version. There are currently no better trace-free reversible methods for lossless compression.