title: Most compact way to encode a sequence of random variable length binary codes?
body: <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>