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

Paolo Ferragina, Giovanni Manzini

Risultato della ricerca: Contributo alla conferenzaContributo in Atti di Convegnopeer review

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 originaleInglese
Pagine648-656
Numero di pagine9
Stato di pubblicazionePubblicato - 2004
Pubblicato esternamente
EventoProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Durata: 11 gen 200413 gen 2004

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Paese/TerritorioUnited States
CittàNew Orleans, LA.
Periodo11/01/0413/01/04

Fingerprint

Entra nei temi di ricerca di 'Compression boosting in optimal linear time using the Burrows-Wheeler Transform'. Insieme formano una fingerprint unica.

Cita questo