Minimum Delay Codes
Author:
- 1 February 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (1) , 82-94
Abstract
Huffman’s algorithm finds a prefix-free binary code on a weighted alphabet which minimizes the expected length of the code string for a single symbol. A definition is given for the expected delay for a prefix-free binary code on a weighted alphabet: it is the expected time between a request to transmit the symbol and the completion of that transmission, assuming a channel with fixed capacity, where requests are queued. An $O(n^5 )$-time $O(n^3 )$-space convex hull algorithm is given that finds a code of minimal expected delay, where n is the size of the alphabet. It is conjectured that the algorithm has substantially lower time and space complexities in the worst case, and still lower in the average case. The heart of the proof of polynomial time complexity is the convex hull theorem, which states that under certain conditions a binary tree that minimizes one penalty measure can be changed to a binary tree that minimizes a second penalty measure in a carefully controlled sequence of changes called elementary shifts.Keywords
This publication has 7 references indexed in Scilit:
- Height Restricted Optimal Binary TreesSIAM Journal on Computing, 1987
- Efficient dynamic programming using quadrangle inequalities1980
- Optimal Binary Search Trees with Restricted Maximal DepthSIAM Journal on Computing, 1974
- Path Length of Binary Search TreesSIAM Journal on Applied Mathematics, 1972
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971
- Optimum binary search treesActa Informatica, 1971
- ber die konvexe H lle von n zuf llig gew hlten PunktenProbability Theory and Related Fields, 1963