home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / compress / 4597 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  2.0 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!swrinde!emory!cs.utk.edu!memstvx1!ujacampbe
  2. From: ujacampbe@memstvx1.memst.edu (James Campbell)
  3. Newsgroups: comp.compression
  4. Subject: DOWNRe: *** IMPORTANT *** new version of PKZIP is on its way.
  5. Message-ID: <1993Jan12.113758.4986@memstvx1.memst.edu>
  6. Date: 12 Jan 93 11:37:58 -0600
  7. References: <3577@accucx.cc.ruu.nl> <1993Jan11.210249.7579@wam.umd.edu> <7457@sersun1.essex.ac.uk>
  8. Organization: MSU Cryptologic Group
  9. Lines: 32
  10.  
  11. In article <7457@sersun1.essex.ac.uk>, mossap@solb1.essex.ac.uk (Moss A D) writes:
  12. > Does anyone have a copy of the proof that any string can be compressed
  13. > down to 256 bits? Sounds like a crock to me, but I'd be interested in 
  14. > seeing it.
  15. > 
  16. > Thanks!
  17. > 
  18. > Regards,
  19. >       Adam Moss
  20. >             <mossap@essex.ac.uk> 
  21.  
  22. (I'm assuming you're referring to lossless compression, since a lossy
  23. algorithm could compress a string down to any arbitrary length.)
  24.  
  25. Intuitively, this is not possible.  Consider that there are exactly 2^257
  26. strings of 256 bits or less (including the null string).  Therefore, only
  27. 2^257 distinct strings could be thus compressed, at best.  The numbers
  28. from 0 to 2^257, for example, could not all be represented into 256 bits
  29. or less.  One would have to be left out, or its compressed version would 
  30. be undifferentiable from that of at least one of the other numbers.
  31.  
  32. I suppose one could argue that all the strings ever used by mankind don't
  33. add up to 2^256 strings, so a limited algorithm should be theoretically
  34. possible.  May be, but the only way I could envision such an algorithm
  35. would be in the form of a lookup table containing _every_ string that was
  36. ever used.  For those of us with finite disk space, this isn't a viable
  37. option :-).  Besides, such a solution would be indexing, _not_ compression.
  38.  
  39. -- 
  40.   ===========================================================================
  41.   James Campbell, Math Sciences Department, MSU; ujacampbe@memstvx1.memst.edu
  42.   ---------------------------------------------------------------------------
  43.