Move-to-Front, Distance Coding and Inversion Frequencies are three simple and effective techniques used to process the output of the Burrows-Wheeler Transform. In this paper we provide the first complete comparative analyses of these techniques, establishing upper and lower bounds on their compression ratios. We describe simple variants of these three techniques that compress any string up to a constant factor of its kth-order empirical entropy for any k >= 0. At the same time we prove lower bounds for the compression of arbitrary strings which show that these variants are nearly optimal. The bounds we establish are "entropy-only" bounds in the sense that they do not involve non-constant overheads. Our analyses provide new insights into the inner workings of these techniques, partially explain their good behavior in practice, and suggest strategies for improving their performance.

Move-to-Front, Distance Coding, and Inversion Frequencies Revisited

MANZINI, Giovanni
2007-01-01

Abstract

Move-to-Front, Distance Coding and Inversion Frequencies are three simple and effective techniques used to process the output of the Burrows-Wheeler Transform. In this paper we provide the first complete comparative analyses of these techniques, establishing upper and lower bounds on their compression ratios. We describe simple variants of these three techniques that compress any string up to a constant factor of its kth-order empirical entropy for any k >= 0. At the same time we prove lower bounds for the compression of arbitrary strings which show that these variants are nearly optimal. The bounds we establish are "entropy-only" bounds in the sense that they do not involve non-constant overheads. Our analyses provide new insights into the inner workings of these techniques, partially explain their good behavior in practice, and suggest strategies for improving their performance.
2007
9783540734369
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11579/25094
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 8
social impact