Databases
StackOverflow2013
Postsdbo
POMost compact way to encode a sequence of random variable length binary codes?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMost compact way to encode a sequence of random variable length binary codes?
    text
    copied!<p>Let's say you have a <code>List&lt;List&lt;Boolean&gt;&gt;</code> and you want to encode that into binary form in the most compact way possible.</p> <p>I don't care about read or write performance. I just want to use the minimal amount of space. Also, the example is in Java, but we are not limited to the Java system. The length of each "List" is <strong>unbounded</strong>. Therefore any solution that encodes the length of each list must in itself encode a variable length data type.</p> <p>Related to this problem is encoding of variable length integers. You can think of each <code>List&lt;Boolean&gt;</code> as a variable length <code>unsigned integer</code>.</p> <p><strong>Please read the question carefully. We are not limited to the Java system.</strong></p> <p>EDIT</p> <p>I don't understand why a lot of the answers talk about compression. I am not trying to do compression per se, but just encoding <em>random</em> sequence of bits down. Except each sequence of bits are of different lengths and order needs to be preserved.</p> <p><strong>You can think of this question in a different way. Lets say you have a list of arbitrary list of random unsigned integers (unbounded). How do you encode this list in a binary file?</strong></p> <h2>Research</h2> <p>I did some reading and found what I really am looking for is <a href="http://en.wikipedia.org/wiki/Universal_code_%28data_compression%29" rel="noreferrer">Universal code</a></p> <h2>Result</h2> <p>I am going to use a variant of <a href="http://en.wikipedia.org/wiki/Elias_omega_coding" rel="noreferrer">Elias Omega Coding</a> described in the paper <a href="http://hirosuke.it.k.u-tokyo.ac.jp/files/ABST/Y2000.html" rel="noreferrer">A new recursive universal code of the positive integers</a></p> <p>I now understand how the smaller the representation of the smaller integers is a trade off with the larger integers. By simply choosing an Universal code with a "large" representation of the very first integer you save a lot of space in the long run when you need to encode the arbitrary large integers.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload