Back to Compression
LZW Compression
Lempel-Ziv-Welch dictionary-based compression algorithm
Algorithm Type
Dictionary-based, lossless compression
Time Complexity
O(n) - single pass through data
Applications
GIF, TIFF, PDF compression formats
LZW Compression Simulator
LZW Algorithm Explanation
How LZW Works
1. Initialize Dictionary: Start with all single characters (0-255 for ASCII)
2. Read Input: Process input character by character
3. String Matching: Find the longest string in dictionary that matches current input
4. Output Code: Output the code for the matched string
5. Update Dictionary: Add the matched string + next character to dictionary with new code
6. Repeat: Continue until all input is processed
Advantages
- • Single pass compression
- • Adaptive dictionary building
- • Good compression for repetitive text
- • No need to store dictionary
- • Suitable for streaming data
Disadvantages
- • Dictionary can grow very large
- • Poor performance on random data
- • Patent restrictions (expired now)
- • Fixed-width codes limit efficiency
- • Memory intensive for large dictionaries
📝 Exam Preparation Tips
Key Points to Remember
- • Dictionary starts with all single characters (0-255)
- • Always output code for longest match found
- • Add concatenation of match + next char to dictionary
- • New dictionary entries get sequential codes (256, 257, ...)
- • Decompression can rebuild dictionary from codes alone
Common Exam Questions
- • "Compress given string using LZW" (10 marks)
- • "Show dictionary building process" (8 marks)
- • "Explain LZW compression steps" (6 marks)
- • "Compare LZW with Huffman coding" (5 marks)
- • "Calculate compression ratio" (3 marks)