Towards Clean Reversible Lossless Compression
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Towards Clean Reversible Lossless Compression. / Lyngby, Therese; Nylandsted, Rasmus Ross; Glück, Robert; Yokoyama, Tetsuo.
Reversible Computation - 16th International Conference, RC 2024, Proceedings. ed. / Torben Aegidius Mogensen; Lukasz Mikulski. Springer, 2024. p. 94-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 14680 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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 -
ID: 397032700