Proc. 15th SIAM-ACM Symposium on Discrete Algorithms (SODA '04)

Compression Boosting in Optimal Linear Time Using the Burrows-Wheeler Transform

Paolo Ferragina (Università di Pisa)
Giovanni Manzini (Università del Piemonte Orientale and IIT-CNR, Pisa)

Abstract. In this paper we provide the first compression booster that turns a zeroth order compressor into a more effective k-th order compressor without any loss in time efficiency. More precisely, let A be an algorithm that compresses a string s within c|s|H₀(s) + d bits of storage in O(T(|s|)) time, where H₀(s) is the zeroth order entropy of the string s. Our booster improves A by compressing s within c |s| H_k(s) +log(|s|) + d' bits still using O(T(|s|)) time, where H_k(s) is the k-th order entropy of s. The compression bound holds for any k>0.

Retrieve a preliminary version in PDF (237956 bytes)