Alphabetic coding with exponential costs
This note considers an alphabetic binary tree formulation in a family of nonlinear problems. An application of this family occurs when a random Outcome needs to be determined via alphabetically ordered search within a stochastic time window. Rather than finding a decision tree minimizing Sigma(n)(i=1) w(i)l(i). this variant involves minimizing log(a) Sigma(n)(i=1) w(i)a(l(i)) for a given a is an element of (0, 1). Herein a dynamic programming algorithm finds the optimal solution in O(n(3)) time and O(n(2)) space; methods traditionally used to improve the speed of optimizations in related problems, such as the Hu-Tucker procedure, fail for this problem. This note thus also introduces two algorithms which can find a suboptimal solution in linear time (for one) or O(n logn) time (for the other), with associated redundancy bounds guaranteeing their coding efficiency. (C) 2009 Elsevier B.V. All rights reserved.
dynamic programming approximation algorithms information retrieval renyi entropy tree searching