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.

See Usage Policy.


Use this Persistent URL to link to this item:


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
Related URLs:
URLURL TypeDescription
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7402
Deposited By: Lindsay Cleary
Deposited On:12 Feb 2007
Last Modified:08 Nov 2021 20:42

Repository Staff Only: item control page