This was pretty much ripped off from The File Formats Handbook. If you can still find this book, this is one of the absolute best books for learning file formats. The explanations are very clear, especially compared to other file format books I've bought. Note that this example doesn't take into account that GIF's LZW has a Clear Code and an EOF code.

For source code examples see my compression page.

Compression:

initialize table
clear buffer [..]

While NOT EOF Do
  read in code K

  If [..]K in table
    [..] <- [..]K
  Else
    output index of [..]
    [..] <- K
  End If
Wend

Example:

Input codes: ABACABA

Table Starts out as:

code  |  char
--------------
 0    |   A
 1    |   B
 2    |   C
 3    |   D

(yes D isn't used, but 4 bits represents 4 chars)

Table at the end of the algorithm is:

code  |  char
--------------
 0    |   A
 1    |   B
 2    |   C
 3    |   D
 4    |   AB
 5    |   BA
 6    |   AC
 7    |   CA
 8    |   ABA

Output codes: 0 1 0 2 4 0


Decompression:

Initalize table
code := first code
output table[code]
old := code

While NOT EOF Do
  code := next code
  If table[code] exists
    output table[code]
    [..] <- table[old]
    K <- first code of table[code]
    write [..]K into table as next code
    old := code
  Else
    [..] <- table[old]
    K <- first char of [..]
    output [..]K
    write [..]K into table as next code
    old := code
  End If

Wend


Table Starts out as:

code  |  char
--------------
 0    |   A
 1    |   B
 2    |   C
 3    |   D

using the decompression algorithm, the table will be rebuilt
as it looks during compression

Copyright 1997-2024 - Michael Kohn