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 λ|s|H0*(s)+ bits of storage in O(T(|s|)) time, where H0*(s) is the zeroth order entropy of the string s. Our booster improves A by compressing s within λ|s|Hk*(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 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.
Lingua originale | Inglese |
---|---|
Pagine | 648-656 |
Numero di pagine | 9 |
Stato di pubblicazione | Pubblicato - 2004 |
Pubblicato esternamente | Sì |
Evento | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Durata: 11 gen 2004 → 13 gen 2004 |
???event.eventtypes.event.conference???
???event.eventtypes.event.conference??? | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Paese/Territorio | United States |
Città | New Orleans, LA. |
Periodo | 11/01/04 → 13/01/04 |