Compression : News Postings : General Prediction

11-6-95

It is well known that Markov-Modelling compression algorithms can
also be used for prediction.  However, this result is also true
of all compression algorithms.

In prediction, the goal is to use the preceeding set of data, S,
to guess the probability that the next character will be n,
(where 0 <= n < N).

Let Si = S + i ( where + denotes string concatenation)

let C(X) be a reversible transform (aka a compressor).
let L(C(X)) be the length of the output of C(X)

let Li = L(C(S+i))

let DiffLi = Li - L(C(S))

if ( DiffLi <= 0 for any i, this method does not apply )
	( DiffLi == 0 is imaginable, DiffLi < 0 is strange )

now PP(S,i) = 2^( - DiffLi)

PP(S,i) = Predicted_Probability of i following S

--

for example : let C(X) be an order-0 statistical compressor.

Then Li = L(C(S+i)) = L(C(S)) + L(C(i))

and L(C(i)) = - log2( P(i) )

so DiffLi = -log2( P(i) )

then PP(S,i) = 2^( -DiffLi ) = 2^( log2( P(i) ) ) = P(i)

!!

The example of a high-order markov modeller is similar.

---

the advantage of this definition of PP(S,i) is that it
is totally general, and proves that compression and
prediction are equivalent in all cases.

Back to the Index