title: Compressing a vector of positive integers (int32) that have a specific order
body: <p>I'm trying to compress long vectors (their size ranges from 1 to 100 million elements). The vectors have positive integers with values ranging from 0 to 1 or 100 million (depending on the vector size). Hence, I'm using 32 bit integers to encompass the large numbers but that consumes too much storage.
  The vectors have the following characteristic features:</p>
  <ol>
  <li>All values are positive integers. Their range grows as the vector size grows.</li>
  <li>Values are increasing but smaller numbers do intervene frequently (see the figure below).</li>
  <li>None of the values before a specific index are larger than that index (Index starts at zero). For instance, none of the values that occur before the index of 6 are larger than 6. However, smaller values may repeat after that index. This holds true for the entire array.</li>
  <li>I'm usually dealing with very long arrays. Hence, as the array length passes 1 million elements, the upcoming numbers are mostly large numbers mixed with previous reoccurring numbers. Shorter numbers usually re-occur more than larger numbers. New Larger numbers are added to the array as you pass through it.</li>
  </ol>
  <p>Here is a sample of the values in the array: {initial padding..., 0, 1, 2, 3, 4, 5, 6, 4, 7, 4, 8, 9, 1, 10, ... later..., 1110, 11, 1597, 1545, 1392, 326, 1371, 1788, 541,...}</p>
  <p>Here is a plot of a part of the vector:
  <a href="https://i.stack.imgur.com/9EkWD.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/9EkWD.jpg" alt="Here is a plot of a part of the vector:" /></a></p>
  <p><strong>What do I want?</strong> :
  Because I'm using 32 bit integers this is wasting a lot of memory since smaller numbers that can be represented with less than 32 bit do repeat too. I want to compress this vector maximally to save memory (Ideally, by a factor of 3 because only a reduction by that amount or more will meet our needs!). What is the best compression algorithm to achieve that? Or is there away to take advantage of the array's characteristic features described above to reversibly convert the numbers in that array to 8 bit integers?</p>
  <p><strong>Things that I have tried or considered</strong>:</p>
  <ol>
  <li>Delta encoding: This doesn't work here because the vector is not always increasing.</li>
  <li>Huffman coding: Does not seem to help here since the range of unique numbers in the array is quite large, hence, the encoding table will be a large overhead.</li>
  <li>Using variable Int encoding. i.e using 8 bit integers for smaller numbers and 16 bit for larger ones...etc. This has reduced the vector size to size*0.7 (not satisfactory since it doesn't take advantage of the specific characteristics described above)</li>
  <li>I'm not quite sure if this method described in the following link is applicable to my data: <a href="http://ygdes.com/ddj-3r/ddj-3r_compact.html" rel="noreferrer">http://ygdes.com/ddj-3r/ddj-3r_compact.html</a>
  I don't quite understand the method but it gives me the encouragement to try similar things because I think there is some order in the data that can be taken to its advantage.
  For example, I tried to reassign any number(n) larger than 255 to n-255 so that I can keep the integers in 8 bit realm because I know that no number is larger than 255 before that index. However, I'm not able to distinguish the reassigned numbers with the repeated numbers... so this idea doesn't work unless doing some more tricks to reverse the re-assignments...</li>
  </ol>
  <p>Here is the link to the fist 24000 elements of the data for those interested:
  <a href="https://drive.google.com/file/d/1vIUt75A1mer2Mmz3CBYvc7wGr4SvaBwf/view?usp=sharing" rel="noreferrer">data</a></p>
  <p>Any advice or suggestions are deeply appreciated. Thanks a lot in advance.</p>
  <p><strong>Edit1:</strong></p>
  <p>Here is a plot of the data after delta encoding. As you can see, it doesn't reduce the range!
  <a href="https://i.stack.imgur.com/uDxF8.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/uDxF8.jpg" alt="delta encoded" /></a></p>
  <p><strong>Edit2:</strong></p>
  <p>I was hoping that I could find a pattern in the data that allows me to reversibly change the 32-bit vector to a single 8-bit vector but this seems very unlikely.
  I have tried to decompose the 32-bit vector to 4 x 8-bit vectors, hoping that the decomposed vectors lend themselves to compression better.
  Below are plots for the 4 vectors. Now their ranges are from 0-255.
  What I did was to recursively divide each element in the vectors by 255 and store the reminder into another vector. To reconstruct the original array all I need to do is: ( ( (vec4*255) + vec3 )*255 + vec2 ) *255 + vec1...</p>
  <p><a href="https://i.stack.imgur.com/Du3wz.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/Du3wz.jpg" alt="decomposed arrays" /></a></p>
  <p>As you can see, the last vector is all zeros for the current shown length of the data.. in fact, this should be zeros all the way to 2^24th element. This will be a 25% reduction if my total vector length was less than 16 million elements but since I'm dealing with much longer vectors this has a much smaller impact.
  More importantly, the third vector seems also to have some compressible features as its values do increase by 1 after each 65,535 steps.
  It does seem that now I can benefit from Huffman coding or variable bit encoding as suggested. Any suggestions that allows me to maximally compress this data are deeply appreciated.
  Here I attached a bigger sample of the data if anyone is interested:</p>
  <p><a href="https://drive.google.com/file/d/10wO3-1j3NkQbaKTcr0nl55bOH9P-G1Uu/view?usp=sharing" rel="noreferrer">https://drive.google.com/file/d/10wO3-1j3NkQbaKTcr0nl55bOH9P-G1Uu/view?usp=sharing</a></p>
  <p><strong>Edit3:</strong></p>
  <p>I'm really thankful for all the given answers. I've learnt a lot from them. For those of you who are interested to tinker with a larger set of the data the following link has 11 million elements of a similar dataset  (zipped 33MB)</p>
  <p><a href="https://drive.google.com/file/d/1Aohfu6II6OdN-CqnDll7DeHPgEDLMPjP/view" rel="noreferrer">https://drive.google.com/file/d/1Aohfu6II6OdN-CqnDll7DeHPgEDLMPjP/view</a></p>
  <p>Once you unzip the data, you can use the following C++ snippet to read the data into a vector&lt;int32_t&gt;</p>
  <pre><code>    const char* path = &quot;path_to\compression_int32.txt&quot;;
      std::vector&lt;int32_t&gt; newVector{};
      std::ifstream ifs(path, std::ios::in | std::ifstream::binary);
      std::istream_iterator&lt;int32_t&gt; iter{ ifs };
      std::istream_iterator&lt;int32_t&gt; end{};
      std::copy(iter, end, std::back_inserter(newVector));
  </code></pre>