# Minimal encoding of a set (unordered collection of elements)?

Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$.

If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are needed.

I'd like to be able to have a "Set" data structure, which take advantage of the fact that the set is unordered to save memory.

It seems that theoretically (information bound), we could only use $k\log \frac{|\mathcal{U}|}{k}$ bits for encoding the set, but I was wondering if such result is known.

I considered looking into implementations of current set structures in popular programming languages, but assumed they'll be more optimized for runtime rather than memory, so my questions are:

• Is there a known data structure that allows storing $k$ elements set using $k\log \frac{|\mathcal{U}|}{k} + O(1)$ bits (supporting adding and deleting items of course)?

• What is the best runtime of such structure?

I'm well aware we could probably save some memory by hashing (if $k << \mathcal{U}$), but I'm looking for a deterministic structure.

• Could you just use arithmetic coding? – Zsbán Ambrus Jun 13 '14 at 14:59
• @ZsbánAmbrus - I'm not sure I follow. Doesn't arithmetic coding encodes ordered words? How can I use it to encode an unordered set of letters without having to save the additional bits required for saving the order? – R B Jun 13 '14 at 15:49
• You can implement the information-theoretic optimum by listing out (or computing) all ${n \choose k}$ possible subsets of length $k$ and giving each a binary encoding of $\log {n \choose k} \in O(k \log \frac{n}{k} )$ bits. – Ari Trachtenberg Jun 13 '14 at 19:56
• @AriTrachtenberg - can you do that and support insertion/deletion/lookup in time depending only on $k$? – R B Jun 13 '14 at 19:59
• @R B - Insertion / deletion of set elements or into the universal set? The problem didn't say anything about the running time of insertions/deletions. – Ari Trachtenberg Jun 13 '14 at 20:14

You can implement the information-theoretic optimum by listing out (or computing) all ${n \choose k}$ possible subsets of length $k$ and giving each a binary encoding of $log{n \choose k} \in O(k \, log \frac{n}{k})$ bits.
What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [insert, delete, lookup] operations in the worst case with high probability" while using $B + o(B)$ bits, where $B$ is the lower bound you mention.
If you need updates, I don't know if you'll be able to beat $O\left(\sqrt{B}\right)$ redundancy, given the lower bounds in Brodnik et al.'s "Resizable Arrays in Optimal Time and Space".
• Thanks for the answer. While this gets close, they still sacrifice space optimality for $O(1)$ worst case runtime. I'm hoping for a data structure which is first optimal by memory consumption (even if it means $O(k)$ time per operation). I'll accept the answer in a few days if no one comes up with a smaller structure (this $o(B)$ could be costly for my purpose). – R B Jun 13 '14 at 8:54