Overview
Run-Length Encoding replaces stretches such as AAAA with a compact count and value pair. It is simple and effective when long repeated runs are common.
FoundationSource checked
Run-Length Encoding
Compresses repeated consecutive values by storing each value with its run length.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Compression
- Difficulty
- Beginner
- Family
- Lossless Compression
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- RLE
Core Concepts
run lengthliteral valuelossless compressionrepetition
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)
When to Use
- Use it when data contains long consecutive repetitions.
- Use it as a simple preprocessing or baseline compression method.
- Use it for masks, simple images, or sparse repeated symbols.
When Not to Use
- Avoid it on data with few repeated runs because it may increase size.
- Avoid it when the format cannot represent counts unambiguously.
- Avoid it as a general-purpose compressor without entropy or dictionary coding.
What It Does
- Finds consecutive repeated symbols
- Stores each run compactly
Use Cases
- Simple image compression
- Compressing repeated text
- Teaching lossless compression
Inputs
- Sequence of symbols
Outputs
- Sequence of symbol-count pairs
Key Formulas (1)
Run token
run = (symbol, count)
run = (symbol, count)Stores one repeated stretch as the value and the number of times it appears.
Pseudocode
- 1.Start with the first symbol
- 2.Count how many times it repeats consecutively
- 3.Write the symbol and count
- 4.Move to the next different symbol
- 5.Repeat until the input ends
Canonical Example
- Input
- text = 'AAAABB'
- Output
- encoded = A4 B2
- Explanation
- Run-Length Encoding: Stores each repeated run as a symbol and count.
Implementation Notes
- Emit a run only when the current value changes or the maximum count is reached.
- Specify whether counts are one-based and how literal values are represented.
- Test empty input, single-symbol input, and runs longer than the maximum encoded count.
Common Pitfalls
- Forgetting that short runs can expand the encoded data.
- Choosing a count representation that cannot handle long runs.
- Failing to escape count markers when encoding arbitrary byte streams.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow repeated blocks collapsing into count labels.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Start with the first symbol
run-compressionNotes
RLE is often combined with other transforms that create longer runs.
Sources (1)
What each reference supports for this entry.
Introduction to Data Compression
BookData compression textbook reference for the coding or dictionary method used by Run-Length Encoding.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withBurrows-Wheeler Transform
BWT can create runs that make run-length encoding more effective.
Alternative toHuffman Coding
RLE exploits repeated runs while Huffman coding exploits symbol frequencies.
Related Algorithms
Tags
CompressionEncodingClassic