[Back to FAQ SWAG index]  [Back to Main SWAG index]  [Original]

{
Robert Rothenburg

Ok, since a few people have requested info about compression routines I
thought some actual descriptions of the algorithm(s) involved would be a
good idea.  Rather than dig out someone else's text file or mail (which
might be copyrighted or arcane) I'll try my hand at explaining a few
methods.

It seems better that programmers have at least a rudimentary understanding
of the algortihms if they plan on using (or not using :) them.

DISCLAIMER: Please pardon any innacuracies: What I know is based on other
  people's mail, text files or from what I've gleaned from spending a few
  hours at the library (adivce: your local college research-library is a
  wonderful resource of algorithms and source-code. Old magazines as well
  as academic papers like the IEEE Transactions are worth examining).


In this insanely long post:

I.   "Garbage Collection"
II.  "Keywords"
III. Run-Length Encoding (RLE)
IV.  Static and Dynamic Huffmann Codes  <--(BTW, is it one or two n's?)
V.   Lampev-Ziv (LZ)
VI.  Lampev-Ziv-Welch (LZW) et al.


I.  "Garbage Collection"

  The simplest methods of compression in weeding out unnecessary data,
  especially from text files.  Spaces at the end of a line, or extra
  carriage returns at the end of a file. (Especially with MS-DOS text
  files, which use a Carriage Return *and* Line Feed--many editors and
  file-browsers do not need both. Eliminating one of them can cut a large
  text file's size by a few percent!)

  I've also seen some utilities that "clean up" the headers of EXE
  files (such as UNP) by eliminating `unnecessary' info.  Other
  utilities will clean up graphics files so that they'll compress
  better.

  In fact, removing excess "garbage" from any file will probably
  improve its compressability.

II. "Keywords"

  Another way to compress text files is to use a "keyword" for each word.

  I.E. we can assume most text files will have less than 65,536 different
  words (16 bits=two bytes), and thus we can assign a different value for
  each word: since most words are longer than three letters (more than two
  bytes), we will save space in the file. However, we'll need some form of
  look-up table for each keyword--one way around this might be to use a
  reference to a standard dictionary file that is included with an operating
  system or word processor.

  (This has other advantages as well. Many BASIC interpreters will store
  commands like PRINT or INPUT as a character code rather than the entire
  name in ASCII text.  Not only does this save memory but improves the
  run-speed of the program.)

  This method can be adapted to other (non-text) files, of course.

III. Run-Length Encoding (RLE)

  With RLE, repeated characters (such as leading spaces in text, or large
  areas of one color in graphics) are expressed with a code noting which
  byte is repeated and how many times it's repeated.

IV.  Static and Dynamic Huffmann Codes

  The logic behind this method is that certain characters occur more often
  than others, and thus the more common characters can be expressed with
  fewer bits. For example, take a text file: 'e' might be the most common
  character, then 'a', then 's', then 'i', etc....

  We can express these characters in a bit-stream like so:

                'e' = 1
                'a' = 01         <--These are Static Huffmann Codes.
                's' = 001
                'i' = 0001
                    etc...

  Since these characters normally take up 8-bits, the first (most common)
  seven will save space when expressed this way, if they occur often enough
  in relation to the other 249 characters.

  This is often represented as a (Static) Huffmann Tree:

                        /\              Note that a compression routine
                 'e' = 1  0             will have to first scan the data
                         / \            and count which characters are
                  'a' = 1   0           more common and assign the codes
                           /  \         appropriately.
                   etc... 1    0
                              /  \
                                etc...

  Notice that if we use the full 256 ASCII characters we'll run into
  a problem with long strings of 0's.  We can get around that by using
  RLE (Which is what the compressor SQUEEZE uses).

  Again, since most files use a large range of the character set, and
  their occurences are much more "even", we can use use Dynamic Huffmann
  Codes as an alternative.  They are like their static cousins, only after
  the string of n zeros they are followed by n (binary) digits:

                1        = 1                             1 character
               01x       = 010, 011                      2 chars
              001xx      = 00100, 00101, 00110, 0011     4 chars
             0001xxx     = 0001000, 0001001 ... 0001111  8 chars
                    etc...

  As you can guess, the Huffmann Tree would look something like:

                      /\            It's a bit too complicated to
                     1  0           express with ASCII <g>
                       / \
                      1    0
                     / \   /\
                    1   0    etc...

  Huffmann Coding is based on how often an item (such as an ASCII
  character) occurs, and not where or in relation to other items.
  It's not the msot efficient mothod, but it is one of the simplest.
  One only needs to make an initial pass to count the characters and
  then re-pass translating them into the appropriate codes. No
  pattern-matching or search routines are required.

V.  Lampev-Ziv (LZ) Encoding.

  This method _does_ require some fast pattern-matching/search routines.
  It takes advantage of the fact that in most files (especially text)
  whole strings of characters repeat themselves.

  Take this sample line of text:

      "THAT WHICH IS, IS. THAT WHICH IS NOT, IS NOT. IS IT? IT IS!"

  (Ok, so "Flowers for Algernon" was on TV the other night... :)
  With LZ, we read in from the beginning of the file and keep adding
  groups ("Windows") of characters that have not already occurred.
  So we add the first sentence, then get to the second "IS"...instead
  of repeating it we note that it's a duplicate, with a reference
  to where the original occurred and how long the string is. (I.E. we note
  that the "IS" occurred 4 characters previously, and is two characters
  long.)

  This method can be tweaked by using a "Sliding Window" approach where the
  largest matches are found...we can compress the second "IS" with the first,
  but when don't gain much.  However the two "IS NOT"s, when matched against
  each other, would compress better.

  Our compressed file will have two types of data: the raw characters and
  the LZ-references (containing the pointer and length) to the raw
  characters, or even to other LZ-references.

  One way to tweak this further is to compress the LZ-References using
  Huffmann codes. (I think this is what's done with the ZIP algorithm.)

VI.  Lampev-Ziv-Welch (LZW) -- Not to be confused with LZ compression.

  This is the method used by Unix COMPRESS, as well as the GIF-graphics
  file format.

  Like LZ, LZW compression can compress a stream of data on one-pass
  relatively quickly (assuming you've got the fast search routines!).
  However, LZW uses a hash table (essentially it's an array of strings,
  also known as a string table), and a "match" is expressed as its index
  in the hash table rather than a reference to where and how long the
  match is.

  The input stream is read in, strings are assembled and sent out when
  they are already in the hash table, or they are added to the hash table
  and sent out in such a way that a decoder can still re-assemble the
  file.

  Needless to say, this method is a memory hog.  Most compressors that
  use this method are usually limited to a certain number of entries
  in the hash-table (12- or 16-bits, or 4096 and 65536 respectively).

  Here's an outline of the LZW Compression Algorithm:

         0. a. Initialize the hash table. (That means for each possible
               character there is one "root" entry in the table. Some
               flavors of LZW may actually have a "null" non-character
               at the base of the table.)
            b. Initialize the "current" string (S) to null.

         1. Read a character (K) from the input stream.
            (If there are none left, then we're done, of course.)

         2. Is the string S+K in the string-table?

         3. If yes, then a. S := S+K
                         b. Go to Step 1.

            If no, then  a. add S+K to the string table.
                         b. output the code for S
                         c. S := K
                         d. Go to Step 1.

  Decompression is very similar.

         0. a. Initialize the string table (the same as with compression).
            b. Read the first code from the compressed file into C
            c. Then output the equivalent string for code C
            d. Let code O := code C (The code, not the string!)

         1. Read the next code from the input stream into C

         2. Does code C exist in the string/hash table?

         3. If yes, then a. output the string for code C
                         b. S := equivalent string for code O
                         c. K := first character of the string for code C
                         d. add S+K to the string table

            If no, then  a. S := equivalent string for code O
                         b. K := first character of S
                         c. output S+K
                         d. add S+K to the table

         4. code O := code C

         5. Go to Step 1.

  It may seem psychotic at first, but it works.  Just keep reading it and
  thinking about it.  The best way is with a pencil and pad experimenting
  with a character set of four characters (A, B, C, and D) and a "word"
  like "ABACADABA" and following through the steps.

  (An actual walk-through is not included here, since it will take up
  *way* too much space.  I recommend getting further, more detailed
  descriptions of LZW if you plan on writing an implementation.)

  One important thing is to *not* confuse between the `code' for a string
  (it's index in the hash table) and the string itself.

  Two points about LZW implementations:

      1. The code stream (i.e. the compressed output) is not usually
         a set number of bits, but reflects how many entries are in
         the string table.  This is another way to further compress
         the data.

         Usually, LZW schemes will output the code in the number of bits
         exactly reflecting the string table.  Thus for the first 512
         codes the output is 9-bits.  Once the 513th string is added to
         the table, it's 10-bits and so on.

         Some implementations will use a constant output until a threshold
         is reached.  For example, the code output will always be 12-bits
         until the 4097th string is added, then the code output is in
         16-bit segments etc...

         If these scenarios are used, the decompression routine *must*
         "think ahead" so as to read in the proper number of bits from
         the encoded data.

      2. Because full string tables are incredible memory hogs, many
         flavors of LZW will use a "hash" table (see, string and hash
         table aren't quite the same).

         Instead of a string of characters like "ABC", there'll be
         a table containing the last character of the string, and a
         reference to the previous character(s).  Thus we'll have
         "A", "[A]B" and "[[A]B]C" where [x] is the reference (or the
         actual "code") for that character/string.  Using this method
         may be slower, but it saves memory and makes the implement-
         ation a little easier.
  There are many variations on LZW using other sets of strings to
  compare with the string table--this is based on the assumption that
  the more entries there are in the table, the more efficient the
  compression will be.

  One variation (Lampev-Ziv-Yakoo) would add the ButFirst(S+K) every
  time S+K was added. "ButFirst" means all characters but the first
  one. So ButFirst("ABCD") = "BCD".


Anyhow, those are the compression algorithms that I know about which I
can even remotely attempt to explain.
I apologize for any (glaring?) mistakes. It's late...what started as a
meaningless reply to somebody asking something about SQUEEZE exploded
into this post.  I hope it's useful to anybody interested.
}

[Back to FAQ SWAG index]  [Back to Main SWAG index]  [Original]