Enhancing Data Compression: Recent Innovations in LZ77 Algorithms
Preprint
- 25 September 2024
- preprint
- Published by MDPI AG in Preprints.org
Abstract
The burgeoning volume of genomic data, fueled by advances in sequencing technologies, demands efficient data compression solutions. Traditional algorithms like Lempel-Ziv77 (LZ77) have been foundational in offering lossless compression, yet they often fall short when applied to the highly repetitive structures typical of genomic sequences. This review delves into the evolution of LZ77 and its derivatives, exploring specialized algorithms such as prefix-free parsing, AVL grammars, and LZ-based methods tailored for genomic data. Innovations in this field have led to enhanced compression ratios and processing efficiencies by leveraging the intrinsic redundancy within genomic datasets. We critically examine a spectrum of LZ77-based algorithms, including newer adaptations for external and semi-external memory settings, and contrast their efficacy in managing large-scale genomic data. Additionally, we discuss the potential of these algorithms to facilitate the construction of data structures such as compressed suffix trees, crucial for genomic analyses. This paper aims to provide a comprehensive guide on the current landscape and future directions of data compression technologies, equipping researchers and practitioners with insights to tackle the escalating data challenges in genomics and beyond.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Building large updatable colored de Bruijn graphs via mergingBioinformatics, 2019
- Utilizing the Public GenomeTrakr Database for Foodborne Pathogen Traceback2018
- LZ77 Computation Based on the Run-Length Encoded BWTAlgorithmica, 2017
- Engineering a Lightweight External Memory Suffix Array Construction AlgorithmMathematics in Computer Science, 2017
- Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets2014
- Lempel-Ziv Parsing in External Memory2014
- LZ77-Like Compression with Fast Random Access2010
- Faster entropy-bounded compressed suffix treesTheoretical Computer Science, 2009
- Lempel–Ziv Factorization Using Less Time & SpaceMathematics in Computer Science, 2008
- Computing Longest Previous Factor in linear time and applicationsInformation Processing Letters, 2008