All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Shrink needed (Posted on 2006-10-18) Difficulty: 2 of 5
A file compressor is great for shrinking stored files, but it depresses me whenever I see a file grow instead of shrink. So what I am looking for is a file compression algorithm that never inflates any files, although it is allowed that some files (not all of course!) have the same length after "compression". Ideally it should work on files of all sizes, but I would be satisfied with a compressor that operates only on files larger than 1MB. Can you provide such an algorithm? No programming knowledge is required for this problem.

See The Solution Submitted by JLo    
Rating: 3.6667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re: Ideas | Comment 7 of 26 |
(In reply to Ideas by Jer)

... and in addition to coding for strings of repeated 0's and repeated 1's, the zipper could identify repeated patterns n-bits in length, '01' for example.  Repeated colors in an image file would be a repeating 8 bit pattern, I suppose.

Also:  Jer said  "A 1MB (8,000,000 bits more or less) file of randomly chosen bits is likely to have a string of 23 0's or 1's in a row.   The position of the string would take 13 bits to encode, the length of the string takes 5 bits and the specification of 0's or 1's takes 1 bit."

I'm not sure you'd have to encode the position in the file, since the decoder would just go right on down the line taking the information in order; like a ribosome ka-chunking its way down an mRNA molecule and adding an amino acide to the growing protein molecule.



  Posted by Larry on 2006-10-18 20:45:07

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information