How can compretion be possible?

  • Thread starter Thread starter prysdieheer
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the concept of data compression, specifically questioning how compression is possible given the limitations of integer storage capacity. Participants explore various aspects of compression algorithms, their effectiveness, and the theoretical limits of repeated compression.

Discussion Character

  • Exploratory
  • Debate/contested
  • Technical explanation

Main Points Raised

  • One participant questions the feasibility of compression, noting that a 64-bit integer can store 2^64 combinations while a 63-bit integer can store 2^63, suggesting a paradox in compressing data.
  • Another participant acknowledges that while compression algorithms can increase the size of certain inputs, they are effective for specific types of data.
  • A participant proposes the idea of an algorithm that could compress data repeatedly, although another later asserts that no algorithm can compress data indefinitely without loss of information.
  • Examples of practical compression techniques are provided, such as using lookup tables for words, encoding binary strings more efficiently, and compressing audio files by representing them with fewer parameters.
  • Some participants humorously claim to have invented algorithms that compress data to extreme extents, though they acknowledge the lack of a decompression method.
  • A participant discusses the theoretical basis of compression, emphasizing that practical usage often involves fewer distinct values than theoretically possible, allowing for effective compression strategies.
  • Another participant mentions existing compression algorithms that optimize data encoding through iterative schemes, referencing methods like Huffman coding and LZ compression.

Areas of Agreement / Disagreement

Participants express differing views on the possibility of repeated compression, with some asserting it is not feasible while others suggest it might be achievable under certain conditions. The discussion remains unresolved regarding the effectiveness and limits of compression algorithms.

Contextual Notes

Participants highlight the dependence of compression effectiveness on the nature of the data being compressed and the assumptions made about input characteristics. There are unresolved questions about the theoretical limits of compression and the conditions under which certain algorithms may perform better.

prysdieheer
Messages
10
Reaction score
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!
 
Technology news on Phys.org


prysdieheer said:
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.
 


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
 


prysdieheer said:
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.
 


prysdieheer said:
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.
 


"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.
 


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 occurring characters with longer bit strings and vice versa, so it all works out in the end.
 


prysdieheer said:
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
 


mgb_phys said:
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.
 
  • #11


sylas said:
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.
 

Similar threads

Factoring polynomials with finite field coeffcients
  • · Replies 3 ·
Replies
3
Views
1K
MHB Computer system : Clarification needed
  • · Replies 32 ·
2
Replies
32
Views
2K
How Can We Efficiently Parallelize the N-Queens Problem?
  • · Replies 11 ·
Replies
11
Views
5K
Combinations Formulae & Mapping to Index Values
  • · Replies 6 ·
Replies
6
Views
2K
Python How does Python tell that an integer is actually an integer?
  • · Replies 47 ·
2
Replies
47
Views
4K
Solve the problem involving probability density function
  • · Replies 8 ·
Replies
8
Views
2K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
Program to find combination of letters associated with phone
  • · Replies 3 ·
Replies
3
Views
2K
Graduate "The Operation Combination Problem"
  • · Replies 2 ·
Replies
2
Views
2K
Making The Best Use Of RAM In Windows
  • · Replies 2 ·
Replies
2
Views
3K