Dynamic Shannon Coding

Preprint English OPEN
Gagie, Travis (2005)
  • Subject: Computer Science - Information Theory | E.4
    acm: Data_CODINGANDINFORMATIONTHEORY

We present a new algorithm for dynamic prefix-free coding, based on Shannon coding. We give a simple analysis and prove a better upper bound on the length of the encoding produced than the corresponding bound for dynamic Huffman coding. We show how our algorithm can be modified for efficient length-restricted coding, alphabetic coding and coding with unequal letter costs.
  • References (17)
    17 references, page 1 of 2

    [1] C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, 1948.

    [2] D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proceedings of the IERE, vol. 40, pp. 1098-1101, 1952.

    [3] R. De Prisco and A. De Santis, “On the redundancy achieved by Huffman codes,” Information Sciences, vol. 88, pp. 131-148, 1996.

    [4] M. Golumbic, “Combinatorial merging,” IEEE Transactions on Computers, vol. 24, pp. 1164-1167, 1976.

    [5] N. Faller, “An adaptive system for data compression,” in Proceedings of the 7th Asilomar Conference on Circuits, Systems, and Computers, 1973, pp. 593-597.

    [6] R. G. Gallager, “Variations on a theme by Huffman,” IEEE Transactions on Information Theory, vol. 24, pp. 668-674, 1978.

    [7] D. E. Knuth, “Dynamic Huffman coding,” Journal of Algorithms, vol. 6, pp. 163-180, 1985.

    [8] R. L. Milidiu´, E. S. Laber, and A. A. Pessoa, “Bounding the compression loss of the FGK algorithm,” Journal of Algorithms, vol. 32, pp. 195-211, 1999.

    [9] J. S. Vitter, “Design and analysis of dynamic Huffman codes,” Journal of the ACM, vol. 34, pp. 825-845, 1987.

    [10] T. Gagie, “Dynamic length-restricted coding,” Master's thesis, University of Toronto, 2003.

  • Metrics
    No metrics available
Share - Bookmark