home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compress / 3035 < prev    next >
Encoding:
Text File  |  1992-08-18  |  2.8 KB  |  64 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!caen!sol.ctr.columbia.edu!sees.bangor.ac.uk!mather
  3. From: mather@sees.bangor.ac.uk (Paul Mather)
  4. Subject: Compression technique mentioned in PCW
  5. Organization: Centre for Applied Obfuscation.
  6. Message-ID: <1992Aug18.155518@sees.bangor.ac.uk>
  7. Sender: mather@sees.bangor.ac.uk (Mr P Mather)
  8. Keywords: snake oil, something for nothing
  9. Date: Tue, 18 Aug 1992 14:55:18 GMT
  10. X-Posted-From: sol.sees.bangor.ac.uk
  11. X-Posted-Through: sol.ctr.columbia.edu
  12. Lines: 50
  13.  
  14. A friend showed me a letter in a recent issue (Sep 1992) of Personal
  15. Computer World magazine.  The letter was a comment on the article
  16. PCW had written on "spectacular" data compression.  It had focussed
  17. (somewhat sarcastically) on W.E.B.'s claimed 16:1 method, and, more
  18. reasonably on Iterated Systems efforts.
  19.  
  20. Anyway, the thrust of the letter was not about those but was to
  21. outline a method which seemed to illustrate that it was possible
  22. to compress data outside the laws of information theory (and
  23. other such W.E.B.-like claims), and indeed to multiply compress
  24. the compressor's output.
  25.  
  26. Sounds like hot air?  (Yes, IMHO.:)
  27.  
  28. Well, the method the person outlined was the familiar one of representing
  29. the bytes of a data stream as a decimal fraction N, where N is between 0
  30. and 1.  A similar scheme was mentioned here during the WEB flame wars,
  31. where compression was achieved by marking this number on a rod.  Decompression
  32. involved precisely measuring the marked length and enumerating it. :-)
  33.  
  34. However, in the compression scheme mentioned in the letter, instead of
  35. using a stout piece of oak :-), the decimal fraction was compressed by
  36. determining two numbers, a and b, such that a/b = N.  To transmit the
  37. original file, one need only transmit a and b.  Decompression would
  38. involve calculating a/b and enumerating the result.
  39.  
  40. A further modification was suggested to the algorithm whereby the
  41. file is partitioned into arbitrary sized chunks and each chunk treated
  42. as a decimal number between 0 and 1 as before.  This would be done
  43. in order to keep down the precision of the fractions (N's) to more
  44. manageable limits and compression would involve finding a's and b's for
  45. each chunk.  (The author of the letter suggested that this list of
  46. a's and b's could be further compressed using the same technique.)
  47.  
  48. When my friend asked me what I thought of the proposed method, my gut
  49. reaction was to say that finding the values of a and b sounded pretty
  50. intractable to me.  It also occurred to me that it was likely that for
  51. some N the enumeration of the integers a and b could be longer than N
  52. itself but my number theory is very rusty so I didn't speculate on that
  53. to my friend. :-)
  54.  
  55. Anyway, I just thought I'd mention it.
  56.  
  57. Cheers,
  58.  
  59. Paul.
  60. -- 
  61. e-mail: p.mather@sees.bangor.ac.uk
  62.  
  63. If your mailer can't reach me, I'm obviously not worth talking to.
  64.