Can We Do Without Ranks in Burrows Wheeler Transform Compression?

Anthony Ian Wirth
Department of Computer Science and Software Engineering, The University of Melbourne, Victoria 3010, Australia.

Alistair Moffat
Department of Computer Science and Software Engineering, The University of Melbourne, Victoria 3010, Australia.

Status

Proc. IEEE Data Compression Conference, Snowbird, Utah, March 2001, 419-428.

Abstract

Compressors based on the Burrows Wheeler transform (BWT) convert the transformed text into a string of (move-to-front) ranks. These ranks are then encoded with an Order-0 model, or a hierarchy of such models. Although these rank-based methods perform very well, we believe the transformation to MTF numbers blurs the distinction between individual symbols and is a possible cause of inefficiency. Instead of relying on symbol ranking, we examine the problem of directly encoding the symbols in the BWT text.