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-2021 - Michael Kohn