2
$\begingroup$

(Sorry for the question title; edits are welcome.)

Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ possibilities, $4$ possibilities, repeat. The total number of possibilities per unit is $2\times3\times5\times4=120\text{ possibilities}$. Assuming that these are all equally probable, that's $\log_2120\approx6.9\text{ bits}$. This means that the minimum space required to represent $1$ unit is $1\text{ Byte}$, but the minimum space required to represent $1000$ units is $864\text{B}$.

The naïve way of producing this compression would be to put them all into a base-120 number, then convert this to binary. However, this requires having access to all of the data at once in order to decompress it. There must[citation needed] be some algorithm that can take in a stream of compressed data, output a stream of decompressed data, and only use finite memory, but I can't find one.

Please describe and explain such an algorithm, if one exists.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Are you familiar with Huffman codes? $\endgroup$ – dkaeae Jan 4 '19 at 18:46
  • $\begingroup$ @dkaeae Yes, but that assumes a fixed number of symbols with variable probability. This has a variable number of symbols with a fixed probability... or at least a fixed number of symbols with a fixed probability. $\endgroup$ – wizzwizz4 Jan 4 '19 at 19:54
  • $\begingroup$ Consider just encoding 8 units in 7 bytes each, for a total of 875 bytes, a waste of 11 bytes or 12.6‰, but you gain "random access". $\endgroup$ – greybeard Jan 5 '19 at 12:02
2
$\begingroup$

However, this requires having access to all of the data at once in order to decompress it.

Not true. The trick is to compress backwards, from the last symbol, to the first. You do need all the data at once to compress though.

However, what you are looking for can be done with arithmetic coding, without even needing access to all of the data at once during compression.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I'm not quite sure how it can be done with arithmetic coding; after reading the Wikipedia article it seems to have this problem too $\endgroup$ – wizzwizz4 Jan 5 '19 at 12:11
  • 1
    $\begingroup$ @wizzwizz4 Arithmetic coding allows you to change the probability table for each symbol encoded. So for the first symbol you use a table with 2 probabilities, then one with 3, etc. $\endgroup$ – orlp Jan 5 '19 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.