On undetected redundancy in the Burrows-Wheeler transform

DOI10.4230/LIPICS.CPM.2018.3MaRDI QIDQ5140764zbMATH OpenOpenAlexFDO

Authors Uwe Baier

Publication date 16 December 2020

Full work available at URL https://arxiv.org/abs/1804.01937

zbMATH Keywords

BWTlossless data compressiontunneling

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: The Burrows-Wheeler-Transform (BWT) is an invertible permutation of a text known to be highly compressible but also useful for sequence analysis, what makes the BWT highly attractive for lossless data compression. In this paper, we present a new technique to reduce the size of a BWT using its combinatorial properties, while keeping it invertible. The technique can be applied to any BWT-based compressor, and, as experiments show, is able to reduce the encoding size by 8-16 % on average and up to 33-57 % in the best cases (depending on the BWT-compressor used), making BWT-based compressors competitive or even superior to today's best lossless compressors.

Recommendations

• scientific article; zbMATH DE number 1305460
• The Burrows-Wheeler transform between data compression and combinatorics on words
• Universal lossless source coding with the Burrows Wheeler transform
• An analysis of the Burrows-Wheeler transform
• Average linear time and compressed space construction of the Burrows-Wheeler transform

Cites work

• A Mathematical Theory of Communication
• A Method for the Construction of Minimum-Redundancy Codes
• A universal algorithm for sequential data compression
• Arithmetic Coding
• Burrows-Wheeler compression: Principles and reflections
• Compression with the tudocomp framework
• Data compression by means of a ``book stack
• scientific article; zbMATH DE number 1615289 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Indexing compressed text
• Suffix Arrays: A New Method for On-Line String Searches
• The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
• When indexing equals compression, experiments with compressing suffix arrays and applications
• Word-based text compression using the Burrows-Wheeler transform

Cited in

(6)

• Context exhumation after the Burrows-Wheeler transform
• Edge minimization in de Bruijn graphs
• Indexing the bijective BWT
• Local decodability of the Burrows-Wheeler transform
• tbwt
• Improved pangenomic classification accuracy with chain statistics

Describes a project that uses

Uses Software

• bzip2
• bcm
• gzip
• zpaq
• 7-Zip
• XZ Utils
• SDSL
• GitHub

This page was built for publication: On undetected redundancy in the Burrows-Wheeler transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140764)