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

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

• Are you familiar with Huffman codes? – dkaeae Jan 4 at 18:46
• @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. – wizzwizz4 Jan 4 at 19:54
• 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". – greybeard Jan 5 at 12:02