Best Huffman Trees

Abstract

Given a sequence of positive weights, W=w1≧...≧wn>0, there is a Huffman tree, T↑ ("T-up") which minimizes the following functions: max{d(wi)}; Σd(wi); Σf(d(wi))wi (here d(wi) represents the distance of a leaf of weight wi to the root and f is a function defined for nonnegative integers having the property that g(x) = f(x + 1) - f(x) is monotone increasing) over the set of all trees for W having minimal expected length. Minimizing the first two functions was first done by Schwartz [5]. In the case of codes where W is a sequence of probabilities, this implies that the codes based on T↑ have all their absolute central moments minimal. In particular, they are the least variance codes which were also described by Kou [3]. Furthermore, there exists a Huffman tree T↓, ("T-down") which maximizes the functions considered above.
However, if g(x) is monotone decreasing, T↑ and T↓, respectively maximize and minimize Σf(d(wi) wi) over the set of all trees for W having minimal expected length. In addition, we derive a number of interesting results about the distribution of labels within Huffman trees. By suitable modifications of the usual Huffman tree construction, (see [1]) T↑ and T↓ can also be constructed in time O(n log n).

Department(s)

Computer Science

International Standard Serial Number (ISSN)

0001-5903

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1981 Springer Verlag, All rights reserved.

Publication Date

01 Nov 1981

Link to Full Text

Share

 
COinS