Boosting textual compression in optimal linear time

DOI10.1145/1082036.1082043MaRDI QIDQ3546295zbMATH OpenOpenAlexFDO

Authors Paolo Ferragina, Giovanni Manzini, M. Sciortino, R. Giancarlo

Publication date 21 December 2008

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1082036.1082043

zbMATH Keywords

arithmetic codingBurrows-Wheeler transformempirical entropyHuffman codingLempel-Ziv compressors, suffix treetext compression

Mathematics Subject Classification ID

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

Recommendations

• Compression boosting in optimal linear time using the Burrows-Wheeler transform
• The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
• On optimally partitioning a text to improve its compression
• scientific article; zbMATH DE number 1305460
• Optimal partitions of strings: a new class of Burrows-Wheeler compression algorithms

Cited in

(27)

• Wheeler graphs: a framework for BWT-based data structures
• Measuring the clustering effect of BWT via RLE
• Fixed block compression boosting in FM-indexes: theory and practice
• Weighted forward looking adaptive coding
• When a dollar makes a BWT
• The alternating BWT: an algorithmic perspective
• DNA combinatorial messages and epigenomics: the case of chromatin organization and nucleosome occupancy in eukaryotic genomes
• The myriad virtues of wavelet trees
• Wavelet trees for all
• A simpler analysis of Burrows-Wheeler-based compression
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• Compressing table data with column dependency
• Rank and select revisited and extended
• A new class of searchable and provably highly compressible string transformations
• Compressed Multiple Pattern Matching
• Bicriteria data compression
• The Burrows-Wheeler transform between data compression and combinatorics on words
• Balancing and clustering of words in the Burrows-Wheeler transform
• The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
• Compression boosting in optimal linear time using the Burrows-Wheeler transform
• Efficient and compact representations of some non-canonical prefix-free codes
• A new class of string transformations for compressed text indexing
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• On optimally partitioning a text to improve its compression
• Text compression methods
• A simple storage scheme for strings achieving entropy bounds
• Move-to-front, distance coding, and inversion frequencies revisited

This page was built for publication: Boosting textual compression in optimal linear time

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