OK, write me a program that can compress an MP3 (of which the content is not known, so you don't cheat with some kind of index) to 4/5ths of it's current size. Prize will be... um... a free copy of my rendering engine, if I ever finish it or sell it.

Now THAT sounds like a good coding contest . I may give it a whirl when YPNgine is done (which will be in about a week ) As it is, I've been trying to figure out an algorithm to compress any file to half it's size (wouldn't be much good for little files )

_________________
When I got VB, I could have flown without thrusters and shot down TIE Interceptors just by spitting at them.

[ This Message was edited by: dxprog on 2003-09-13 05:37 ]

I might enter (not actually as a contestent, of course) to see when the deadline should be. Chances are mine won't work though...

Aye, now this sounds like a good contest!

Now here's a contest that's possible! [addsig]

It's not possible to compress any file to half its size.

It's also not possible to compress _any_ MP3 to a size smaller than the original. You might get good compression with most, but it's just fundamentally impossible to squeeze more information into some space than that space's bits can give you.

[ This Message was edited by: Smerdyakov on 2003-09-14 12:39 ]

Quote:
It's also not possible to compress _any_ MP3 to a size smaller than the original. You might get good compression with most, but it's just fundamentally impossible to squeeze more information into some space than that space's bits can give you.

You need to keep an open mind. Removing the headers in it self would do something. And I have a theory based on irrational numbers that's worth trying. True, not EVERY file can be compressed to a given size, but all MP3s I'm sure can be compressed somewhat. And also, I never said it had to be lossless compression. But of course, if it sounds crappy when extracted, I'll downgrade it, but still. So, in short, you need to think outside of the box.

why on earth would you want to use lossy compression on an mp3?

1. To offer samples for a service you may be selling.

2. For use in the sampling system we discussed in the RIAA thread.

3. To conserve space without caring for quality.

And, there's tons more, but those are my top three reasons. [addsig]

Allowing loss of data changes the rules entirely.

If you do not permit yourself to lose data, then you will not be able to compress all files to a constant multiple of their sizes unless the underlying format is inherently wasteful, i.e., many bit combinations of a particular length have no meaning or duplicate the meanings of other combinations. I'd be surprised if this is the case with MP3.

This isn't an issue of "keeping an open mind." What I said is clear mathematically. If you can compress by even one bit all files that fit a non-redundant format, you find yourself trying to represent N different uncompressed files with only N/2 available compressed files. It's inevitable that, given some compressed version, you won't have enough information to see how to uncompress it.

Again, if you allow for loss of data, applicability to only a limited set of all possible MP3's, etc., you can pull this off, and it could even be a very worthwhile project. That doesn't change the fact that reversible compression of all files of a non-redundant format is a mathematical impossibility.

Allowing lossful compression doesn't change the rules at all. It just changes the way you interpreted them. Also, what you're saying is that there is nothing whatsoever that is in all MP3's, which is not true.

Not so. For what I said to be false, there has to be useless data in MP3's with size proportional to the overall size of the MP3. (I stipulated that I was talking about compression proportional to file size, since you mentioned 4/5 at the start of this thread.)

Actually, I was reffering to this statement:

Quote:
That doesn't change the fact that reversible compression of all files of a non-redundant format is a mathematical impossibility.

lossless compression does seem possilbe, the only thing you would ned to do is compress it in a zip style format (maybe with a self decompiler) then perform some alithgorm on it... although im not sure if you would allow that...

That's how all compression works, in fact

Quote:That doesn't change the fact that reversible compression of all files of a non-redundant format is a mathematical impossibility.

Actually, there's a good chance that most MP3s have SOME redundancy. Just not necessarily in the way you'd first think of it.

Sounds a very interresting competition. Unfortunately:
i) I know very little about MP3 compression
ii) I'm already working on something.

Good luck to whoever enters.

yeah, i do understand how compression works, despite what you may think, im not that dumb

Btw, what languages do you program? I don't think you've ever said. [addsig]

ah not much, im into web dev (php) but i did do a bit of C and visual basic for that fact but apart from that not much im afriad

Quote:
On 2003-09-15 04:02, Smerdyakov wrote:
Allowing loss of data changes the rules entirely.

If you do not permit yourself to lose data, then you will not be able to compress all files to a constant multiple of their sizes unless the underlying format is inherently wasteful, i.e., many bit combinations of a particular length have no meaning or duplicate the meanings of other combinations. I'd be surprised if this is the case with MP3.

This isn't an issue of "keeping an open mind." What I said is clear mathematically. If you can compress by even one bit all files that fit a non-redundant format, you find yourself trying to represent N different uncompressed files with only N/2 available compressed files. It's inevitable that, given some compressed version, you won't have enough information to see how to uncompress it.

Again, if you allow for loss of data, applicability to only a limited set of all possible MP3's, etc., you can pull this off, and it could even be a very worthwhile project. That doesn't change the fact that reversible compression of all files of a non-redundant format is a mathematical impossibility.


Your mathematical impossibility only applies to trying to compress -all possible files-. The vast, vast majority of this set would give you random static, which isn't characteristic of normal mp3 files. Furthermore, any "random" file is unlikely to be a valid mp3 (not even static, to be truthful) (try playing a data file of some sort in winamp. it won't even work.), which means that the set of all mp3 files of length x doesn't fill the set of all possible combinations of bits of length x, thus all mp3 files -could- be represented in length less than x.

And "waste" can be in forms other than redundancy and meaningless space. If that weren't true, ZIP would give you as good lossless compression for sound as lossless sound compressors give you (50%). Here's an example. Compress a file containing, in 2-byte ints, all numbers from 0 to 65535. An infeasibly intelligent data compressor would encode, for this file, an algorithm for recreating the file that takes less than 100 bytes. Yet the file contains no redundancies. The point here is music is much more structured, simple, and redundant on abstract levels than its low-level PCM representation.

(just to give you an idea, think of the size difference between an mp3 and the same song recreated in .it format with its samples compressed into mp3. granted, this wouldn't be lossless, but the loss in file size would be MUCH greater than the loss in sound quality. and if you recreated it sophisticatedly enough, maybe you could probably add a channel that contains the exact difference between the recreated song and the original, in fewer bites per sample because the differences aren't loud enough, just a thought.)

i once wrote an email to the developers of mp3 suggesting that they try compressing music by analyzing it on the level of instruments, perhaps by using some of ircam's technology, and they said they were working on it for mpeg level 4.

in ANY case, just the fact that not just any file can be played *as* an mp3 means that mp3's have some kind of "waste" that's not necessarily redundancy or meaningless bits.



Another idea: Convert the mp3 to a variable-bitrate mp3. yes it will be technically lossy but without loss in sound quality. other possibilities would be to convert it to ogg vorbis or windows media audio, which in some cases can give you the same sound quality in half the bitrate.

i guess that's all i have to say, which was obviously too much.


[ This Message was edited by: inhahe on 2003-09-20 17:43 ]

Heres a stupid idea: bottomume that some aspect is common to all MP3s and store it in the code of the player. It saves space for multiple files

I have a few challenges for the people surfing this thread.

1) Calculate, to the last decimal place, the value of pi.

2) Calculate whose pitchers bat better in interleague play: the nl or the al.

3) Put a zip file in a zip file, and lose no data quality.

4) Be in two places at once.

5) Get past the speed of light with a rocket booster strapped to a donkey. [addsig]