On optimally partitioning a text to improve its compression
From MaRDI portal
Publication:634677
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
dynamic programmingdata compressionBurrows-Wheeler transformempirical entropyarithmetic and Huffman codingcompression boostingtable compression
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
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