# 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? Jan 4, 2019 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. Jan 4, 2019 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". Jan 5, 2019 at 12:02

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.

• 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 Jan 5, 2019 at 12:11
• @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.
– orlp
Jan 5, 2019 at 12:19