Timeline for Minimal encoding of a set (unordered collection of elements)?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 30, 2014 at 12:45 | vote | accept | R B | ||
| Jun 13, 2014 at 23:44 | answer | added | Ari Trachtenberg | timeline score: 0 | |
| Jun 13, 2014 at 20:26 | comment | added | R B | @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. | |
| Jun 13, 2014 at 20:14 | comment | added | Ari Trachtenberg | @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. | |
| Jun 13, 2014 at 19:59 | comment | added | R B | @AriTrachtenberg - can you do that and support insertion/deletion/lookup in time depending only on $k$? | |
| Jun 13, 2014 at 19:56 | comment | added | Ari Trachtenberg | 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. | |
| Jun 13, 2014 at 15:49 | comment | added | R B | @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? | |
| Jun 13, 2014 at 14:59 | comment | added | Zsbán Ambrus | Could you just use arithmetic coding? | |
| Jun 13, 2014 at 13:23 | history | tweeted | twitter.com/#!/StackCSTheory/status/477441191777017856 | ||
| Jun 13, 2014 at 0:16 | answer | added | jbapple | timeline score: 5 | |
| Jun 12, 2014 at 22:44 | history | asked | R B | CC BY-SA 3.0 |