home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / compress / 3828 < prev    next >
Encoding:
Text File  |  1992-11-14  |  1.7 KB  |  42 lines

  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!destroyer!news.iastate.edu!hobbes.physics.uiowa.edu!news.uiowa.edu!news
  3. From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
  4. Subject: Re: How well do random files crunch?
  5. Sender: news@news.uiowa.edu (News)
  6. Message-ID: <1992Nov13.151607.23707@news.uiowa.edu>
  7. Date: Fri, 13 Nov 1992 15:16:07 GMT
  8. References: <1992Nov13.135437.19044@decuac.dec.com>
  9. Nntp-Posting-Host: pyrite.cs.uiowa.edu
  10. Organization: University of Iowa, Iowa City, IA, USA
  11. Lines: 29
  12.  
  13. From article <1992Nov13.135437.19044@decuac.dec.com>,
  14. by bell@ufp.enet.dec.com ():
  15. > So the probability for any given character to occur is 1/256, no matter
  16. > the file length (because it's an even distribution).
  17.  
  18.     Don't expect any compression.  In fact, expect some expansion
  19.     with any compression algorithm that's not theoretically optimal.
  20. > How about for a parabolic distribution?  I mean (since I'm not that good
  21. > with statistics) that it's more likely to get a high or low number, that
  22. > one close to 0.5.  Do you think that would make any difference?
  23.  
  24.     If different characters have significantly different
  25.     probabilities, expect some compression with just about any
  26.     decent compression algorithm.  If the likelyhood of different
  27.     characters depends in any way on the context in which that
  28.     character is found, expect to gain from higher-order source
  29.     models.
  30.  
  31.     For example, you can construct strings where all letters are
  32.     equally likely, but where the letters A-M are always followed
  33.     by the letters N-Z and vicea versa.  In such a "language",
  34.     A simple Huffman code won't manage to compress anything, but
  35.     both LZW and context dependant Huffman coding will compress
  36.     the files fairly well.
  37.  
  38.                     Doug Jones
  39.                     jones@cs.uiowa.edu
  40.