md65536 Posted August 29, 2015 Share Posted August 29, 2015 Some types of compressed files can be compressed further, losslessly... http://www.fastcompany.com/3050180/tech-forecast/these-engineers-just-built-their-own-pied-piper-compression-algorithm yet it is known that there is no possible algorithm that can losslessly compress all possible input data. This puzzle's about that. ---- There is a type of data stream that is a fixed length N bits of binary data. The data is statistically random; every possible variation of 0s and 1s is as likely as any other. There is an optimal lossless compression algorithm that reduces the data size of as many of the possible data variations as is mathematically possible, and produces a variable-length output of M bits. The uncompress algorithm knows the value of N and the size of the compressed data stream. 1. How many of the possible data streams cannot be compressed, ie. where M >= N? 2. For large N, what's the average size savings achieved by the algorithm? 3. Describe or write pseudocode for such an algorithm (compress and uncompress). 4. The CEO of Hooli is offering $1M for your algorithm. Do you take it, or try to develop it with your own startup company? Link to comment Share on other sites More sharing options...
fiveworlds Posted August 30, 2015 Share Posted August 30, 2015 (edited) Some types of compressed files can be compressed further, losslessly... video to msd. It isn't lossless but I wouldn't notice the difference on my crappy screen Edited August 30, 2015 by fiveworlds Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now