• Calendar

December 3, Tuesday
12:00 – 14:00

We shall explore a method allowing the parallel decoding of a file that has been compressed by a static Huffman code, exploiting in particular the tendency of Huffman codes to resynchronize quickly in case of an error. This will then be extended to deal with the parallel decoding of JPEG files. JPEG is a widely used standard image compression technique and the last phase of its baseline implementation includes Huffman coding. We shall assume basic knowledge of Huffman's algorithm and of the properties of Huffman codes, in particular of canonical Huffman codes, which can be found in many good textbooks. Our focus, however, is on decompression, because it may be more important than compression in some cases. For instance, in information retrieval applications, compression is done only once and may therefore be as time consuming as necessary, but decompression of short pieces is done on-line and ought to be fast to allow a reasonable response time to a query.

This is Joint work with Tomi Klein.