compression boosting in optimal linear time using the burrows-wheeler transform
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 ) + log 2 | s | + g k 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 | 2 ). 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.
compression boosting optimality timing transformation paper order algorithm strings storage entropy dynamic programming design structure