CONDITIONS FOR OPTIMALITY OF THE HUFFMAN-ALGORITHM

作     者：PARKER, DS 

出 版 物：《SIAM JOURNAL ON COMPUTING》 

年 卷 期：1980年第9卷第3期

页      面：470-489页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Huffman algorithm optimal tree construction weighted path length tree height quasilinear functions convex functions Rényi entropy 

摘      要：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.