(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.
unit
s in 7byte
s 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