Compression boosting in optimal linear time using the Burrows-Wheeler Transform

ABSTRACT

In this paper we provide the first compression booster that turns a zeroth order compressor into a more effiective k-th order compressor without any loss in time efficiency. More precisely, let A be an algorithm that compresses a string s within λ|s|H*0(s)+μ bits of storage in O(T (|s|)) time, where H*0(s) is the zeroth order entropy of the string s. Our booster improves A by compressing s within λ|s|H*0(S) + log2 |s| + gk bits still using O(T (|s|)) time, where H*k(s) is the k-th order entropy of s.The idea of a "compression booster" has been very recently introduced by Giancarlo and Sciortino in [7]. They combined the Burrows-Wheeler Transform [3] with dynamic programming and achieved our same compression bound but with running time O(T (|s|)) + Ω(|s|²). We start from the same premises of [7], but instead of using dynamic programming we design a linear time optimization algorithm based on novel structural properties of the Burrows-Wheeler Transform.

REFERENCES

• 1: Z. Arnavut, Generalization of the BWT Transformation and Inversion Ranks, Proceedings of the Data Compression Conference (DCC '02), p.447, April 02-04, 2002
• 2: Bernhard Balkenhol , Stefan Kurtz , Yuri M. Shtarkov, Modifications of the Burrows and Wheeler Data Compression Algorithm, Proceedings of the Conference on Data Compression, p.188, March 29-31, 1999
• 3: M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.
• 4: Sebastian Deorowicz, Second step algorithms in the Burrows-Wheeler compression algorithm, Software—Practice & Experience, v.32 n.2, p.99-111, February 2002 [doi>10.1002/spe.426]
• 5: P. Fenwick. The Burrows-Wheeler transform for block sorting text compression: principles and improvements. The Computer Journal, 39(9):731--740, 1996.
• 6: P. Ferragina , G. Manzini, Opportunistic data structures with applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.390, November 12-14, 2000
• 7: R. Giancarlo and M. Sciortino. Optimal partitions of strings: A new class of Burrows-Wheeler compression algorithms. In Combinatorial Pattern Matching Conference (CPM '03), pages 129--143, 2003.
• 8: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, When indexing equals compression: experiments with compressing suffix arrays and applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 9: Giovanni Manzini, An analysis of the Burrows—Wheeler transform, Journal of the ACM (JACM), v.48 n.3, p.407-430, May 2001 [doi>10.1145/382780.382782]
• 10: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 11: J. Seward. The bzip2 home page, 1997. http://sources.redhat.com/bzip2.
• 12: Anthony Ian Wirth , Alistair Moffat, Can We Do without Ranks in Burrows Wheeler Transform Compression?, Proceedings of the Data Compression Conference (DCC '01), p.419, March 27-29, 2001