ICS Theory Group

ICS 269, Spring 2002: Theory Seminar


15 November 2002:
Title: A Survey of Variable-Length Integer Coding Techniques
Speaker: Kevin Wortman

Abstract: The need often arises to encode a sequence of arbitrary integers. It is possible to map such a sequence to a stream of bytes and present the result to a general purpose compression algorithm, such as gzip, but the results are disappointing.

However, if we introduce the assumption that an integer's frequency is approximately inversely proportional to its magnitude, it becomes possible to encode integers efficiently. This talk will introduce one motivation for integer coding: the lossless compression of digitized audio. Then it will proceed to paraphrase a 1996 paper by Peter Fenwick that summarizes several methods of integer coding, and presents an experimental comparison of their effectiveness.