HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item:
Title: A generic top-down dynamic-programming approach to prefix-free coding
Authors: Golin, Mordecai J.
Xu, Xiaoming
Yu, Jiajin
Keywords: Dynamic programming
Speedup techniques
Issue Date: Jan-2009
Citation: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, USA, 4-6 January 2009, p. 758-767.
Abstract: Given a probability distribution over a set of n words to be transmitted, the Huffman Coding problem is to find a minimal-cost prefix free code for transmitting those words. The basic Huffman coding problem can be solved in O(n log n) time but variations are more difficult. One of the standard techniques for solving these variations utilizes a top-down dynamic programming approach. In this paper we show that this approach is amenable to dynamic programming speedup techniques, permitting a speedup of an order of magnitude for many algorithms in the literature for such variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.
Rights: Copyright © SIAM. This paper is made available with permission of the Society for Industrial and Applied Mathematics for limited noncommerical distribution only.
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
gener.pdf400KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.