LZW compression

Concept

Lempel-Ziv-Welch(LZW)

• lossless compression
• fixed length code, usually 12 bits (257-4095)
• doesn’t require a dictonary to be sent alongside
• dictionary is rebuilt built during decoding
• used in:
  • GIF

Algorithm

1. initialize the dictionary, implicitly starting with all ASCII characters
2. start a substring buffer w = ""
3. take a new character k
4. check if w + k is in the dictionary
   • if already inside:
     • w = w + k, positive lookahead
   • else:
     • add a new entry in the dictionary for w + k
     • set w = k
5. repeat from step 3 until the end of the string

next_code = 257
w = ""

for each character k in input:
	if w + k is in dictionary:
		w = w + k
	else:
		output code(w)
		add (w + k) to dictionary with next_code
		next_code++
		w = k

output code(w)

abaabc

  abaabc -> 97 98 97 257 99
6×8 bits    5×12 bits

Application

Encoding

ABBAABBAABBAABBAABBA