TY - GEN

T1 - Towards Clean Reversible Lossless Compression

AU - Lyngby, Therese

AU - Nylandsted, Rasmus Ross

AU - Glück, Robert

AU - Yokoyama, Tetsuo

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024

Y1 - 2024

N2 - 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 n2 slower than the most efficient irreversible version. There are currently no better trace-free reversible methods for lossless compression.

AB - 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 n2 slower than the most efficient irreversible version. There are currently no better trace-free reversible methods for lossless compression.

KW - Burrows–Wheeler transforms (BWT)

KW - Clean reversible algorithms

KW - Lempel–Ziv–Welch compression (LZW)

KW - Lossless compression algorithms

KW - Reversible software

U2 - 10.1007/978-3-031-62076-8_7

DO - 10.1007/978-3-031-62076-8_7

M3 - Article in proceedings

AN - SCOPUS:85195886079

SN - 9783031620751

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 94

EP - 102

BT - Reversible Computation - 16th International Conference, RC 2024, Proceedings

A2 - Mogensen, Torben Aegidius

A2 - Mikulski, Lukasz

PB - Springer

T2 - 16th International Conference on Reversible Computation, RC 2024

Y2 - 4 July 2024 through 5 July 2024

ER -