Towards Clean Reversible Lossless Compression
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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.
Originalsprog | Engelsk |
---|---|
Titel | Reversible Computation - 16th International Conference, RC 2024, Proceedings |
Redaktører | Torben Aegidius Mogensen, Lukasz Mikulski |
Forlag | Springer |
Publikationsdato | 2024 |
Sider | 94-102 |
ISBN (Trykt) | 9783031620751 |
DOI | |
Status | Udgivet - 2024 |
Begivenhed | 16th International Conference on Reversible Computation, RC 2024 - Torun, Polen Varighed: 4 jul. 2024 → 5 jul. 2024 |
Konference
Konference | 16th International Conference on Reversible Computation, RC 2024 |
---|---|
Land | Polen |
By | Torun |
Periode | 04/07/2024 → 05/07/2024 |
Navn | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Vol/bind | 14680 LNCS |
ISSN | 0302-9743 |
Bibliografisk note
Funding Information:
The last author was supported by JSPS KAKENHI Grant No. 22K11983 and Nanzan University Pache Research Subsidy I-A-2 for 2023.
Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
ID: 397032700