Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How can compretion be possible?

  1. Jun 3, 2009 #1
    How can compretion be possible???

    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!
     
  2. jcsd
  3. Jun 3, 2009 #2

    sylas

    User Avatar
    Science Advisor

    Re: How can compretion be possible???

    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.
     
  4. Jun 3, 2009 #3
    Re: How can compretion be possible???

    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
     
  5. Jun 3, 2009 #4

    sylas

    User Avatar
    Science Advisor

    Re: How can compretion be possible???

    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.
     
  6. Jun 3, 2009 #5

    mgb_phys

    User Avatar
    Science Advisor
    Homework Helper

    Re: How can compretion be possible???

    I have an excellent algorithm that compresses any input into a single bit.
    Unfortunately I haven't written the decompression algorithm yet.
     
  7. Jun 3, 2009 #6
    Re: How can compretion be possible???

    "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.
     
  8. Jun 3, 2009 #7
    Re: How can compretion be possible???

    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.
     
  9. Jun 4, 2009 #8
    Re: How can compretion be possible???

    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
     
  10. Jun 4, 2009 #9

    sylas

    User Avatar
    Science Advisor

    Re: How can compretion be possible???

    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.
     
  11. Jun 7, 2009 #10
  12. Jun 8, 2009 #11

    rcgldr

    User Avatar
    Homework Helper

    Re: How can compretion be possible???

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How can compretion be possible?
  1. How can I code this? (Replies: 1)

  2. How i can learn ? (Replies: 16)

Loading...