TY - GEN
T1 - The burrows-wheeler transform
T2 - 24th International Symposium on Mathematical Foundations of Computer Science, MFCS 1999
AU - Manzini, Giovanni
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - In this paper we describe the Burrows-Wheeler Transform (BWT) a completely new approach to data compression which is the basis of some of the best compressors available today. Although it is easy to intuitively understand why the BWT helps compression, the analysis of BWT-based algorithms requires a careful study of every single algorithmic component. We describe two algorithms which use the BWT and we show that their compression ratio can be bounded in terms of the k-th order empirical entropy of the input string for any k ≥ 0. Intuitively, this means that these algorithms are able to make use of all the regularity which is in the input string. We also discuss some of the algorithmic issues which arise in the computation of the BWT, and we describe two variants of the BWT which promise interesting developments.
AB - In this paper we describe the Burrows-Wheeler Transform (BWT) a completely new approach to data compression which is the basis of some of the best compressors available today. Although it is easy to intuitively understand why the BWT helps compression, the analysis of BWT-based algorithms requires a careful study of every single algorithmic component. We describe two algorithms which use the BWT and we show that their compression ratio can be bounded in terms of the k-th order empirical entropy of the input string for any k ≥ 0. Intuitively, this means that these algorithms are able to make use of all the regularity which is in the input string. We also discuss some of the algorithmic issues which arise in the computation of the BWT, and we describe two variants of the BWT which promise interesting developments.
UR - https://www.scopus.com/pages/publications/49749104952
U2 - 10.1007/3-540-48340-3_4
DO - 10.1007/3-540-48340-3_4
M3 - Conference contribution
AN - SCOPUS:49749104952
SN - 3540664084
SN - 9783540664086
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 34
EP - 47
BT - Mathematical Foundations of Computer Science 1999 - 24th International Symposium, MFCS 1999, Proceedings
A2 - kutyłowski, Mirosław
A2 - Pacholski, Leszek
A2 - Wierzbicki, Tomasz
PB - Springer Verlag
Y2 - 6 September 1999 through 10 September 1999
ER -