Is there an algorithm to achieve optimal compression in a “streamed” manner, assuming equal probability of each possibility?

Question

^{(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.

Answer 1

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.