The Generalized Prediction Encoder
A Universally Optimal Encoder
The Generalized Prediction Encoder (GPE) is defined as follows:
For each symbol, in some specific order:
- Predict probabilities for each possible symbol based on previous symbols.
- Encode actual symbol using predicted probabilities.
Note that the symbol size has not been defined, and may even be variable.
The GPE can be used to at least tie any given encoder.
Proof:
The representation of a symbol using any encoder is entirely dependant on that encoder's internal state.
The internal state is entirely dependant on the previously encoded symbols.
Therefore, (1) the representation of a symbol using any encoder is entirely dependant on the previously encoded symbols.
Any representation of a symbol can be at least tied by an arithmetic encoder with an appropriate probability distribution.
This distribution is the implicit probability distribution associated with that representation.
Thus, by (1), (2) The implicit probability distribution for the encoding of a symbol using any encoder is entirely dependant on the previously encoded symbols.
The implicit probability distribution for the representation of a symbol is simply the current state of the implicit probability model of the encoder.
Thus, by plugging the implicit probability model of any encoder into the GPE, the GPE becomes the encoder.
Therefore, (3) With an appropriate probability model, any encoder can be at least tied by the GPE.
There exists no encoder more efficient than the GPE.
Proof:
Assume there exists an encoder more efficient than the GPE.
Then, (4) This encoder can not be tied by the GPE.
By (3), the GPE can at least tie this encoder.
Therefore (4) is false by contradiction.
Therefore There exists no encoder more efficient than the GPE.