CaltechAUTHORS
  A Caltech Library Service

PPM performance with BWT complexity: a new method for lossless data compression

Effros, Michelle (2000) PPM performance with BWT complexity: a new method for lossless data compression. In: Data Compression Conference (DCC 2000), Snowbird, UT, 28-30 March 2000. IEEE , Los Alamitos, CA, pp. 203-212. ISBN 0 7695 0592 9. http://resolver.caltech.edu/CaltechAUTHORS:EFFdcc00

[img]
Preview
PDF
See Usage Policy.

231Kb

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

Abstract

This work combines a new fast context-search algorithm with the lossless source coding models of PPM to achieve a lossless data compression algorithm with the linear context-search complexity and memory of BWT and Ziv-Lempel codes and the compression performance of PPM-based algorithms. Both sequential and nonsequential encoding are considered. The proposed algorithm yields an average rate of 2.27 bits per character (bpc) on the Calgary corpus, comparing favorably to the 2.33 and 2.34 bpc of PPM5 and PPM* and the 2.43 bpc of BW94 but not matching the 2.12 bpc of PPMZ9, which, at the time of this publication, gives the greatest compression of all algorithms reported on the Calgary corpus results page. The proposed algorithm gives an average rate of 2.14 bpc on the Canterbury corpus. The Canterbury corpus Web page gives average rates of 1.99 bpc for PPMZ9, 2.11 bpc for PPM5, 2.15 bpc for PPM7, and 2.23 bpc for BZIP2 (a BWT-based code) on the same data set.


Item Type:Book Section
Additional Information:© Copyright 2002 IEEE. Reprinted with permission. This material is based upon work partially supported by NSF Award No. CCR-9909026.
Subject Keywords:computational complexity, search problems, sequential codes, source coding, source code design, source coding theory, universal source coding
Record Number:CaltechAUTHORS:EFFdcc00
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:EFFdcc00
Alternative URL:http://dx.doi.org/10.1109/DCC.2000.838160
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7402
Collection:CaltechAUTHORS
Deposited By: Lindsay Cleary
Deposited On:12 Feb 2007
Last Modified:26 Dec 2012 09:31

Repository Staff Only: item control page