1.Previous
3.Next

that there are distinct -subsets of (or binary strings of length with exactly 1's), and thus is an information theoretic lower bound on the number of bits needed to store . There is a succinct (static) dictionary which attains this bound, namely using space. This structure can be extended to support rank and select queries and takes space. Correct rank queries in this structure are however limited to elements contained in the set, analogous to how minimal perfect hashing functions work. This bound can be reduced to

1.Previous
3.Next