World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ALGORITHMS FOR CONSTRUCTION OF OPTIMAL AND ALMOST-OPTIMAL LENGTH-RESTRICTED CODES

    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

    • A. Aggarwal, B. Schieber and T. Tokuyama, Journal on Discrete & Computational Geometry 12, 263 (1994). Crossref, ISIGoogle Scholar
    • P. Berman, M. Karpinski and Y. Nekritch, Approximating Huffman Codes in Parallel, Proc. 29th ICALP (2002) pp. 845–855. Google Scholar
    • M. Buro, Information Processing Letters 45, 219 (1993). Crossref, ISIGoogle Scholar
    • M. Garey, SIAM Journal on Computing 3, 101 (1974). CrossrefGoogle 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
    • R. Güttler, K. Mehlhorn and W. Schneider, 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
    • D. Kirkpatrick and T. Przytycka, Algorithmica 172 (1996). Google Scholar
    • L. Larmore, SIAM Journal on Computing 16, 1115 (1987). Crossref, ISIGoogle Scholar
    • L. Larmore and D. Hirschberg, Journal of the ACM 37(3), 464 (1990). Crossref, ISIGoogle 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
    • L. Larmore and T. Przytycka, SIAM Journal on Computing 24(6), 1163 (1995). Crossref, ISIGoogle Scholar
    • M. Liddell and A. Moffat, Incremental Calculation of Minimum-Redundancy Length-Restricted Codes, Proc. Data Compression Conference (2002) pp. 182–191. Google Scholar
    • K. Mehlhorn, IEEE Trans. Inf. Theory 26, 513 (1980). Crossref, ISIGoogle Scholar
    • A. Moffat and J. Katajainen, In-Place Calculation of Minimum-Redundancy Codes, Proc. WADS (1995) pp. 393–402. Google Scholar
    • R. 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 Scholar
    • R. 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 Scholar
    • R. 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 Scholar
    • B. 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 Scholar
    • J. van Leeuwen, On the construction of Huffman trees, Proc. 3rd Int. Colloquium on Automata, Languages and Programming (1976) pp. 382–410. Google Scholar