home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / c / 16662 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  2.5 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!spool.mu.edu!olivea!charnel!sifon!thunder.mcrcim.mcgill.edu!mouse
  2. From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: LZW Compression algorithm
  5. Message-ID: <1992Nov17.124947.7065@thunder.mcrcim.mcgill.edu>
  6. Date: 17 Nov 92 12:49:47 GMT
  7. References: <BxMAwz.D6C@willamette.edu> <Bxs4oA.9s6.2@cs.cmu.edu>
  8. Organization: McGill Research Centre for Intelligent Machines
  9. Lines: 48
  10.  
  11. In article <Bxs4oA.9s6.2@cs.cmu.edu>, kosak+@cs.cmu.edu (Corey Kosak) writes:
  12. > In article <1992Nov15.200257.20378@thunder.mcrcim.mcgill.edu> mouse@thunder.mcrcim.mcgill.edu (der Mouse) writes:
  13. >> In article <BxMAwz.D6C@willamette.edu>, bbrown@willamette.edu (Brian Brown) writes:
  14. >>> Does anybody have any information on how to implement LZW
  15. >>> compression/decompression?
  16. >> [description of compression algorithm]
  17.  
  18. > Mr./Ms. Mouse leaves off the description of the decoding process.
  19.  
  20. > The description that Herr/Frau Mouse gives for the encoding process
  21. > is almost correct.  The problem is that in the given algorithm, the
  22. > encoder's table updates are one step ahead of the decoder's; this
  23. > usually doesn't matter, but will cause incorrect behavior for some
  24. > input.
  25.  
  26. True enough.  This is a relatively subtle point I probably should have
  27. mentioned: as you point out, when the input being compressed is of the
  28. form xfooxfoox for some character x and string foo, the compression
  29. algorithm will generate a code that the decompressor does not yet
  30. recognize at the time it gets it.
  31.  
  32. The compress(1) source I have access to contains the following snippet:
  33.  
  34.     /*
  35.      * Special case for KwKwK string.
  36.      */
  37.     if ( code >= free_ent ) {
  38.             *stackp++ = finchar;
  39.         code = oldcode;
  40.     }
  41.  
  42. When compressing KwKwK (w is a string, K is a single character) and Kw
  43. is present in the table but KwK is not, the encoder will emit the code
  44. for Kw and enter KwK, and the next code it emits will be the
  45. newly-entered one for KwK, which a naive decoder won't yet know how to
  46. recognize.  Consequently, the decoder recognizes input codes it doesn't
  47. yet have in its table as indicating this has occurred, and compensates.
  48. (The decoder does have enough information to decode this correctly,
  49. since the previous code will always be the one for Kw, from which KwK
  50. can trivially be deduced.)
  51.  
  52. Fortunately, this is the only circumstance in which a correct
  53. compresser will generate a code the decoder doesn't already know...
  54.  
  55.                     der Mouse
  56.  
  57.                 mouse@larry.mcrcim.mcgill.edu
  58.