Data regression

Numerical Recipes in C, Chapter 3 Interpolation and Extrapolation and Chapter 15 Modeling of Data
(Numerical Recipes is a really nice Book...)

Interpolation (Wikipedia)
Lagrange Interpolating Polynomial (Mathworld)
Regression Analysis (Wikipedia)
...
If you write what exactly you trying to do maybe I could help you with more specific information.

I've yet to spend much time looking at your links (thanks), but I'll post a more specific description of what I'm attempting to do.

Some time ago I got the idea that a file is essentially a really really big number, nothing more. I also noticed that certain equations in math would produce rather large numbers themselves (think quadratic equation which returns numbers that the calculator has to write in scientific notation).
So I got to thinking that I could compress a file by representing it as an equation (probably a rather high order one) and an input (x) for that equation.
I don't think that this will be a very efficient form of compression, if at all; but I'm just messing around with it anyway.

Quote:

Original post by luke2 So I got to thinking that I could compress a file by representing it as an equation (probably a rather high order one) and an input (x) for that equation. I don't think that this will be a very efficient form of compression, if at all; but I'm just messing around with it anyway.

I think this is only applicable to lossy compression. See:
http://www.dogma.net/markn/FAQ.html#Q19

Actually, this will be quite a difficult form of compression to implement, if you aim to interpolate the data set, as you say.

Any entire polynomial or non-cardinal interpolant will have huge coefficients when the data set gets even moderately large. The resulting calculation will be way out of the reach of 32- or 64- bit integer arithmetic, and would be plagued by inaccuracy for floating-point arithmetic.

Localised interpolants would sidestep the magnitude problem, but you'll find that you need more data to represent the spline than the set you're trying to 'compress'.

Understand the difference between regression and interpolation. Regression produces a 'best fit' curve, whereas interpolation produces an 'exact fit' curve. The latter is barely workable in this context. The former is exactly what current lossy compression algorithms do. I suggest you take a look at SVD to see what representation-based matrix compression procedures typically look like.

Admiral

OK. You can produce a number like pi=3,1415926… just by calculating 4*arctan(1) so if a file some representation of pi you can compress it as “4*arctan(1)”. Or you can represent 2,5,10,17,… as f(x=1,2,3,…)=x^2+1 But generally you will not able to find a formula that is smaller than the data itself. If you want to experiment with large numbers you can use a library like apfloat (as I remember it includes a BigInt class too).
http://www.apfloat.org/

I do not know how much you know about compression algorithm but understanding some algorithms like Huffman coding and LZW could help you a lot developing your own algorithm.
Huffman coding
LZW (Lempel-Ziv-Welch)
Maybe you will find this interesting: Self-information

If your compression algorithm starts out with "consider a file as a really big number", you're already setting yourself up for failure. Compression exploits structure, and by waving away patterns in the bitstream into an arbitrary scalar representation you get rid of structure.

The string "ABAB"? pretty darn structured. The number 1094861122? Less so.

>The string "ABAB"? pretty darn structured.
Just sort the letters to AABB... that has even greater potential for compression
(look up "Move-To-Front" - if I remember it correctly).

Quote:

Original post by Sneftel If your compression algorithm starts out with "consider a file as a really big number", you're already setting yourself up for failure. Compression exploits structure, and by waving away patterns in the bitstream into an arbitrary scalar representation you get rid of structure. The string "ABAB"? pretty darn structured. The number 1094861122? Less so.

A different form of representation does not make it any less or more structured, in a sense that both can be compressed equally well. In the case that you have four letter strings consisting of only A and B, it very well might be the case that your example is the less structured of them all. This all depends on context. If the four letter string is part of a english document, "BABA" is probably much more common than "ABAB" and thus should be compressed with less bits than "ABAB" (assuming both are distinct words). Here structure is defined wrt. the context as attainable compression as IMHO it should be

If on the other hand, "ABAB" is all there is, and a compression algorithm has to determine the context (in this case, probability of each symbol), then for some algorithms "ABAB" is as structured as "AABB" because all the symbols are equally frequent (first order entropy). In fact, all the other four letter strings consisting of two symbols (A,B) would be equally or more structured. Again, structure defined as attainable compression.

[Edited by - Winograd on February 25, 2007 11:27:26 PM]

Whoops, above poster was me >_<

Data compression is based on modeling the data set in such a way as to make very good predictions about the next symbol based on the stream of previous symbols already encountered. Some algorithms are so blunt that they use single bits as the fundamental input alphabet (so if we predict a '1' and are told we are wrong, then it must be a '0' .. and vise-versa .. no need for escape codes in the compressed stream.)

Considering an *uncompressed* stream as a big abstract value is not going to be very helpful. OTOH, considering a *compressed* stream as one is VERY helpful (see Arithmetic Coding or Range Coding) and this strategy is used by all of the best (ratio) compressors.