How can compretion be possible???

**prysdieheer** · Jun3-09, 07:36 PM

Since a 64bit integer can store 2^64 possible combinations and a 63bit integer can store 2^63 possible combinations and 64<63, how is it possible to compress anything?
::::::::::::::::::::::::::::::::::::::::::::

In love
Prys die Heer!

**sylas** · Jun3-09, 08:01 PM

Originally Posted by prysdieheer

Since a 64bit integer can store 2^64 possible combinations and a 63bit integer can store 2^63 possible combinations and 64<63, how is it possible to compress anything?
::::::::::::::::::::::::::::::::::::::::::::

In love
Prys die Heer!

Every compression algorithm actually increases the size of many inputs. They are useful because they decrease the size of the ones you are most likely to be using.

**prysdieheer** · Jun3-09, 08:22 PM

Thank You Sylas, that is a very good answer, really helps me.
But I have one more question, do you think it is possible to compress things over and over again, because I think I know an algorithm that can( It also makes a very good sorting algorithm)
::::::::::::::::::::::::::::
In Love
Ashton

**sylas** · Jun3-09, 09:16 PM

Originally Posted by prysdieheer

Thank You Sylas, that is a very good answer, really helps me.
But I have one more question, do you think it is possible to compress things over and over again, because I think I know an algorithm that can( It also makes a very good sorting algorithm)
::::::::::::::::::::::::::::
In Love
Ashton

If is a formal mathematical proof that there is no algorithm which compresses over and over again indefinitely. A good algorithm will normally (that is, on the inputs of interest) return a string that cannot be compressed a second time. If you have an algorithm that often compresses its input a second time, then the algorithm is not a good one for that class of inputs.

**mgb_phys** · Jun3-09, 10:07 PM

Originally Posted by prysdieheer

do you think it is possible to compress things over and over again, because I think I know an algorithm that can

I have an excellent algorithm that compresses any input into a single bit.
Unfortunately I haven't written the decompression algorithm yet.

**AUMathTutor** · Jun4-09, 12:49 AM

"I have an excellent algorithm that compresses any input into a single bit.
Unfortunately I haven't written the decompression algorithm yet."

I love you.

**AUMathTutor** · Jun4-09, 12:52 AM

To the OP:

The theory of compression is basically that, even though 2^64 different values are possible, in practice you use many fewer than these. If you're writing a letter in English, you probably use ~ 100 characters, tops. Also, some values occur more frequently than others. Using this information, you can replace frequently occuring characters with longer bit strings and vice versa, so it all works out in the end.

**junglebeast** · Jun4-09, 01:05 AM

Originally Posted by prysdieheer

Since a 64bit integer can store 2^64 possible combinations and a 63bit integer can store 2^63 possible combinations and 64<63, how is it possible to compress anything?
::::::::::::::::::::::::::::::::::::::::::::

In love
Prys die Heer!

Some examples:

Instead of sending a document as letters, you can replace each word with a single number and use a lookup table to reconstruct the message along with a dictionary.

What if I want to send the string "00101011". This has 8 numbers, each number represented by a byte. But since I only used 2 different possible numbers, it could all be encoded as bits in a single byte.

What if I want to send "5555555566666666666" I could send that as 19 numbers, or I could send "8.5.11.6" which represents 8 fives followed by 11 sixes.

An audio file is a sequence of numbers representing the magnitude of the combined waveform at each instant in time. If it remains a constant pitch, then this will look like a sine wave. If you just send the parameters of the sine wave, you don't need to send an infinite number of magnitude measurements.. a music file can be compressed by extracting a bunch of waves which, when added together, recreate the original music. The same thing is done in JPEG images, but with colors.

Compression uses these sorts of tactics

**sylas** · Jun4-09, 01:30 AM

Originally Posted by mgb_phys

I have an excellent algorithm that compresses any input into a single bit.
Unfortunately I haven't written the decompression algorithm yet.

I have an excellent algorithm that compresses any input to half its size. I wrote it on the margin of a book somewhere. Unfortunately, I have compressed all my books, and now the margins look like everything else, and I can't find the algorithm again.

**granpa** · Jun7-09, 11:58 PM

http://en.wikipedia.org/wiki/Arithmetic_coding

**Jeff Reid** · Jun8-09, 05:13 AM

Originally Posted by sylas

There is no algorithm which compresses over and over again indefinitely.

Perhaps he meant an algorithm that iterates thorugh various schemes to find an optimal compressed encoding of data. pkzip and later compression algortihms do this, such as a check to see if huffman encoding of 8 bit values (bytes) is beneficial (text files are good for this scheme), in addition to choosing a huffman encoding table for lengths and offsets using a moving window (LZ1 like) compression algorithm.