ExtendedSource checked

Arithmetic Coding

Encodes a message as a number inside a probability interval.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Compression
Difficulty: Advanced
Family: Entropy Coding
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 7
Code example: Not ready
Visualization: Ready

Overview

Arithmetic Coding narrows a numeric interval for each symbol according to its probability, often compressing close to entropy limits.

Core Concepts

probability modelcodeword encodingentropy codingsymbol representationlossless decodingstream encoding

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

When to Use

Use Arithmetic Coding when you need to maintain a shrinking probability interval.
Use it for entropy coding with inputs like symbol stream.
Use it when the data has repetition, predictable structure, or symbol frequency imbalance.
Use it when the Entropy Coding tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when small inputs or already compressed data would make metadata larger than the savings.
Avoid it when the required output is not compressed numeric code.

What It Does

Maintains a shrinking probability interval
Uses symbol probabilities to assign interval ranges

Use Cases

Entropy coding
Adaptive compression
Compression theory education

Inputs

Symbol stream
Probability model

Outputs

Compressed numeric code

Key Formulas (1)

Interval update

range_next = range_current · probability(symbol | context)

range_next = range_current * probability(symbol | context)

Shrinks the active numeric interval according to the probability of each symbol.

Pseudocode

1.Start with the full interval
2.Split the interval by symbol probabilities
3.Keep the subinterval for the next symbol
4.Emit bits whenever the interval range is determined
5.Finish with a code inside the final interval

Canonical Example

Input: text = 'AAAABBBCCDAA'
Output: compressed representation with repeated runs or shorter codes
Explanation: Arithmetic Coding: The algorithm replaces predictable or repeated structure with a more compact representation.

Implementation Notes

Keep the input contract explicit: Symbol stream; Probability model.
Use this step as the implementation spine: Start with the full interval.
Then preserve the next state change: Split the interval by symbol probabilities.
Keep encoder and decoder tests paired so every compressed sample round-trips exactly.

Common Pitfalls

Practical arithmetic coders handle finite precision carefully.
Forgetting that the decoder needs the same model, dictionary, or metadata used by the encoder.
Returning compressed numeric code without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show a probability interval shrinking after each symbol.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Start with the full interval

interval-coding

Notes

Arithmetic Coding operates in O(n) time and O(1) space within the Entropy Coding family. Key governing relation: range_next = range_current * probability(symbol | context). Often compared with Huffman Coding and Prediction by Partial Matching.