Hybrid Prefix Codes for Practical Use

Mike Liddell
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. IEEE Data Compression Conference, Snowbird, Utah, March 2003, 392-401.

Errata

There have been problems discovered in this paper, unfortunately, and some of the stated claims may not be correct. Please contact me for an update before citing it.

Abstract

Minimum-redundancy prefix codes are widely used, and approximate codes have also received considerable attention. Flat codes, which may be considered as a class of approximate codes, have an extremely simple structure which facilitates fast decoding, but their compression effectiveness is often poor. Minimum-redundancy prefix codes, on the other hand, are slower to decode than flat codes, but minimize the compressed file size. We present a hybrid code which exhibits the simple structure of a flat code and retains much of the compression effectiveness of a minimum-redundancy code. The structural constraints of the hybrid code should enable fast decoding and also provide for fast compressed string searching. We discuss properties of the hybrid codes and a method for their efficient calculation.