home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compress / 3870 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  2.6 KB
  1. Path: sparky!uunet!know!mips2!news.bbn.com!noc.near.net!news.Brown.EDU!qt.cs.utexas.edu!cs.utexas.edu!zaphod.mps.ohio-state.edu!uwm.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!tgl
  2. From: tgl+@cs.cmu.edu (Tom Lane)
  3. Newsgroups: comp.compression
  4. Subject: Re: Need a compressor for sparse bit datastream
  5. Keywords: compression technique
  6. Message-ID: <Bxu5t8.D1B.2@cs.cmu.edu>
  7. Date: 17 Nov 92 01:07:53 GMT
  8. References: <1992Nov13.120505.29654@spectrum.xerox.com>
  9. Sender: news@cs.cmu.edu (Usenet News System)
  10. Organization: School of Computer Science, Carnegie Mellon
  11. Lines: 36
  12. Nntp-Posting-Host: g.gp.cs.cmu.edu
  13.  
  14. richard@garfield.noname (richard_landells.sbd-e@rx.xerox.com) writes:
  15. > I have an application that generates binary output.  The output is
  16. > relatively random, but there are approximately twice as many off bits as on
  17. > bits.  My objective is to compress this as much as possible.  
  18.  
  19. > I have tried several 'standard' compressors, arj 2.2, lharc, pkzip 1.1, and
  20. > have only managed to achieve very minimal compression in the order of 4% at
  21. > best (on a 40K file).  Now I know that a truly random binary datastream
  22. > cannot be compressed, but I was kind of hoping for better than 4%.  Am I
  23. > missing something fundamental, or is this really the best that can be
  24. > achieved?  
  25.  
  26. Most 'standard' compressors work by looking for repeated byte strings.
  27. If your source is really random then this won't be very effective since
  28. you won't have much repetition at the byte level.
  29.  
  30. However, you should be able to exploit the 2:1 ratio of 0s to 1s to get
  31. better than 4% compression.  To do this will require arithmetic compression.
  32. Huffman would work if the symbols were bigger than a bit, but since Huffman
  33. codes can't be less than one bit, you can't get any compression with
  34. single-bit input symbols.  Arithmetic coding wins because it can encode
  35. source symbols into "fractional bits".  Arithmetic compression code is easy
  36. to come by, see the comp.compression FAQ.  (But if you want to use this for
  37. any commercial purpose, beware of patents.)
  38.  
  39. But wait... if all we know about your source is that 0's have probability
  40. .67 and 1's have probability .33, then the entropy is
  41.     -(.67*log2(.67) + .33*log2(.33))
  42. or 0.92, which means you could theoretically achieve at most 8% compression
  43. this way.  I'd say implementing arithmetic coding on individual bits is
  44. probably not worth the trouble.  Are you sure the 0's and 1's are
  45. uncorrelated?  If not, higher-order arithmetic coding might work.
  46. The fact that standard compressors can do as well as 4% suggests to me that
  47. there is more order in the input bitstream than you've let on.
  48.  
  49.                 regards, tom lane
  50.