Boosting textual compression in optimal linear time

DOI10.1145/1082036.1082043zbMath1323.68260OpenAlexW1968228074MaRDI QIDQ3546295

Paolo Ferragina, Marinella Sciortino, Giovanni Manzini, Raffaele 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 transformtext compressionempirical entropyHuffman codingLempel-Ziv compressors, suffix tree

Mathematics Subject Classification ID

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

Related Items (24)

The myriad virtues of wavelet trees ⋮ Weighted forward looking adaptive coding ⋮ A simple storage scheme for strings achieving entropy bounds ⋮ The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words ⋮ Wheeler graphs: a framework for BWT-based data structures ⋮ Measuring the clustering effect of BWT via RLE ⋮ 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 ⋮ Wavelet trees for all ⋮ When a dollar makes a BWT ⋮ Fixed block compression boosting in FM-indexes: theory and practice ⋮ 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 ⋮ Balancing and clustering of words in the Burrows-Wheeler transform ⋮ Move-to-front, distance coding, and inversion frequencies revisited ⋮ Efficient and compact representations of some non-canonical prefix-free codes ⋮ The alternating BWT: an algorithmic perspective ⋮ Compressed Multiple Pattern Matching ⋮ A new class of searchable and provably highly compressible string transformations ⋮ Bicriteria Data Compression ⋮ DNA combinatorial messages and epigenomics: the case of chromatin organization and nucleosome occupancy in eukaryotic genomes

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