home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compress / 4163 < prev    next >
Encoding:
Text File  |  1992-12-15  |  2.5 KB  |  71 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!moe.ksu.ksu.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: Fixed point of the lzw compression alg.
  5. Sender: news@news.uiowa.edu (News)
  6. Message-ID: <1992Dec15.172309.3667@news.uiowa.edu>
  7. Date: Tue, 15 Dec 1992 17:23:09 GMT
  8. References: <1992Dec15.165902.3227@news.uiowa.edu>
  9. Nntp-Posting-Host: pyrite.cs.uiowa.edu
  10. Organization: University of Iowa, Iowa City, IA, USA
  11. Lines: 58
  12.  
  13. From article <1992Dec15.165902.3227@news.uiowa.edu>,
  14. by williams@herky.cs.uiowa.edu (Kent Williams):
  15.  
  16. > From ren@function.mps.ohio-state.edu (Liming Ren):
  17. >
  18. >> Is there a fixed point for lzw?
  19.  
  20. A really interesting question, but in a realm akin to "pure math" in that
  21. I can't see a single reason that the answer could be useful to anyone.
  22. (And I say this as someone who's looked seriously at fixed points of
  23. macro assembly languages and linking loaders!)
  24.  
  25. > Taking the Unix Compress.  You start out with ...
  26. > 
  27. >     <NO PREDECESSOR>N
  28. > 
  29. > for N in 0..256.  The code for <NO PREDECESSOR>N is N, but the code
  30. > will be output at nine bits of precision. ...
  31.  
  32. This gives us the key we need to begin constructing a fixed point for
  33. LZW, but keep in mind that UNIX compress puts a three byte magic cookie
  34. on the front of the compressed file.  Ignoring this magic cookie, we can
  35. make the following observation:
  36.  
  37. Input  XXXXXXXX < a single byte input file
  38.  
  39. Output XXXXXXXX < the LZW compressed result
  40.               0
  41.  
  42. Input  XXXXXXXX < a two byte input file
  43.        YYYYYYYY
  44.  
  45. Output XXXXXXXX < the LZW compressed output
  46.        YYYYYYY0
  47.              0Y
  48.  
  49. From this, we conclude that if there is a fixed point, the second
  50. character must have an even code in binary (the LSB must be zero).
  51.  
  52. Furthermore, each new byte that occurs (before a string is found
  53. that is actually compressible) adds one bit to the output, so there
  54. must eventually be a compressible string in the sequence to take away
  55. a bit.
  56.  
  57. Conclusion.  7 new characters add 7 bits to the string.  If the 8th
  58. and 9th characters are a repeat of a previous digraph in the string,
  59. they will add a single 9 bit lump for two characters, thus making the
  60. total input string length equal to the total output string length.
  61.  
  62. Therefore, the shortest possible fixed point for LZW (ignoring end
  63. of file coding) will be something like:
  64.  
  65.    ABCDEFGAB
  66.  
  67. with a letter substitution that is very carefully chosen.
  68.  
  69.                     Doug Jones
  70.                     jones@cs.uiowa.edu
  71.