Best Huffman trees
 Citation data:

Acta Informatica, ISSN: 00015903, Vol: 16, Issue: 3, Page: 363370
 Publication Year:
 1981
 Repository URL:
 http://scholarsmine.mst.edu/comsci_facwork/321
 DOI:
 10.1007/bf00289311
 Author(s):
 Publisher(s):
 Tags:
 Computer Science; Computer Sciences
article description
Given a sequence of positive weights, W=w≧...≧w>0, there is a Huffman tree, T↑ ("Tup") which minimizes the following functions: max{d(w)}; Σd(w); Σf(d(w)) w(here d(w) represents the distance of a leaf of weight w 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↓, ("Tdown") which maximizes the functions considered above. However, if g(x) is monotone decreasing, T↑ and T↓, respectively maximize and minimize Σf(d(w) w) 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). © 1981 SpringerVerlag.