ALGORITHMS FOR CONSTRUCTION OF OPTIMAL AND ALMOST-OPTIMAL LENGTH-RESTRICTED CODES
Abstract
In this paper we present new results on sequential and parallel construction of optimal and almost-optimal length-restricted prefix-free codes. We show that length-restricted prefix-free codes with error 1/nk for any k > 0 can be constructed in O(n log n) time, or in O(log n) time with n CREW processors. A length-restricted code with error 1/nk for any k ≤ L/ logΦ n, where
, can be constructed in O(log n) time with n/ log n CREW processors. We also describe an algorithm for the construction of optimal length-restricted codes with maximum codeword length L that works in O(L) time with n CREW processors.
A preliminary version of this paper appeared in the Proceedings of 2005 Data Compression Conference (DCC 2005)
References
- Journal on Discrete & Computational Geometry 12, 263 (1994). Crossref, ISI, Google Scholar
P. Berman , M. Karpinski and Y. Nekritch , Approximating Huffman Codes in Parallel, Proc. 29th ICALP (2002) pp. 845–855. Google Scholar- Information Processing Letters 45, 219 (1993). Crossref, ISI, Google Scholar
- SIAM Journal on Computing 3, 101 (1974). Crossref, Google Scholar
M. J. Golin , C. Kenyon and N. E. Young , Huffman coding with unequal letter costs, Proc. 34th STOC (2002) pp. 785–791. Google Scholar- Elektronische Informationsverarbeitung und Kybernetik 16, 41 (1980). Google Scholar
J. Katajainen , A. Moffat and A. Turpin , A Fast and Space-economical Algorithm for Length-Limited Coding, Proc. International Symposium on Algorithms and Computation (1995) pp. 12–21. Google Scholar- Algorithmica 172 (1996). Google Scholar
- SIAM Journal on Computing 16, 1115 (1987). Crossref, ISI, Google Scholar
- Journal of the ACM 37(3), 464 (1990). Crossref, ISI, Google Scholar
L. L. Larmore , T. Przytycka and W. Rytter , Parallel Construction of Optimal Alphabetic Trees, Proc. 5th ACM Symposium on Parallel Algorithms and Architectures (1993) pp. 214–223. Google Scholar- SIAM Journal on Computing 24(6), 1163 (1995). Crossref, ISI, Google Scholar
M. Liddell and A. Moffat , Incremental Calculation of Minimum-Redundancy Length-Restricted Codes, Proc. Data Compression Conference (2002) pp. 182–191. Google Scholar- IEEE Trans. Inf. Theory 26, 513 (1980). Crossref, ISI, Google Scholar
A. Moffat and J. Katajainen , In-Place Calculation of Minimum-Redundancy Codes, Proc. WADS (1995) pp. 393–402. Google ScholarR. L. Milidiu , A. A. Pessoa and E. S. Laber , In-Place Length-Restricted Prefix Coding, Proc. String Processing and Information Retrieval: A South American Symposium (1998) pp. 50–59. Google ScholarR. L. Milidiu , A. A. Pessoa and E. S. Laber , Efficient Implementation of the WARMUP Algorithm for the Construction of Length-Restricted Prefix Codes, Proc. ALENEX (1999) pp. 1–17. Google ScholarR. L. Milidiu , A. A. Pessoa and E. S. Laber , A Work Efficient Parallel Algorithm for Constructing Huffman Codes, Proc. Data Compression Conference (1999) pp. 277–286. Google ScholarB. Schieber , Computing a minimum-weight k-link path in graphs with concave Monge property, Proc. the 6th Annual Symposium on Discrete Algorithms (1995) pp. 405–411. Google ScholarJ. van Leeuwen , On the construction of Huffman trees, Proc. 3rd Int. Colloquium on Automata, Languages and Programming (1976) pp. 382–410. Google Scholar


