logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

PPM performance with BWT complexity: A fast and effective data compression algorithm

delete2000-11-01
delete12
delete
OA
AI
M
Michelle Effros
DOI：10.1109/5.892706delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
This paper introduces a new data compression algorithm. The goal underlying this new code design is to achieve a single lossless lossless compression algorithm with the excellent compensation ratios of the Prediction by Partial Mapping (PPM) algorithms and the low complexity of codes based on the Burrows Wheeler Transform (BWT). Like the BWT-based codes, the proposed algorithm requires worst case O(n) computational complexity and memory; in contrast, the unbounded-context PPM algorithm, called PPM*, requires worst case O(n(2)) computational complexity. Like PPM*, the proposed algorthm allows the use of unbounded contexts. Using standard data sets for comparison, the proposed algorithm achieves compression performance better than proposed algorithm achieves compression performance better than that of the proposed algorithm yields an average rate of 2.29 bits per character (bpc) on the Calgary corpus; this results compares favorably with the 2.33 and 2.34 bpc of PPM5 and PPM* (PPM algorithms), the 2.43 bpc of BW94 (the original BWT-based code), and the 3.64 and 2.69 bpc of compress and gzip (popular Unix compression algorthms based on Lempel-Ziv (LZ) coding techniques) on the same data set. The given code does not, however match the best reported compression performance-2.12 bpc with PPMZ9-listed on the Calgary corpus results web page at the time of this publication. Results on the Canterbury corpus give a similar relative standing. The proposed algorithm gives an average rate of 2.15 bpc on the Canterbury corpus, while the Canterbury corpus web page gives an average rates of 1.99 bpc for PPMZ9, 2.11 bpc for PPM5, 2.15 bpc for PPM7, 2.23 bpc for BZIP2 (a popular BWT-based code), and 3.31 and 2.53 bpc for compress and gzip repectively.
Keywords:
Burrows Wheeler Transform
lossless source coding
prediction by partial mapping algorithm
suffix trees
text compression

Journal

Proceedings of the IEEE cover
Proceedings of the IEEE
IF:
25.9
Papers:
9.9K
Citations:
4.5W

Organization

No organization information available