home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / c / 16569 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  4.8 KB

  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!kosak
  2. From: kosak+@cs.cmu.edu (Corey Kosak)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: LZW Compression algorithm
  5. Message-ID: <Bxs4oA.9s6.2@cs.cmu.edu>
  6. Date: 15 Nov 92 22:48:09 GMT
  7. Article-I.D.: cs.Bxs4oA.9s6.2
  8. References: <BxMAwz.D6C@willamette.edu> <1992Nov15.200257.20378@thunder.mcrcim.mcgill.edu>
  9. Sender: Corey Kosak <kosak+@cmu.edu>
  10. Organization: School of Computer Science, Carnegie Mellon
  11. Lines: 96
  12. Nntp-Posting-Host: ibis.warp.cs.cmu.edu
  13.  
  14. In article <1992Nov15.200257.20378@thunder.mcrcim.mcgill.edu> mouse@thunder.mcrcim.mcgill.edu (der Mouse) writes:
  15. >In article <BxMAwz.D6C@willamette.edu>, bbrown@willamette.edu (Brian Brown) writes:
  16. >
  17. >> Does anybody have any information on how to implement LZW
  18. >> compression/decompression?
  19. >
  20. >You have a table of 65536 (2^16) entries.  Each table entry
  21. >conceptually contains a string of bytes, or is empty.  Initially, 256
  22. >of the entries contain the 256 possible single-byte strings, with the
  23. >rest empty.  Initialize the algorithm by reading the first byte of
  24. >input into a working variable which conceptually contains a string of
  25. >bytes.
  26. >
  27. >While the current working string of bytes is listed in the table, read
  28. >another byte.  As soon as the string is not listed in the table, output
  29. >the table index corresponding to the last string that was in the table,
  30. >add the working string to the table, and reset the working string so it
  31. >contains just the last byte.  Then go back to the beginning of this
  32. >paragraph.  Dealing with EOF on input complicates this slightly, but
  33. >only slightly.  Dealing with a full table is fairly easy: just skip the
  34. >"add the working string to the table" step.
  35.  
  36. Mr./Ms. Mouse leaves off the description of the decoding process.
  37. However, it is fairly straightforward.  Input a table index, decode it
  38. by retrieving the associated string from your table, and then add a new entry
  39. to your table.  This new entry is the concatenation of the previous string
  40. found and the first character of the current string.  (Note that for
  41. the first time through the loop, there is no "previous string", so
  42. you do not do a table update)
  43.  
  44. The description that Herr/Frau Mouse gives for the encoding process
  45. is almost correct.  The problem is that in the given algorithm,
  46. the encoder's table updates are one step ahead of the decoder's;
  47. this usually doesn't matter, but will cause incorrect behavior for some
  48. input.
  49.  
  50. Consider an input that begins with "aaaa", and trace the algorithm.
  51.  
  52. 1. Initialize the table
  53.  
  54. 2. read a byte.  (the first 'a'.  Our working string is "a".  This is
  55.    in the table, so we loop)
  56.  
  57. 3. read another byte.  (the second 'a'.  Now our working string is "aa",
  58.    which is not in the table.  Following the instructions, we:
  59.  
  60.    - output the index for the last string that was in the table
  61.      OUTPUT (INDEX ("a")) -- assume for the sake of argument that this index is 97
  62.    - add the working string to the table
  63.      TABLE [256] = "aa"
  64.    - reset the working string so it contains the last byte
  65.      WORKING_STRING = "a"
  66.    - loop
  67.  
  68. 4. read another byte.  (the third 'a'.  Now our working string is "aa".
  69.    This is in the table, so we loop)
  70.  
  71. 5. read another byte.  (the fourth 'a'.  Now our working string is "aaa",
  72.    which is not in the table.  Following the instructions we:
  73.  
  74.    - output the index for the last string that was in the table
  75.      OUTPUT (INDEX ("aa")) -- this is 256
  76.    - add the working string to the table
  77.      TABLE [257] = "aaa"
  78.    - reset the working string so it contains the last byte
  79.      WORKING_STRING = "a"
  80.    - loop
  81.  
  82.  
  83. Let's stop here and look at what happens when we try to decompress
  84. this data.  So far, we've emitted two codes: 97 and 256.
  85.  
  86. Decoding 97 tells us that the first byte is 'a'.  But when we encounter
  87. the second code, 256, we have no way of knowing what the sender has
  88. in slot 256 of its array.  Maybe "aa".  Maybe not.
  89.  
  90. As I mentioned above, this problem is caused by the encoder being
  91. one step ahead of the decoder with respect to table updates.
  92. The way to fix this is to delay sender table updates by one iteration.
  93. So the revised instructions might read:
  94.  
  95. >While the current working string of bytes is listed in the table, read
  96. >another byte.  As soon as the string is not listed in the table, output
  97. >the table index corresponding to the last string that was in the table,
  98. ***add LAST_UPDATE to the table, set LAST_UPDATE to the current working string,***
  99. >and reset the working string so it
  100. >contains just the last byte.  Then go back to the beginning of this
  101. >paragraph.  Dealing with EOF on input complicates this slightly, but
  102. >only slightly.  Dealing with a full table is fairly easy: just skip the
  103. >"add the working string to the table" step.
  104.  
  105. (The same note applies to the compressor: for the first time through the
  106. loop, LAST_UPDATE is not valid, so you do not add anything to the table.)
  107.  
  108.  
  109. -Corey Kosak
  110.