Block Merging for Off-Line Compression
Raymond Wan
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Alistair Moffat
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Status
Proc. International Conference on Combinatorial Pattern Matching,
Fukuoka, Japan, July 2002, pages 32-41.
Abstract
To bound memory consumption, most compression systems provide a
facility that controls the amount of data that may be processed at
once.
In this work we consider the Re-Pair mechanism of Larsson and Moffat,
which processes large messages as disjoint blocks.
We show that the blocks emitted by Re-Pair can be post-processed to
yield further savings, and describe techniques that allow files of
500 MB or more to be compressed in a holistic manner using
less than that much main memory.
The block merging process we describe has the additional advantage
of allowing new text to be appended to the end of the compressed
file.