Compression and Coding Algorithms

by

Andrew Turpin

Kluwer Academic Publishers, 2002

The Springer (nee Kluwer) catalog page is here; and it diverts to the Springer page, which is here.

It can also be ordered from Amazon.

Features

In-depth coverage of recent research in the areas of minimum-redundancy (Huffman) coding and arithmetic coding.
Full treatment of adaptive Huffman coding and adaptive arithmetic coding, plus other adaptive transformations such as recency-ranking.
Experimental results showing the performance of different coding methods on real-life data.
More than 30 compression algorithms explained with detailed pseudo-code, ranging from unary and binary coding through to calculation of length-limited and alphabetic codes.
Coverage of modern compression systems, including sliding window compression, PPM, and the Burrows-Wheeler transform.
Detailed bibliography of research resources, including, for each reference, an index of relevant pages.
Full topic index.

Information Available

Kluwer publicity flyer

Errata listing

Sample pages (subject to copyright, and not for distribution or duplication):

Title page, table of contents, and complete preface (PDF, 33K)
Page 1 (PDF, 5K)
Page 41 (PDF, 19K). Context: towards the end of the section about Golomb and Rice codes
Page 81 (PDF, 22K). Context: last page of the section about generating minimum-redundancy codes for certain constrained probability distributions.
Page 121 (PDF, 31K). Context: use of binary arithmetic coding to handle multi-symbol alphabets.
Page 161 (PDF, 20K). Context: data structures for maintaining cumulative frequency distributions for adaptive arithmetic coding.
Page 201 (PDF, 15K). Context: towards the end of the section about length-limited code construction, including part of a pseudo-code description of an algorithm.
Page 241 (PDF, 9K). Context: towards the end of the section that describes the Burrows-Wheeler transform.
Page 261 (PDF, 5K). Context: Sample bibliography page.

Note that, with the exception of the preface, these pages were selected because of their number rather than their content.

(click for larger image)

Links to Other Information

Other things that may be of interest:

Software for minimum redundancy coding
Software for arithmetic coding
Software for some integer coders: carry and rbuc
Software for some 64-bit integer coders

Other Books

And if Compression and Coding Algorithms is too expensive, consider buying a copy of Managing Gigabytes: Compressing and Indexing Documents and Images second edition, 1999, which can be purchased from Amazon (again, with a small commission paid from Amazon to us).

Alistair Moffat
ammoffat / unimelb.edu / au
December 1, 2003, January 13, 2013

Mandatory disclaimer: This page, its content and style, are the responsibility of the author and do not necessarily represent the views, policies, or opinions of The University of Melbourne.