Best Huffman trees

Citation data:

Acta Informatica, ISSN: 0001-5903, Vol: 16, Issue: 3, Page: 363-370

Publication Year:
1981
Usage 1
Abstract Views 1
Captures 4
Readers 4
Citations 6
Citation Indexes 6
Repository URL:
http://scholarsmine.mst.edu/comsci_facwork/321
DOI:
10.1007/bf00289311
Author(s):
Markowsky, George
Publisher(s):
Springer Nature; Springer Verlag
Tags:
Computer Science; Computer Sciences
article description
Given a sequence of positive weights, W=w≧...≧w>0, there is a Huffman tree, T↑ ("T-up") 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↓, ("T-down") 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 Springer-Verlag.