Alphabetic coding with exponential costs

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

Michael B. Baer

Publication date: 2 September 2010

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

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.

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

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

zbMATH Keywords

dynamic programmingapproximation algorithmsinformation retrieval[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=R%EF%BF%BD%EF%BF%BDnyi+entropy&go=Go R��nyi entropy]tree searching

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• On the Huffman and alphabetic tree problem with general cost functions
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Operations research applications of dichotomous search
• Title not available (Why is that?)
• 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)