CaltechAUTHORS
  A Caltech Library Service

Universal lossless source coding with the Burrows Wheeler transform

Effros, Michelle (1999) Universal lossless source coding with the Burrows Wheeler transform. In: DCC 1999 -- Data Compression Conference, 29-31 March, 1999, Snowbird, Utah. IEEE , Los Alamitos, CA, pp. 178-187. ISBN 0-7695-0096-X http://resolver.caltech.edu/CaltechAUTHORS:EFFdcc99

[img]
Preview
PDF
See Usage Policy.

378Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:EFFdcc99

Abstract

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.


Item Type:Book Section
Additional Information:© Copyright 1999 IEEE. Reprinted with permission. This material is based upon work partially supported by NSF CAREER Grant No. MIP-9501977, a grant from the Powell Foundation, and donations through the Intel 2000 Technology for Education Program.
Subject Keywords:convergence of numerical methods; source coding; transforms; source code design; source coding theory; universal source coding
Record Number:CaltechAUTHORS:EFFdcc99
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:EFFdcc99
Alternative URL:http://dx.doi.org/10.1109/DCC.1999.755667
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7334
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:01 Feb 2007
Last Modified:26 Dec 2012 09:31

Repository Staff Only: item control page