home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1993 May / SIMTEL_0593.ISO / msdos / archivrs / dwc_a501.exe / ARTICLE.DOC next >
Encoding:
Text File  |  1988-08-29  |  7.9 KB  |  139 lines
  1.      Only part one of this article was ever written.  For further
  2. information on Lempel-Ziv compression  and decompression,  please
  3. refer to the source notes supplied with the DWC source code.
  4. -----------------------------------------------------------------
  5.  
  6.  
  7.                         Lempel-Ziv-Welch
  8.                       Compression Algorithm
  9.  
  10.                          Dean W. Cooper
  11.                          Germantown, MD
  12.  
  13.      This  is  part one in a three part article that  explains  a 
  14. general  purpose  compression  algorithm that can  compress  text 
  15. files as much as 75%,  and many other types of files as well.  It 
  16. is  perhaps  the best general purpose algorithm and can  only  be 
  17. beat  consistently  by special purpose  algorithms  designed  for 
  18. specific types of data.
  19.  
  20.      The Lempel-Ziv-Welch (LZW) compression algorithm is a simple 
  21. and  relatively fast way to compress many kinds of data including 
  22. text files,  object files and libraries,  executable  files,  and 
  23. graphic bitmaps.  It is a general algorithm that assumes only one 
  24. thing in the data that it is compressing:  that the data contains 
  25. similar  sequences  of  symbols.   Like the  Huffman  compression 
  26. algorithm,  LZW  depends  upon  the frequency of  occurrences  of 
  27. symbols.   But  where  Huffman  depends  upon  the  frequency  of 
  28. discrete symbols,  LZW depends upon the frequency of sequences of 
  29. symbols.
  30.      By definition,  sequences of symbols are called strings.  In 
  31. actual  implementation,  the set of all discrete symbols must  be 
  32. small,  so  usually the data is interpreted as a stream of  bytes 
  33. allowing  for  256 discrete symbols.   These  are  called  atomic 
  34. strings or atoms for short.
  35.      The general idea of LZW is to create a table of all  strings 
  36. that  make  up  the  data and then output  an  encoding  for  the 
  37. strings.   For  example,  let's look at this paragraph to see one 
  38. way  we could encode strings.   It has seven sentences  so  let's 
  39. call  them our strings.   We can encode them simply  enough:  the 
  40. first sentence is 1,  the second is 2,  etc.   Thus,  the encoded 
  41. output is "1234567".  That's all there is to the compressed data, 
  42. that is,  as long as the decompressor knows about the encoding we 
  43. made.   Unfortunately, we can't assume the decompressor knows our 
  44. encoding,  so we are forced to pass this information along to the 
  45. decompressor.
  46.      This  is  usually  done by simply tacking  on  the  required 
  47. information  onto the front of the encoded data.   For  instance, 
  48. the  Huffman algorithm tacks onto the front of its  encoded  data 
  49. the  frequency  histogram of the discrete symbols it  compressed. 
  50. This is just enough information for the decompressor to  recreate 
  51. the encoding used.   LZW, on the other hand, is a little trickier 
  52. and  actually  merges  the  encoded  data  with  the  information 
  53. required for the decompressor to know the encoding.
  54.      The trick is in how LZW defines a string.   Simply, a string 
  55. is  either just an atom or a string followed by an  atom.   Thus, 
  56. the  sequence "abc" is a string because the atom 'c' follows  the 
  57. string  "ab",  which is a string because the atom 'b' follows the 
  58. string "a", which is a string because it itself is an atom.
  59.      Now,  using this definition,  the LZW algorithm reads in its 
  60. data and creates a table of strings.  Since every byte read in is 
  61. an  atom,  adding  the byte to the preceding string read in  will 
  62. create a new string one symbol longer.   The only rule is to read 
  63. in  bytes progressively making larger and larger strings until  a 
  64. string is formed that is not already in the string  table.   When 
  65. this happens,  the last known string's encoding is output and the 
  66. new string is added to the table.  That's all there is to it!
  67.      To  start things off,  we can immediately add to the  string 
  68. table the 256 atomic strings since the decompressor already knows 
  69. these strings.   Also,  let's call the string already read in the 
  70. predecessor  and  the  last  byte  read  in  the  follower.   The 
  71. predecessor  plus the follower creates a new string that we  must 
  72. check  to see if it already exists in the string table.   For  an 
  73. example, let's compress the letters "ababc".
  74.      The first byte read in,  'a',  is a degenerate case since it 
  75. has  no predecessor.   A null predecessor plus the  follower  'a' 
  76. make  the  string "a" which is already in the string table so  we 
  77. must  continue.   "a" now becomes the predecessor string  and  we 
  78. read  in  'b'  as the follower.   The string "ab" is not  in  the 
  79. table,  so we add it and output the code for the predecessor  "a" 
  80. which  in  ASCII  is 97.   The code given to the string  "ab"  is 
  81. simply  256,  that is,  the next code available after the  atomic 
  82. strings 0-255.
  83.      The new predecessor is now "b" and the next follower is 'a'.  
  84. This again forms a string,  "ba", which is not in the table so we 
  85. output the code for the predecessor, "b" which is 98, and add the 
  86. string "ba" to the table with the code 257.  Now, the predecessor 
  87. is "a" and the next follower is 'b'.   This time the string  "ab" 
  88. is in the table so we continue.  The predecessor becomes "ab" and 
  89. the  next follower is 'c'.   This forms the string "abc" which is 
  90. not in the table, so we output the code for the predecessor which 
  91. is  256  and  add  the  string  "abc"  to  the  table.   The  new 
  92. predecessor  is "c",  but now we are out of data so there  is  no 
  93. follower.   This  is another special case and here we just output 
  94. the code for the last predecessor, "c" which is 99.
  95.      Thus,  the  encoding for the compressed sequence "ababc"  is 
  96. 97,98,256,99.   Not so great for such a short sequence,  but  LZW 
  97. does  better  as it creates a larger string table.   Note how  at 
  98. least  nine bits per code is needed as new string codes start  at 
  99. 256  after the atomic strings.   Also note how a code unknown  to 
  100. the decompressor is not used until it could figure out for itself 
  101. what  the code represents.   The pseudo-code for the  compression 
  102. algorithm is as follows:
  103.  
  104.             Predecessor = Read first data byte
  105.             While ( Follower = Read data byte exists )
  106.                if ("Predecessor + Follower" is in string table)
  107.                    Predecessor = Predecessor + Follower
  108.                else
  109.                    Output code for Predecessor
  110.                    Add "Predecessor + Follower" to string table
  111.                    Predecessor = Follower
  112.  
  113.             Output code for predecessor
  114.  
  115.      Each entry in the string table can be simply made up of  the 
  116. codes  for  the predecessor and follower strings that  make  that 
  117. entry.  In our example above the string table would be:
  118.  
  119.             Code:      Predecessor:  Follower:
  120.                0      NOPREDECESSOR      0       Atomic strings
  121.                            ...                         "
  122.              255      NOPREDECESSOR    255             "
  123.              256           97           98       String "ab"
  124.              257           98           97       String "ba"
  125.              258          256           99       String "abc"
  126.  
  127.      Although the string table could be scanned for the string we 
  128. are looking for every time we need to check,  this would be  very 
  129. slow,  so  we add a hash table.   Given a predecessor code and  a 
  130. follower  code,  we can put these values through a hash  function 
  131. and obtain an index into the hash table.  A hash table entry only 
  132. needs  to have the code of the string that it is associated  with 
  133. and  a  pointer to a linked list of other codes of  strings  that 
  134. also hashed to the same hash table entry.  The simplest way is to 
  135. have the linked list use empty slots in the hash table itself.
  136.      Next time, I will elaborate on implementation details of the 
  137. compression algorithm along with some optimization techniques.  
  138.  
  139.