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

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