2006/05/23 by Michael B. Baer, Baer, Michael B. · 1 citation
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #E.4 #FOS: Computer and information sciences #H.1.1 #I.2.8 #Information Theory (cs.IT) #cs.DS #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0605099
7 pages, submitted to Elsevier
arxiv created 2009/03/28 · arxiv updated 2009/12/01
An alphabetic binary tree formulation applies to problems in which an outcome needs to be determined via alphabetically ordered search prior to the termination of some window of opportunity. Rather than finding a decision tree minimizing ∑i=1n w(i) l(i), this variant involves minimizing loga ∑i=1n w(i) al(i) for a given a ∈ (0,1). This note introduces a dynamic programming algorithm that finds the optimal solution in polynomial time and space, and shows that 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 approximation algorithms which can find a suboptimal solution in linear time (for one) or \order(n log n) time (for the other), with associated coding redundancy bounds.