home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / 2799 < prev    next >
Encoding:
Internet Message Format  |  1992-07-25  |  1.9 KB
  1. Path: sparky!uunet!sun-barr!ames!pacbell.com!pacbell!oracle!unrepliable!bounce
  2. Newsgroups: comp.compression
  3. From: escreven@latenite.us.oracle.com (Edward Screven)
  4. Subject: Re: PERPETUAL MOTION
  5. In-Reply-To: ts@cup.portal.com's message of 24 Jul 92 04:42:17 GMT
  6. Message-ID: <ESCREVEN.92Jul24134328@latenite.us.oracle.com>
  7. Sender: usenet@oracle.us.oracle.com (Oracle News Poster)
  8. Nntp-Posting-Host: latenite.us.oracle.com
  9. Organization: Oracle Corporation, Redwood Shores CA
  10. References: <35610@sdcc12.ucsd.edu> <62020@cup.portal.com>
  11.   <7486@public.BTR.COM> <62692@cup.portal.com>
  12. Date: Fri, 24 Jul 1992 21:43:28 GMT
  13. X-Disclaimer: This message was written by an unauthenticated user
  14.               at Oracle Corporation.  The opinions expressed are those
  15.               of the user and not necessarily those of Oracle.
  16. Lines: 24
  17.  
  18.  
  19. > From: ts@cup.portal.com (Tim W Smith)
  20. > [ algorithm to compress some files of length M without expanding others ]
  21.  
  22. no need to present an algorithm -- you can easily show by counting it is
  23. possible to build a compressor that compresses some bit strings of exactly
  24. length M and doesn't expand any bit string of length M since there are
  25. 2**(M+1) - 1 bit strings of length M or less, but only 2**M bit strings of
  26. length M.
  27.  
  28. > However, I believe that it *DOES* provide a counterexample to the usual
  29. > counting argument.
  30.  
  31. not really.  the usual (correct) counting argument shows that a compressor
  32. cannot compress *all* bit strings of length M.
  33.  
  34.     - edward screven
  35. --
  36. -------------------------------------------------------------------------------
  37. Edward Screven                Internet: escreven@us.oracle.com
  38. Senior Technical Staff       Telephone: (415) 506-6126   Fax: (415) 506-7200
  39. Tools and Multimedia           US Mail: 500 Oracle Parkway, Box 659411,
  40. Oracle Corporation                      Redwood Shores, CA 94065
  41. -------------------------------------------------------------------------------
  42.