<p>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.</p>

CC BY-SA 3.0
2014-06-14T00:54:06.747Z
Moreover, you can do it efficiently using "binomial encoding", described in several answers on this site and cs.se.
Yuval Filmus
CC BY-SA 3.0
2014-06-15T18:56:53.133Z
What you need is a constant-weight code (ideally perfect).  See also http://cstheory.stackexchange.com/questions/19313/optimal-encoding-of-k-subsets-of-n.
Ari Trachtenberg
CC BY-SA 3.0
2014-06-13T23:44:36.407Z
2014-06-13T23:44:36.407Z
Ari Trachtenberg
<p>What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is <a href="http://arxiv.org/abs/0912.5424" rel="nofollow">Backyard cuckoo hashing, by Arbitman et al from FOCS 2010</a>, 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.</p>

<p>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 <a href="http://erikdemaine.org/papers/ResizableArraysTR/" rel="nofollow">Brodnik et al.'s "Resizable Arrays in Optimal Time and Space"</a>.</p>

CC BY-SA 3.0
2014-06-13T08:54:12.907Z
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
CC BY-SA 3.0
2014-06-13T00:16:43.723Z
2014-06-13T13:41:14.647Z
2014-06-13T13:41:14.647Z
jbapple
<p>Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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:</p>

<ul>
<li><p><strong>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)?</strong></p></li>
<li><p><strong>What is the best runtime of such structure?</strong></p></li>
</ul>

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

CC BY-SA 3.0
2014-06-13T14:59:52.430Z
Could you just use arithmetic coding?
Zsbán Ambrus
CC BY-SA 3.0
2014-06-13T15:49:57.320Z
@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
CC BY-SA 3.0
2014-06-13T19:56:09.220Z
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
CC BY-SA 3.0
2014-06-13T19:59:41.227Z
@AriTrachtenberg - can you do that and support insertion/deletion/lookup in time depending only on $k$?
R B
CC BY-SA 3.0
2014-06-13T20:14:39.853Z
@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
CC BY-SA 3.0
2014-06-13T20:26:16.407Z
@AriTrachtenberg - you are correct that the problem didn't say anything about it, but I was wondering if it's possible. What is the possible runtime of adding/deleting items in your suggestion? Do you think it's possible to assign the enumeration encoding such that operations will be doable in $O(k)$ time?

By the way, you can write your previous comment as an answer, and we can have this discussion in its comments.
R B
<ds.algorithms><ds.data-structures><space-bounded><encoding>
Minimal encoding of a set (unordered collection of elements)?
R B
# Minimal encoding of a set (unordered collection of elements)?

(Asked by: username_0 on 2014-06-12)

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.

**Tags:** ds.algorithms, ds.data-structures, space-bounded, encoding
> **Comments:**
> **username_1**: Could you just use arithmetic coding?  
> **username_0**: @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?  
> **username_2**: 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.  
> **username_0**: @AriTrachtenberg - can you do that and support insertion/deletion/lookup in time depending only on $k$?  
> **username_2**: @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.  
> **username_0**: @AriTrachtenberg - you are correct that the problem didn't say anything about it, but I was wondering if it's possible. What is the possible runtime of adding/deleting items in your suggestion? Do you think it's possible to assign the enumeration encoding such that operations will be doable in $O(k)$ time?  By the way, you can write your previous comment as an answer, and we can have this discussion in its comments.  

---

## 2 answers

### Answer by username_2 on 2014-06-13. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_3**: Moreover, you can do it efficiently using "binomial encoding", described in several answers on this site and cs.se.  
> **username_2**: What you need is a constant-weight code (ideally perfect).  See also http://cstheory.stackexchange.com/questions/19313/optimal-encoding-of-k-subsets-of-n.  

---

### Answer by username_4 on 2014-06-13. Score: 5

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](http://arxiv.org/abs/0912.5424), 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"](http://erikdemaine.org/papers/ResizableArraysTR/).

> **Comments:**
> **username_0**: 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).  

---

