Lempel-Ziv-Welch (LZW)
Dictionary-based lossless compression building table of string sequences. Used in GIF, TIFF, PDF. Patented algorithm (expired 2004). Adaptive compression requiring no prior knowledge of input.
Visualization
Interactive visualization for Lempel-Ziv-Welch (LZW)
Interactive visualization with step-by-step execution
Implementation
1class LZW {
2 encode(data: string): number[] {
3 // Initialize dictionary with ASCII characters
4 const dictionary = new Map<string, number>();
5 for (let i = 0; i < 256; i++) {
6 dictionary.set(String.fromCharCode(i), i);
7 }
8
9 let dictSize = 256;
10 let current = '';
11 const result: number[] = [];
12
13 for (const char of data) {
14 const combined = current + char;
15
16 if (dictionary.has(combined)) {
17 current = combined;
18 } else {
19 result.push(dictionary.get(current)!);
20 dictionary.set(combined, dictSize++);
21 current = char;
22 }
23 }
24
25 if (current) {
26 result.push(dictionary.get(current)!);
27 }
28
29 return result;
30 }
31
32 decode(encoded: number[]): string {
33 // Initialize dictionary with ASCII characters
34 const dictionary = new Map<number, string>();
35 for (let i = 0; i < 256; i++) {
36 dictionary.set(i, String.fromCharCode(i));
37 }
38
39 let dictSize = 256;
40 let previous = String.fromCharCode(encoded[0]);
41 let result = previous;
42
43 for (let i = 1; i < encoded.length; i++) {
44 const code = encoded[i];
45 let entry: string;
46
47 if (dictionary.has(code)) {
48 entry = dictionary.get(code)!;
49 } else if (code === dictSize) {
50 entry = previous + previous[0];
51 } else {
52 throw new Error('Invalid compressed data');
53 }
54
55 result += entry;
56 dictionary.set(dictSize++, previous + entry[0]);
57 previous = entry;
58 }
59
60 return result;
61 }
62
63 compressionRatio(original: string, encoded: number[]): number {
64 const originalBits = original.length * 8;
65 const encodedBits = encoded.length * 12; // Assuming 12-bit codes
66 return (1 - encodedBits / originalBits) * 100;
67 }
68}Deep Dive
Theoretical Foundation
Builds dictionary dynamically during compression. Starts with single-character entries. Reads longest match in dictionary, outputs code, adds match+next char to dictionary. Decoder rebuilds same dictionary. Compression ratio improves as dictionary grows. GIF uses 12-bit codes (4096 entries).
Complexity
Time
O(n)
O(n)
O(n)
Space
O(dictionary size)
Applications
Industry Use
GIF image format compression
TIFF image format (LZW option)
PDF document compression
Unix compress utility
PostScript Level 2 compression
Network data compression
Backup software compression
Use Cases
Related Algorithms
A* Search Algorithm
Informed search algorithm combining best-first search with Dijkstra's algorithm using heuristics. Widely used in pathfinding and graph traversal, A* is optimal and complete when using admissible heuristic. Used in games, GPS navigation, and robotics. Invented by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968.
Convex Hull (Graham Scan)
Find smallest convex polygon containing all points. Graham Scan invented by Ronald Graham in 1972, runs in O(n log n). Essential in computational geometry, computer graphics, and pattern recognition.
Line Segment Intersection
Determine if two line segments intersect. Fundamental geometric primitive used in graphics, CAD, GIS. Uses orientation and collinearity tests.
Caesar Cipher
The Caesar Cipher is one of the oldest and simplest encryption techniques, named after Julius Caesar who used it to protect military messages around 100 BC. It works by shifting each letter in the plaintext by a fixed number of positions down the alphabet. For example, with a shift of 3, A becomes D, B becomes E, and so on. Despite being used for over 2000 years, it's extremely weak by modern standards with only 25 possible keys, making it trivially breakable by brute force or frequency analysis.