Suppose a finite string \(S\), consists of a set of elements of equal length over an alphabet of \(N\) elements, and that the occurrence frequencies of each element in \(S\) are known in advance. The best known technique for data compression is the static Huffman compression algorithm which produces a minimal prefix code for the elements of \(S\) in the sense that no other prefix code compresses \(S\) more. However, because Huffman codes are dependent on the element frequencies, decode information must be stored along with the compressed file. The decode table typically consists of some representation of the shape of the Huffman tree followed by a list of elements being encoded. The authors consider the representation of the Huffman tree in a canonical form which leads to storage efficiencies. In addition, the storage of the tree shape is further improved by avoiding the rather large fixed length fields of size \(\log N\) bits typically used to store the number of leaves at each level of the tree. Two techniques for storing the Huffman tree shape were addressed. One technique uses a base one method and the other a base two method of encoding the number of leaves at each level yielding significant improvements in the size of the tree shape.
For the entire collection see [Zbl 0772.00029].