Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Conditions for Optimality of the Huffman Algorithm
Ist Teil von
SIAM journal on computing, 1980-08, Vol.9 (3), p.470-489
Ort / Verlag
Philadelphia: Society for Industrial and Applied Mathematics
Erscheinungsjahr
1980
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
A new general formulation of Huffman tree construction is presented which has broad application. Recall that the Huffman algorithm forms a tree, in which every node has some associated weight, by specifying at every step of the construction which nodes are to be combined to form a new node with a new combined weight. We characterize a wide class of weight combination functions, the quasilinear functions, for which the Huffman algorithm produces optimal trees under correspondingly wide classes of cost criteria. In addition, known results about Huffman tree construction and related concepts from information theory and from the theory of convex functions are tied together. Suggestions for possible future applications are given.