LZW Fundamentals
Lempel and Ziv published initial algorithm in 1977,
Welch published refinements in 1984.
Basic Idea:
- Replaces strings of characters with single integer codes
- A table of string/code pairs is built as the compression algorithm reads
the input file
- The table is reconstructed as the decompression algorithm reads \
the compressed file.
Now, let s suppose our input stream we wish to compress is "banana_bandana", and that we are only using the initial dictionary:
Index Entry
0 a
1 b
2 d
3 n
4 _ (space)
The encoding steps would proceed like this:
Input Current String Seen this Before? Encoded Output New Dictionary Entry/Index
B b yes nothing None
Ba ba no 1 ba / 5
Ban an no 1,0 an / 6
Bana na no 1,0,3 na / 7
Banan an yes no change None
Banana ana no 1,0,3,6 ana / 8
Banana_ a_ no 1,0,3,6,0 a_ / 9
banana_b _b no 1,0,3,6,0,4 _b / 10
banana_ba ba yes no change None
banana_ban ban no 1,0,3,6,0,4,5 ban / 11
banana_band nd no 1,0,3,6,0,4,5,3 nd / 12
banana_banda da no 1,0,3,6,0,4,5,3,2 da / 13
banana_bandan an yes no change None
banana_bandana ana yes 1,0,3,6,0,4,5,3,2,8 None