On optimally partitioning a text to improve its compression

DOI10.1007/s00453-010-9437-6zbMath1221.68302arXiv0906.4692OpenAlexW2157238134MaRDI QIDQ634677

Paolo Ferragina, Igor Nitto, Rossano Venturini

Publication date: 16 August 2011

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingdata compressionBurrows-Wheeler transformempirical entropyarithmetic and Huffman codingcompression boostingtable compression

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)

Related Items

The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words, Greedy versus optimal analysis of bounded size dictionary compression and on-the-fly distributed computing, The greedy approach to dictionary-based static text compression on a distributed system, Fixed block compression boosting in FM-indexes: theory and practice, The alternating BWT: an algorithmic perspective, Bicriteria Data Compression, Improved and extended locating functionality on compressed suffix arrays

Uses Software

• Bigtable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The myriad virtues of wavelet trees
• 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
• Word-based text compression using the Burrows-Wheeler transform
• The compressed permuterm index
• An analysis of the Burrows—Wheeler transform
• Improving table compression with combinatorial optimization
• Position-Restricted Substring Searching
• Boosting textual compression in optimal linear time
• Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms
• A locally adaptive data compression scheme
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
• Data compression with long repeated strings