Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding

P. G. Howard and J. S. Vitter. ``Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding,'' Journal of Information Processing and Management, 30(6), 1994, 777-790. A shortened version appears in Proceedings of the 1993 IEEE Data Compression Conference (DCC '93), Snowbird, UT, April 1993.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

We give a detailed algorithm for fast text compression. Our algorithm, related to the PPM method, simplifies the modeling phase by eliminating the escape mechanism, and speeds up coding by using a combination of quasi-arithmetic coding and Rice coding. We provide details of the use of quasi-arithmetic code tables, and analyze their compression performance. Our Fast PPM method is shown experimentally to be almost twice as fast as the PPMC method, while giving comparable compression.