Does the Shannon bound really apply to all data structures?; pp. 47–58Full article in PDF format | doi: 10.3176/proc.2013.1.06
Shannon’s information-theoretic lower bound has been developed for uniquely decodable systems of bit strings, while ordinary data structures often consist of many separate blocks of memory. One might expect that adapting the bound to data structures is trivial, but we demonstrate that this is not the case. Kraft’s inequality is at the heart of information-theoretic lower bound proofs. We present a tiny distributed data structure where Kraft’s inequality fails, or it is at least very difficult to give any other satisfactory explanation. Then we formalize the concept of data structure with the notion of “representation scheme” that is general enough to model the example system. We re-establish the information-theoretic lower bound by proving that Kraft’s inequality applies to a subset of representation schemes that contains at least one memory-optimal scheme for each set of objects. Unlike in classical information theory, a representation scheme may be memory-optimal even if some object has more than one representation. However, this only happens if some representation has probability zero.
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 2nd edition. The MIT Press, 2001.
2. Foldes, S. On McMillan’s theorem about uniquely decipherable codes. arXiv:0806.3277v2, 2008.
3. Karush, J. A simple proof of an inequality of McMillan. IRE Trans. Inform. Theory, 1961, 7(2), 118.
4. Kraft, L. G. A Device for Quantizing, Grouping, and Coding Amplitude-Modulated Pulses. Master’s thesis, Massachusetts Institute of Technology, Cambridge, USA, 1949.
5. McMillan, B. Two inequalities implied by unique decipherability. IRE Trans. Inform. Theory, 1956, 2(4), 115–116.
6. Reingold, E. M. Algorithm design and analysis techniques. In Algorithms and Theory of Computation Handbook (Atallah, M. J., ed.). CRC Press, 1999.
7. Shannon, C. E. A mathematical theory of communication. Bell System Techn. J., 1948, 27(3), 379–423 and 27(4), 623–656.8. Valmari, A. What the small Rubik’s cube taught me about data structures, information theory and randomisation. STTT, 2006, 8(3), 180–194.
Back to Issue