Hybrid prefix codes for practical use

Prefix-free codes continue to enjoy widespread use in compression systems due to their simple structure and their ease of decoding. Minimum-redundancy prefix codes, such as Huffman codes, are widely used. However, approximate codes also receive considerable attention. Flat prefix codes have an extremely simple structure that facilitates fast decoding, but their compression effectiveness is often regarded as poor. The minimum-redundancy prefix code is much slower to decode than a flat code while the compressed file size is minimized. A hybrid prefix code is presented that 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 provide fast compressed string searching. Properties of the hybrid codes are discussed as well as the method for their efficient calculation. An algorithm for the efficient construction of minimum-redundancy K-flat codes is presented and tested empirically.