Alphabetic coding with exponential costs

DOI10.1016/J.IPL.2009.11.008zbMATH Open1206.68365OpenAlexW2004107401MaRDI QIDQ990132FDOQ990132

Authors Michael B. Baer

Publication date 2 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0605099

zbMATH Keywords

dynamic programmingapproximation algorithmsinformation retrievaltree searchingRényi entropy

Mathematics Subject Classification ID

Dynamic programming (90C39) Approximation algorithms (68W25)

Abstract: 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 $su{m}_{i=1}^{n}w(i)l(i)$, this variant involves minimizing $lo{g}_{a}su{m}_{i=1}^{n}w(i)a^{l(i)}$ for a given $ain(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(nlogn)$ time (for the other), with associated coding redundancy bounds.

Recommendations

• scientific article; zbMATH DE number 4047170
• Optimal Prefix Codes for Infinite Alphabets With Nonlinear Costs
• scientific article; zbMATH DE number 1260845
• Huffman coding with letter costs: a linear-time approximation scheme
• Universal Coding on Infinite Alphabets: Exponentially Decreasing Envelopes
• Coding Combinatorial Sources With Costs
• Bounds on the redundancy of binary alphabetical codes
• scientific article; zbMATH DE number 1083083
• scientific article; zbMATH DE number 8007
• Coding on Countably Infinite Alphabets

Cites work

• scientific article; zbMATH DE number 4210044 (Why is no real title available?)
• A Method for the Construction of Minimum-Redundancy Codes
• A coding theorem and Rényi's entropy
• Binary Trees Optimum Under Various Criteria
• Bounds on the redundancy of binary alphabetical codes
• Conditions for Optimality of the Huffman Algorithm
• Definition of entropy by means of a coding problem
• Optimal Prefix Codes for Infinite Alphabets With Nonlinear Costs
• Optimum binary search trees

Cited in

(5)

• On the Huffman and alphabetic tree problem with general cost functions
• Operations research applications of dichotomous search
• scientific article; zbMATH DE number 1927561 (Why is no real title available?)
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Trees with exponentially growing costs

This page was built for publication: Alphabetic coding with exponential costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990132)