Shannona€?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. Krafta€?s inequality is at the heart of information-theoretic lower bound proofs. We present a tiny distributed data structure where Krafta€?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 a€?representation schemea€? that is general enough to model the example system. We re-establish the information-theoretic lower bound by proving that Krafta€?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.
展开▼
