home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compress / 3909 < prev    next >
Encoding:
Text File  |  1992-11-21  |  2.3 KB  |  48 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!cs.utexas.edu!swrinde!sdd.hp.com!think.com!spool.mu.edu!darwin.sura.net!Sirius.dfn.de!Urmel.Informatik.RWTH-Aachen.DE!tabaqui!dak
  3. From: dak@tabaqui.informatik.rwth-aachen.de (David Kastrup)
  4. Subject: Re: Q: How well do random files crunch? A: Not very.
  5. Message-ID: <dak.722386743@tabaqui>
  6. Sender: news@Urmel.Informatik.RWTH-Aachen.DE (Newsfiles Owner)
  7. Nntp-Posting-Host: tabaqui
  8. Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
  9. References: <1992Nov13.135437.19044@decuac.dec.com> <83939@ut-emx.uucp>
  10. Date: 21 Nov 92 22:59:03 GMT
  11. Lines: 35
  12.  
  13. dougmc@ccwf.cc.utexas.edu (Doug McLaren) writes:
  14.  
  15. >In article <1992Nov13.135437.19044@decuac.dec.com> bell@ufp.enet.dec.com () writes:
  16.  
  17. >>Ok, let's talk about random files.  Say I produce a file filled with
  18. >>random bytes, based on a fairly equal-distribution function.
  19.  
  20. >Well, the way I understand it, if your file is completely random, you
  21. >will not be able to compress it at all.
  22.  
  23. >Basically, entropy must always increase.  A random file already has the maximum
  24. >entropy for a file of that length, so you can't compress it.  (compression
  25. >increases entropy while decreasing (or increasing -- sometimes a compression
  26. >scheme will increase the size of the file, but that's irrelavent here) the
  27. >size.
  28.  
  29. >Now, if your file isn't completely random, then it's certainly possible
  30. >that it could be compressed
  31.  
  32. >Of course, it's possible to have a 100,000 byte file thats completely
  33. >'0's come up randomly, but the odds against this are so astronomical ...
  34. >(the infinite number of monkeys idea is nice, but has nothing to do with the
  35. >real world.  One million monkeys typing 100 wps for the total age of the
  36. >universe aren't likely to come up with even ONE work of Shakespear.)
  37.  
  38. But iff such a file cropped up, it would compress better. The thing to note
  39. is, you cannot decrease the MEAN size. As soon as some of the n-byte
  40. patterns a n-byte file may assume 256^{8n} has different probabilities,
  41. a compression might increase entropy, decreasing mean size.
  42.  
  43. Now you could just add, say, one bit to tell whether you tried compression
  44. or not on the remainder of the file, and compress only where you might gain.
  45. Information theory tells you that having random files, ANY compression
  46. will not provide a sufficient gain even that often that the prolongation
  47. by one bit would be compensated in the long run.
  48.