Run-Length Encoding (RLE)
Simple lossless compression replacing sequences of same character with count+character. Effective for data with many consecutive repeated values. Used in BMP, TIFF formats.
Visualization
Interactive visualization for Run-Length Encoding (RLE)
Interactive visualization with step-by-step execution
Implementation
1class RunLengthEncoding {
2 encode(data: string): string {
3 if (!data) return '';
4
5 let encoded = '';
6 let count = 1;
7 let current = data[0];
8
9 for (let i = 1; i < data.length; i++) {
10 if (data[i] === current && count < 255) { // Limit count to prevent overflow
11 count++;
12 } else {
13 encoded += count + current;
14 current = data[i];
15 count = 1;
16 }
17 }
18
19 encoded += count + current; // Append last run
20 return encoded;
21 }
22
23 decode(encoded: string): string {
24 let decoded = '';
25 let i = 0;
26
27 while (i < encoded.length) {
28 // Extract count
29 let count = '';
30 while (i < encoded.length && /d/.test(encoded[i])) {
31 count += encoded[i];
32 i++;
33 }
34
35 // Extract character
36 if (i < encoded.length) {
37 const char = encoded[i];
38 decoded += char.repeat(parseInt(count));
39 i++;
40 }
41 }
42
43 return decoded;
44 }
45
46 // For binary data (array of numbers)
47 encodeBinary(data: number[]): { counts: number[]; values: number[] } {
48 if (data.length === 0) return { counts: [], values: [] };
49
50 const counts: number[] = [];
51 const values: number[] = [];
52
53 let count = 1;
54 let current = data[0];
55
56 for (let i = 1; i < data.length; i++) {
57 if (data[i] === current) {
58 count++;
59 } else {
60 counts.push(count);
61 values.push(current);
62 current = data[i];
63 count = 1;
64 }
65 }
66
67 counts.push(count);
68 values.push(current);
69
70 return { counts, values };
71 }
72
73 decodeBinary(counts: number[], values: number[]): number[] {
74 const decoded: number[] = [];
75
76 for (let i = 0; i < counts.length; i++) {
77 for (let j = 0; j < counts[i]; j++) {
78 decoded.push(values[i]);
79 }
80 }
81
82 return decoded;
83 }
84
85 compressionRatio(original: string, encoded: string): number {
86 return (1 - encoded.length / original.length) * 100;
87 }
88}Deep Dive
Theoretical Foundation
Scans input and replaces runs of identical symbols with (count, symbol) pairs. Example: 'AAAABBBCC' → '4A3B2C'. Best for data with long runs (images, fax). Worst case: doubles size if no repeats. Variants use different escape sequences.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(n) worst case
Applications
Industry Use
BMP and TIFF image compression
Fax machine data transmission
Simple bitmap compression
PCX image format
Preprocessing for other compression algorithms
Video compression (motion vectors)
Network protocol optimization
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.