We consider the following variant of Huffman coding in which the costs of the letters rather than the probabilities of the words, are nonuniform: "Given an alphabet of r letters of nonuniform length, find a minimum-average-length prefix-free set of n codewords over the alphabet"; equivalently, "Find an optimal r-ary search tree with n leaves, where each leaf is accessed with equal probability but the cost to descend from a parent to its ith child depends on i." We show new structural properties of such codes, leading to an O(n log2 r)-time algorithm for finding them. This new algorithm is simpler and faster than the best previously known O(nr min{log n, r})-time algorithm, due to Perl, Garey, and Even [J. Assoc. Comput. Mach., 22 (1975), pp. 202-214].

We give a polynomial-time approximation scheme for the generalization of Huffman coding in which codeword letters have nonuniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a (1 +?)-approximate solution in time O(n+f(?) log3 n), where n is the input size. © 2012 Society for Industrial and Applied Mathematics.

Huang and Wong [1984] proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler [1994] proposed modifying Huang and Wong's algorithm to obtain an algorithm for a different problem: computing optimal two-way-comparison search trees. We show that the dynamic program underlying Spuler's algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.

AbstractHuang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong’s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler’s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.