Data Compression Conference (DCC '99)
Universal Lossless Source Coding with the Burrows Wheeler Transform
Snowbird, Utah
March 29-March 31
ISBN: 0-7695-0096-X
We here consider a theoretical evaluation of data compression algorithms based on the Burrows Wheeler Transform (BWT). The main contributions include a variety of very simple new techniques for BWT-based universal lossless source coding on finite-memory sources and a set of new rate of convergence results for BWT-based source codes. The result is a theoretical validation and quantification of the earlier experimental observation that BWT-based lossless source codes give performance better than that of Ziv-Lempel style codes and almost as good as that of prediction by partial mapping (PPM) algorithms.