home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compress / research / 286 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.6 KB  |  39 lines
  1. Newsgroups: comp.compression.research
  2. Path: sparky!uunet!walter!att-out!pacbell.com!ames!purdue!decwrl!adobe!wtyler
  3. From: wtyler@adobe.com (William Tyler)
  4. Subject: Re: C source for Fractal compression, huh !
  5. Message-ID: <1992Nov18.083335.18739@adobe.com>
  6. Followup-To: comp.compression.research
  7. Summary: Back to Basics
  8. Sender: Bill Tyler
  9. Organization: Adobe Systems Inc., Mountain View, CA
  10. References: <1992Nov16.184754.3170@maths.tcd.ie> <Bxu712.LvA@metaflow.com> <1992Nov18.024912.24072@maths.tcd.ie>
  11. Date: Wed, 18 Nov 1992 08:33:35 GMT
  12. Lines: 25
  13.  
  14. In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:
  15.  
  16. >Chaitin/Kolmogorov Algorithmic Information Theory
  17. >does set an absolute limit to the degree to which
  18. >any given data can be compressed:
  19. >the string s cannot be compressed 
  20. >beyond its entropy (or informational content) H(s).
  21. >H(s) is precisely defined,
  22.  
  23. Ah, there's the rub. H(s) is only precisely defined with respect to
  24. some particular model of the information source s, expressed in the
  25. form of probabilities. The better your model of the source, the more
  26. you can compress the information. Usually our source models are far
  27. from ideal, due both to lack of complete understanding of the source,
  28. and practical considerations of constructing and using complex models.
  29. As an example, consider a source where the probability of a given
  30. symbol being emitted was a function of the previous 10^10 symbols.
  31. You aren't likely to even try to tabulate the probabilities, let alone
  32. make optimal use of them :-)
  33.  
  34. Bill
  35.  
  36.  
  37. -- 
  38. Bill Tyler      wtyler@adobe.com
  39.