The length-restricted code-construction problem arises when using prefix codes for large messages and also for search-tree depth minimization. A problem instance comprises an ordered set of input probabilities which in this paper are assumed, without loss of generality, to be a set of unnormalized integer frequencies {f1, f2,..., fn}, and a maximum codeword length L bits. The package-merge algorithm of Larmore and Hirschberg constructs a minimum-redundancy length-restricted code in O(nL) time. Here we present an algorithm which computes a minimum-redundancy length-restricted code in O((H L + 1)n) time, by starting with a minimum-redundancy (Huffman) code with a maximum codeword length of H, and then refining it to meet the length limit L. The new algorithm is suited to problems where H - L is small; and when H - L > L - [log n], the new algorithm outperforms all previous methods. Experimental results confirm the behavior of the new algorithm

Minimum-redundancy prefix codes have been a mainstay of research and commercial compression systems since their discovery by David Huffman more than 50 years ago. In this experimental evaluation we compare techniques for decoding minimum-redundancy codes, and quantify the relative benefits of recently developed restricted codes that are designed to accelerate the decoding process. We find that table-based decoding techniques offer fast operation, provided that the size of the table is kept relatively small, and that approximate coding techniques can offer higher decoding rates than Huffman codes with varying degrees of loss of compression effectiveness. Copyright © 2006 John Wiley & Sons, Ltd.

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.

The prefix-free code construction problem is to take a message containing n unique symbols and produce a set of n codewords which can be used to create a reversible encoding of the message. The minimum-redundancy code construction problem adds the requirement that the code produced must minimise the cost of transmission (or storage) of the message. Adding another constraint, the minimum-redundancy length-restricted code construction problem is to create a minimum-redundancy code in which no codeword has a length greater than L bits. The solution to the minimum-redundancy code construction problem is due to Huffman (1952). The package-merge strategy of Larmore and Hirschberg (1990) is a two-stage mechanism for creating minimum-redundancy length-restricted codes. Their implementation, here called ORIGINAL-PM, requires O(nL) time and space. ORIGINAL-PM follows the underlying strategy closely and the following is a description of both the principle and that first implementation. Different implementation methods are discussed.

This paper describes variants of a recent length-restricted coding technique for use in static and dynamic frameworks. The resulting compression systems are shown to have identical asymptotic time complexity and also competitive performance to the corresponding unrestricted systems.