Suggest a method for statistical data compression

Question

There's a lot of work done in statistics, while state-of-art in lossless data compression is apparently this: http://mattmahoney.net/dc/dce.html#Section_4

Please suggest good methods/models applicable for data compression. To be specific:
1) How to estimate the probability of the next bit in a bit string?
2) How to integrate predictions of different models?

Update:

you should include a better description of what data you want to compress...

Why, I'm talking about universal compression obviously. For data with known structure its really not a mathematical problem, so there's no sense to discuss it here. In other words, the first question is: given a string of bits, what do we do to determine the probability of the next bit, as precisely as possible?

otherwise we will have 10 different answers trying to summarize different part of the huge theory of compression

I'd written quite a few statistical compressors, and I'm not interested in that. I'm asking how a statistician would approach this task, detect correlations in given data, and compute a probability estimation for the next bit.

In addition, the two point you give to be more specific are not detailed enough to be understood.

What's not detailed in there? I'm even talking about bits, not some vague "symbols". I'd note though, that I'm talking about "probability of a bit" because computing a probability of bit==0 or bit==1 is a matter of convenience.

Also, I'm obviously not talking about some "random data compression", or methods with infinite complexity, like "Kolmogorov compression". Again, I want to know how a good statistician would approach this problem, given a string of bits.

Here's an example, if you need one: hxxp://encode.ru/threads/482-Bit-guessing-game

Answer 1

Interesting question! All statistical models can be viewed as performing lossy data compression. For instance simple linear regression with one predictor replaces $N$ points (where $N$ can be massive, e.g., in the 1000s) with two parameters: a slope and intercept. The parameters may then be used to reconstruct the data, with degree of success depending on how good the original fit was.

Your specific example concerns predicting binary time series data (Bernoulli distributed data, which is a specific case of the binomial distribution). Binary data can encode a lot: coin flips, pictures, sounds, the digits of $\pi$, statistical programming languages...

As you can imagine, and as a quick search around Google will confirm, there are a lot of statistical models which could apply to binary data. One is logistic regression, or (to express the same model in a more general framework) a Generalized Linear Model with a binomial distribution and a logit link function. The function fit is of the following form: $\mbox{logit}[P(Y)] = \beta X + \epsilon$, where $X$ (predictors), $Y$ (probability of a 1), and $\epsilon$ (residuals) are vectors.

Okay. Now a little demonstration. Suppose data are generated so that the probability of a 1 correlates with the sine of time (represented as black points in the graph below). You don't know this, however. You get data for time points from 0 to 359 (blue points).

alt text http://img196.imageshack.us/img196/589/cointimepredict2.png

With the available data points, I fitted the function $\mbox{logit}[P(Y)] = \beta_0 + \beta_1 t + \beta_2 t^2 + \beta_3 t^3$, which popped out as $\mbox{logit}[P(Y)] = -0.2 -30.9 t -3.1 t^2 + 22.2 t^3$. (The probability predictions are plotted in red.) It's a good fit to the data (between 0 and 359). However as you can see, when extrapolating, it does a rather poor job: beyond a certain point it says "just guess 1!"

Take-home message: to do the analysis correctly, you need to have a some idea of the likely processes generating the data. If I knew a sine process were doing the job, then I'd be able to do a wonderful job predicting. Thinking about this is where a statistician would start. The appropriate model is always going to be domain specific, which is why, for example, compression techniques working well for images don't automatically apply to sounds.

Answer 2

So, here's the example: http://nishi.dreamhosters.com/u/book1bwt_de.txt

Its a list of choices between 'd' and 'e' in coding of BWT output of a plaintext book. (This is a practical task, think bzip2). For the reference, current result is (reasonably good, but not really the best possible) 6087 bytes = 48686 bits (ie log-likelihood) for that string of 99054 bits