home *** CD-ROM | disk | FTP | other *** search
/ Falcon 030 Power 2 / F030_POWER2.iso / ST_STE / MAGS / ICTARI10.ARJ / ictari.10 / MISC / LZW / LZW_GIF.TXT
Text File  |  1994-04-04  |  18KB  |  331 lines
  1.  
  2.                    LZW and GIF explained----Steve Blackstock
  3.                    =========================================
  4.  
  5.      I hope this little document will help enlighten those of you out there
  6.     who want to know more about  the Lempel-Ziv Welch compression algorithm
  7.     and, specifically, the implementation that GIF uses.
  8.  
  9.      Before we start, here's a little terminology, for the purposes of this
  10.     document:
  11.  
  12.       "character": a fundamental data element.  In  normal text files, this
  13.     is just a single byte. In raster images, which is what we're interested
  14.     in, it's an index that specifies the color of a given pixel. I'll refer
  15.     to an arbitrary character as "K".
  16.  
  17.       "charstream": a stream of characters, as in a data file.
  18.  
  19.       "string": a number of  continuous  characters,  anywhere  from one to
  20.     very many characters in length.  I  can  specify an arbitrary string as
  21.     "[...]K".
  22.  
  23.       "prefix": almost the same as a  string, but with the implication that
  24.     a prefix immediately precedes  a  character,  and  a  prefix can have a
  25.     length of zero. So a prefix and  a  character  make up a string. I will
  26.     refer to an arbitrary prefix as "[...]".
  27.  
  28.       "root": a single-character  string.  For  most  purposes,  this  is a
  29.     character, but we may occasionally  make  a  distinction. It is [...]K,
  30.     where[...] is empty.
  31.  
  32.       "code": a number, specified by a known  number of bits, which maps to
  33.     a string.
  34.  
  35.       "codestream": the output stream of  codes,  as  in the "raster data "
  36.     "entry": a code and its string.
  37.  
  38.       "string table": a  list  of  entries;  usually,  but not necessarily,
  39.     unique.
  40.  
  41.       That should be enough of that.
  42.  
  43.      LZW is a way of compressing data that takes advantage of repetition of
  44.     strings in the data. Since raster  data  usually contains a lot of this
  45.     repetition, LZW is a good way of compressing and decompressing it.
  46.  
  47.      For the moment, lets consider normal  LZW encoding and decoding. GIF's
  48.     variation on the concept is just an extension from there.
  49.  
  50.      LZW manipulates three objects  in  both compression and decompression:
  51.     the charstream, the codestream, and  the  string table. In compression,
  52.     the charstream is  the  input  and  the  codestream  is  the output. In
  53.     decompression, the codestream is the  input  and  the charstream is the
  54.     output.  The  string  table  is  a  product  of  both  compression  and
  55.     decompression, but is never passed from one to the other.
  56.  
  57.      The first thing we  do  in  LZW  compression  is initialize our string
  58.     table.
  59.  
  60.      To do this, we need to choose a code size (how many bits) and know how
  61.     many values our characters can possibly  take.  Let's say our code size
  62.     is 12 bits, meaning we can store  0->FFF, or 4096 entries in our string
  63.     table. Let's also say that  we  have  32 possible different characters.
  64.     (This corresponds to, say, a  picture  in  which there are 32 different
  65.     colors possible for each pixel.) To  initialize  the table, we set code
  66.     #0 to character #0, code #1 to character  #1, and so on, until code #31
  67.     to character #31. Actually, we are specifying  that each code from 0 to
  68.     31 maps to a root. There will be no more entries in the table that have
  69.     this property.
  70.  
  71.      Now we start compressing data. Let's first define something called the
  72.     "current prefix". It's just a  prefix  that  we'll  store things in and
  73.     compare things to  now  and  then.  I  will  refer  to  it  as "[.c.]".
  74.     Initially, the current prefix has  nothing  in  it. Let's also define a
  75.     "current string", which  will  be  the  current  prefix  plus  the next
  76.     character in the charstream.  I  will  refer  to  the current string as
  77.     "[.c.]K", where K is some character. OK, look at the first character in
  78.     the charstream. Call it P. Make [.c.]P the current string.
  79.  
  80.      (At this point, of course, it's  just  the root P.) Now search through
  81.     the string table to see if  [.c.]P  appears  in  it. Of course, it does
  82.     now, because our string table is  initialized  to have all roots. So we
  83.     don't do anything.
  84.  
  85.      Now make [.c.]P the current prefix. Look  at the next character in the
  86.     charstream. Call it Q. Add it to the current prefix to form [.c.]Q, the
  87.     current string. Now search through  the  string  table to see if [.c.]Q
  88.     appears in it. In this case, of course,  it doesn't. Aha! Now we get to
  89.     do something.
  90.  
  91.      Add [.c.]Q (which is PQ in  this  case)  to  the string table for code
  92.     #32, and output the code for  [.c.]  to  the codestream. Now start over
  93.     again with the  current  prefix  being  just  the  root  P. Keep adding
  94.     characters to [.c.] to form [.c.]K, until  you can't find [.c.]K in the
  95.     string table. Then output the  code  for  [.c.]  and  add [.c.]K to the
  96.     string table. In pseudo-code, the algorithm goes something like this :-
  97.  
  98.      [1] Initialize string table;
  99.  
  100.      [2] [.c.] <- empty;
  101.  
  102.      [3] K <- next character in charstream;
  103.  
  104.      [4] Is [.c.]K in string table?
  105.  
  106.       (yes: [.c.] <- [.c.]K;            go to [3];      )
  107.  
  108.       (no: add [.c.]K to the string table;
  109.  
  110.            output the code for [.c.] to the codestream;
  111.           [.c.] <- K;
  112.  
  113.            go to [3];      )
  114.  
  115.        It's as simple as that!  Of  course,  when  you  get to step [3] and
  116.     there aren't any more characters  left,  you  just  output the code for
  117.     [.c.] and throw the table away. You're done.
  118.  
  119.       Wanna do an example? Let's pretend we have a four-character alphabet:
  120.     A,B,C,D. The charstream looks like  ABACABA.  Let's compress it. First,
  121.     we initialize our string table  to:  #0=A,  #1=B, #2=C, #3=D. The first
  122.     character is A, which is in the  string table, so [.c.] becomes A. Next
  123.     we get AB, which is not in the table, so we output code #0 (for [.c.]),
  124.     and add AB to the string table as code #4. [.c.] becomes B. Next we get
  125.     [.c.]A = BA, which is not in  the  string table, so output code #1, and
  126.     add BA to the string table as code #5. [.c.] becomes A. Next we get AC,
  127.     which is not in the string  table.  Output  code  #0, and add AC to the
  128.     string table as code #6. Now [.c.] becomes  C. Next we get [.c.]A = CA,
  129.     which is not in the table.
  130.  
  131.      Output #2 for C, and add CA to  table as code #7. Now [.c.] becomes A.
  132.     Next we get AB, which IS in the  string table, so [.c.] gets AB, and we
  133.     look at ABA, which is not in  the  string table, so output the code for
  134.     AB, which is #4, and add  ABA  to  the  string  table as code #8. [.c.]
  135.     becomes A. We can't get any more  characters,  so we just output #0 for
  136.     the code for A, and we're done. So, the codestream is #0#1#0#2#4#0.
  137.  
  138.       A few words  (four)  should  be  said  here  about  efficiency: use a
  139.     hashing  strategy.  The  search  through   the   string  table  can  be
  140.     computationally intensive, and some hashing  is  well worth the effort.
  141.     Also, note that "straight LZW" compression runs the risk of overflowing
  142.     the string table -getting to a  code  which can't be represented in the
  143.     number of bits you've set aside  for  codes.  There are several ways of
  144.     dealing with this problem, and  GIF  implements  a very clever one, but
  145.     we'll get to that.
  146.  
  147.       An important thing  to  notice  is  that,  at  any  point  during the
  148.     compression, if [...]K is in  the  string  table,  [...] is there also.
  149.     This fact suggests  an  efficient  method  for  storing  strings in the
  150.     table. Rather than store the entire string of K's in the table, realize
  151.     that any string can be expressed as  a prefix plus a character: [...]K.
  152.     If we're about to store  [...]K  in  the  table,  we know that [...] is
  153.     already there, so we can just store  the  code for [...] plus the final
  154.     character K.
  155.  
  156.       Ok, that takes care  of  compression.  Decompression  is perhaps more
  157.     difficult conceptually, but it is really easier to program.
  158.  
  159.       Here's how it goes: We again have to start with an initialised string
  160.     table.  This  table  comes  from  what  knowledge  we  have  about  the
  161.     charstream that we will eventually  get,  like what possible values the
  162.     characters can take. In GIF files, this information is in the header as
  163.     the number of possible pixel values. The beauty of LZW, though, is that
  164.     this is all we need to know. We will build the rest of the string table
  165.     as we decompress the codestream. The compression  is done in such a way
  166.     that we will never encounter  a  code  in  the codestream that we can't
  167.     translate into a string.
  168.  
  169.       We need to define something  called  a  "current  code", which I will
  170.     refer to as "<code>",  and  an  "old-code",  which  I  will refer to as
  171.     "<old>". To start things  off,  look  at  the  first  code. This is now
  172.     <code>. This code will be in  the  initialised string table as the code
  173.     for a root. Output the root to  the charstream. Make this code the old-
  174.     code <old>. *Now look at  the  next  code,  and  make  it <code>. It is
  175.     possible that this code will  not  be  in  the  string table, but let's
  176.     assume for now that it is. Output the string corresponding to <code> to
  177.     the codestream. Now find the  first  character  in  the string you just
  178.     translated. Call this K.  Add  this  to  the  prefix [...] generated by
  179.     <old> to form a new string [...]K. Add this string [...]K to the string
  180.     table, and set the old-code <old> to the current code <code>.
  181.  
  182.     Repeat from where I typed the  asterisk,  and you're all set. Read this
  183.     paragraph again if  you  just  skimmed  it!!!   Now  let's consider the
  184.     possibility that <code> is  not  in  the  string  table.  Think back to
  185.     compression, and try to understand what  happens when you have a string
  186.     like P[...]P[...]PQ appear in the charstream. Suppose P[...] is already
  187.     in the string table, but P[...]P is  not. The compressor will parse out
  188.     P[...], and find that  P[...]P  is  not  in  the  string table. It will
  189.     output the code for P[...], and  add  P[...]P to the string table. Then
  190.     it will get up to P[...]P for the next string, and find that P[...]P is
  191.     in the table, as the code just  added.  So  it will output the code for
  192.     P[...]P if it finds that P[...]PQ is not in the table.
  193.  
  194.      The decompressor is always "one step  behind" the compressor. When the
  195.     decompressor sees the code for  P[...]P,  it  will  not have added that
  196.     code to it's string table yet because it needed the beginning character
  197.     of P[...]P to add to the string for  the last code, P[...], to form the
  198.     code for P[...]P. However, when  a  decompressor  finds  a code that it
  199.     doesn't know yet, it will always be  the  very  next one to be added to
  200.     the string table. So it  can  guess  at  what  the  string for the code
  201.     should be, and,  in  fact,  it  will  always  be  correct.  If  I  am a
  202.     decompressor, and I see code #124, and  yet my string table has entries
  203.     only up to code #123, I can figure  out  what code #124 must be, add it
  204.     to my string table, and output  the  string. If code #123 generated the
  205.     string, which I will refer to here  as a prefix, [...], then code #124,
  206.     in this special case, will be [...]  plus the first character of [...].
  207.     So just add the first character of [...]  to the end of itself. Not too
  208.     bad.
  209.  
  210.      As an example (and a  very  common  one)  of  this special case, let's
  211.     assume we have a raster image in  which the first three pixels have the
  212.     same color value. That is,  my  charstream  looks like: QQQ.... For the
  213.     sake of argument, let's say we have 32  colors, and Q is the color #12.
  214.     The compressor will generate the code sequence 12,32,.... (if you don't
  215.     know why, take a minute to understand  it.) Remember that #32 is not in
  216.     the initial table, which goes from #0 to #31. The decompressor will see
  217.     #12 and translate it just fine as color Q. Then it will see #32 and not
  218.     yet know what that means. But if it thinks about it long enough, it can
  219.     figure out that QQ should be entry  #32  in  the table and QQ should be
  220.     the  next  string  output.   So   the  decompression  pseudo-code  goes
  221.     something like:
  222.  
  223.      [1] Initialize string table;
  224.  
  225.      [2] get first code: <code>;
  226.  
  227.      [3] output the string for <code> to the charstream;
  228.  
  229.      [4] <old> = <code>;
  230.  
  231.      [5] <code> <- next code in codestream;
  232.  
  233.      [6] does <code> exist in the string table?
  234.  
  235.       (yes: output the string for <code> to the charstream;
  236.  
  237.             [...] <- translation for <old>;
  238.  
  239.             K <- first character of translation for <code>;
  240.  
  241.             add [...]K to the string table;
  242.  
  243.         <old> <- <code>;  )      (no: [...] <- translation for <old>;
  244.  
  245.            K <- first character of [...];
  246.  
  247.            output [...]K to charstream and add it to string table;
  248.  
  249.            <old> <- <code>      )
  250.  
  251.      [7] go to [5];
  252.  
  253.       Again, when you get to step [5]  and  there are no more codes, you're
  254.     finished.  Outputting of strings, and  finding of initial characters in
  255.     strings are efficiency problems all to themselves, but I'm not going to
  256.     suggest ways to do them here.  Half  the fun of programming is figuring
  257.     these things out!
  258.  
  259.                                       ---
  260.  
  261.       Now for the GIF variations on the  theme.  In part of the header of a
  262.     GIF file, there is a  field,  in  the  Raster Data stream, called "code
  263.     size". This is a very misleading  name  for  the  field, but we have to
  264.     live with it. What it is really is the "root size". The actual size, in
  265.     bits, of the compression  codes  actually  changes during compression /
  266.     decompression, and I will refer to  that  size here as the "compression
  267.     size". The initial table is just the codes for all the roots, as usual,
  268.     but two special codes are added on top of those.
  269.  
  270.      Suppose you have a "code size",  which  is  usually the number of bits
  271.     per pixel in the image, of N.  If  the  number  of bits / pixel is one,
  272.     then N must be 2: the  roots  take  up  slots  #0 and #1 in the initial
  273.     table, and the two special codes will  take  up slots #4 and #5. In any
  274.     other case, N is the number of  bits  per  pixel, and the roots take up
  275.     slots #0 through  #(2**N-1),  and  the  special  codes  are  (2**N) and
  276.     (2**N+1). The initial compression size  will  be  N+1 bits per code. If
  277.     you're encoding, you output the  codes  (N+1)  bits  at a time to start
  278.     with, and if you're decoding, you  grab  (N+1) bits from the codestream
  279.     at a time.  As  for  the  special  codes:  <CC>  or  the clear code, is
  280.     (2**N), and <EOI>, or end-of-information,  is  (2**N+1). <CC> tells the
  281.     compressor  to  re-initialise  the  string  table,  and  to  reset  the
  282.     compression  size  to  (N+1).  <EOI>  means  there's  no  more  in  the
  283.     codestream.  If you're encoding  or  decoding,  you should start adding
  284.     things to the string table at <CC>  + 2. If you're encoding, you should
  285.     output <CC> as the very first  code,  and  then whenever after that you
  286.     reach code #4095 (hex  FFF),  because  GIF  does  not allow compression
  287.     sizes to be greater than 12  bits.  If  you're decoding, you should re-
  288.     initialise your string  table  when  you  observe  <CC>.   The variable
  289.     compression sizes are really no big deal. If you're encoding, you start
  290.     with a compression size of  (N+1)  bits,  and,  whenever you output the
  291.     code (2**(compression size)-1), you  bump  the  compression size up one
  292.     bit. So the next code you output  will be one bit longer. Remember that
  293.     the largest compression size is  12  bits,  corresponding  to a code of
  294.     4095. If you get that far, you  must  output <CC> as the next code, and
  295.     start over.  If you're  decoding,  you  must  increase your compression
  296.     size AS SOON  AS  YOU  write  entry  #(2**(compression  size)-1) to the
  297.     string table. The next code you READ will be one bit longer. Don't make
  298.     the mistake of waiting until you  need  to add the code (2**compression
  299.     size) to the table. You'll  have  already  missed  a  bit from the last
  300.     code.  The packaging of codes into  a  bitsream  for the raster data is
  301.     also a potential stumbling block for the novice encoder or decoder. The
  302.     lowest order bit in the code  should coincide with the lowest available
  303.     bit in the first  available  byte  in  the  codestream. For example, if
  304.     you're starting with  5-bit  compression  codes,  and  your first three
  305.     codes are, say, <abcde>, <fghij>, <klmno>,  where  e,  j, and o are bit
  306.     #0, then your codestream will start off like:
  307.  
  308.        byte#0: hijabcde       byte#1: .klmnofg
  309.  
  310.       So the  differences  between  straight  LZW  and  GIF  LZW  are:  two
  311.     additional  special  codes  and  variable  compression  sizes.  If  you
  312.     understand LZW, and you understand  those variations, you understand it
  313.     all!
  314.  
  315.       Just as sort of a P.S., you may  have noticed that a compressor has a
  316.     little bit of flexibility at  compression  time. I specified a "greedy"
  317.     approach to the compression,  grabbing  as  many characters as possible
  318.     before outputting codes. This  is,  in  fact,  the  standard LZW way of
  319.     doing things, and it will yield the best compression ratio.
  320.  
  321.     But there's no rule saying you  can't  stop anywhere along the line and
  322.     just output the code for  the  current  prefix, whether it's already in
  323.     the table or not, and add  that  string  plus the next character to the
  324.     string table.  There  are  various  reasons  for  wanting  to  do this,
  325.     especially  if  the  strings  get   extremely  long  and  make  hashing
  326.     difficult.
  327.  
  328.      If you need to, do it.
  329.  
  330.               Hope this helps out.----steve blackstock
  331.