Arithmetic Coding — Why Frame 500 Decodes Wrong

Huffman coding assigns whole bits to symbols. But what if a symbol has probability 0.99 — it deserves 0.015 bits, not 1? This mismatch between symbol probability and assigned bit length is the redundancy that arithmetic coding eliminates. For a message consisting of 99% one symbol, arithmetic coding compresses it ~65x better than Huffman.

Arithmetic coding is now in every modern video codec. H.264 uses CABAC (Context-Adaptive Binary Arithmetic Coding) — it is why H.264 achieves better quality than MPEG-2 at the same bitrate. H.265/HEVC and AV1 also use arithmetic coding at their core. Every Netflix stream, YouTube video, and Zoom call is decoded using arithmetic coding. The patent issues that delayed adoption for decades have expired, and it is now the standard.

By the end you'll understand why Huffman fails for skewed distributions, how arithmetic coding recursively divides the number line, the renormalization trick that makes integer implementation possible, and how CABAC uses context to adapt probabilities on the fly.

Arithmetic Coding: Precision Without Discrete Symbols

Arithmetic coding is a lossless compression algorithm that encodes an entire message as a single fractional number in [0,1). Unlike Huffman coding, which assigns a fixed-length bit pattern to each symbol, arithmetic coding maps the whole sequence to an interval that narrows with each symbol. The final interval is represented by a binary fraction — typically 1–3 bits shorter than Huffman for the same entropy.

In practice, the encoder maintains a current interval [low, high). For each symbol, it subdivides the interval proportionally to the symbol's probability. The decoder mirrors this process: given the encoded fraction, it determines which symbol's subinterval contains it, then updates the interval identically. The catch: finite precision arithmetic causes interval boundaries to drift. If the encoder and decoder use different rounding or precision (e.g., 32-bit vs 64-bit), the decoded interval can fall outside the expected range, corrupting the entire remaining stream.

Use arithmetic coding when symbol probabilities are skewed or when you need near-optimal compression (within 1% of entropy). It's standard in JPEG 2000, H.264/AVC CABAC, and bzip2. Avoid it in real-time systems without careful precision management — a single off-by-one in interval scaling can cascade into total decode failure.

The Core Idea

Arithmetic coding treats the message as a single number in the interval [0,1). The encoder recursively divides this interval according to symbol probabilities. After processing the entire message, any number in the final interval uniquely identifies it. The decoder works backwards: given the code, it finds which symbol's interval contains it, updates the interval, and repeats.

For a message "aab" with probabilities P(a)=0.5, P(b)=0.25, P(c)=0.25: - Start with [0,1). For 'a' (0 to 0.5), new interval [0, 0.5). - For second 'a' (0 to 0.5), subdivide [0,0.5) into [0,0.25), [0.25,0.375), [0.375,0.5). Second 'a' yields [0,0.25). - For 'b' in last symbol: within [0,0.25), 'b' covers [0.125,0.1875). - Final code = 0.15625 (midpoint). The decoder reverse-engineers this.

from fractions import Fraction

def arithmetic_encode(message: str, probs: dict) -> Fraction:
    """Encode message as a fraction in [0,1)."""
    # Build cumulative probability table
    symbols = sorted(probs)
    cum = {}
    total = Fraction(0)
    for s in symbols:
        cum[s] = total
        total += Fraction(probs[s]).limit_denominator(1000)
    low, high = Fraction(0), Fraction(1)
    for symbol in message:
        range_size = high - low
        high = low + range_size * (cum[symbol] + Fraction(probs[symbol]).limit_denominator(1000))
        low  = low + range_size * cum[symbol]
    return (low + high) / 2  # midpoint of final interval

def arithmetic_decode(code: Fraction, probs: dict, length: int) -> str:
    symbols = sorted(probs)
    cum = {}
    total = Fraction(0)
    for s in symbols:
        cum[s] = total
        total += Fraction(probs[s]).limit_denominator(1000)
    message = ''
    for _ in range(length):
        for s in reversed(symbols):
            if code >= cum[s]:
                message += s
                p = Fraction(probs[s]).limit_denominator(1000)
                code = (code - cum[s]) / p
                break
    return message

probs = {'a': 0.5, 'b': 0.25, 'c': 0.25}
msg = 'aab'
code = arithmetic_encode(msg, probs)
print(f'Encoded {msg!r} → {float(code):.6f}')
print(f'Decoded → {arithmetic_decode(code, probs, len(msg))!r}')

Why Arithmetic Beats Huffman

Huffman is only optimal when all probabilities are exact negative powers of 2 (0.5, 0.25, 0.125...). For any other distribution, Huffman's per-symbol integer-bit constraint wastes space. The redundancy is at most 1 bit per symbol, but that adds up. For a source with 30 symbols each with probability ~1/30, Huffman wastes about 1 bit per symbol. For highly skewed sources (one symbol dominant), the waste is even higher proportionally. Arithmetic coding's fractional-bit efficiency makes it ideal for contexts where probabilities are not powers of 2 — which is almost every real-world source.

import math
import heapq
from fractions import Fraction

# Huffman simulation (code length calculation)
def huffman_expected_length(probs):
    heap = [(p, []) for p in probs if p > 0]
    heapq.heapify(heap)
    while len(heap) > 1:
        p1, c1 = heapq.heappop(heap)
        p2, c2 = heapq.heappop(heap)
        for code in c1:
            code.append('0')
        for code in c2:
            code.append('1')
        heapq.heappush(heap, (p1 + p2, c1 + c2))
    codes = heap[0][1]
    code_lengths = [len(code) for code in codes]
    return sum(p * l for p, l in zip(probs, code_lengths))

# Entropy calculation
def entropy(probs):
    return -sum(p * math.log2(p) for p in probs if p > 0)

probabilities = [0.99, 0.01]
huff_len = huffman_expected_length(probabilities)
ent = entropy(probabilities)
print(f"Huffman expected length: {huff_len:.3f} bits/symbol")
print(f"Entropy: {ent:.3f} bits/symbol")
print(f"Redundancy: {huff_len - ent:.3f} bits/symbol")
print(f"For 1000 symbols: Huffman {1000 * huff_len} bits, optimal {1000*ent:.0f} bits")
print(f"Arithmetic coding (theoretically) can get within 0.001 bits/symbol of entropy")

# Multiple symbols scenario
probs_multi = [0.4, 0.3, 0.2, 0.1]
huff_multi = huffman_expected_length(probs_multi)
ent_multi = entropy(probs_multi)
print(f"\n4 symbols (0.4,0.3,0.2,0.1): Huffman {huff_multi:.2f}, Entropy {ent_multi:.2f}")
print(f"Waste: {huff_multi - ent_multi:.2f} bits/symbol, {1000 * (huff_multi - ent_multi):.0f} bits per KB")

Applications

JPEG2000: Replaces JPEG's Huffman with arithmetic coding for better quality at same bitrate. JPEG2000 uses EBCOT (Embedded Block Coding with Optimized Truncation) which works with arithmetic coding to achieve progressive decoding.

HEVC/H.265: CABAC (Context-Adaptive Binary Arithmetic Coding) — every modern video stream uses arithmetic coding. CABAC uses 399 different context models (for syntax elements like motion vectors, coefficients) with adaptive probability updates per symbol. This is why H.264/HEVC achieve 50% bitrate reduction over MPEG-2 for the same quality.

LZMA (xz/7-zip): Combines LZ77 with range coding (arithmetic coding variant) for best-in-class ratios. LZMA's range coder is byte-oriented and uses 4-byte low/high range and renormalisation.

PPM (Prediction by Partial Matching): Combines context modelling with arithmetic coding — near-theoretical compression on text. PPM uses context length (order-n) to predict next symbol probability, feeding that to arithmetic coding.

Modern codecs: AV1 (next-gen video) uses arithmetic coding with symbol-to-symbol probability adaptation. Daala (Xiph.org) used range coding. Zstandard (Facebook) uses ANS for better speed.

// Simplified CABAC-style renormalization in integer arithmetic
// From H.264 standard: range is in [2^8, 2^9) after renormalization

#include <stdint.h>

// Encoder state (as in CABAC)
typedef struct {
    uint32_t low;      // current interval low point (scaled integer)
    uint32_t range;    // current interval range (>= 256 << 16)
    uint8_t  pending;  // number of pending bits (for carry)
} CabacEncoder;

// Renormalisation: called when range < 256 << 16
void cabac_renorm(CabacEncoder *enc, void (*output)(uint8_t byte)) {
    while (enc->range < (256 << 16)) {
        if (enc->low < (1 << 24)) {  // No carry to propagate
            output(enc->low >> 24);   // Output highest byte
            for (int i = 0; i < enc->pending; i++) output(0xFF); // Emit pending 0xFFs
            enc->pending = 0;
        } else if (enc->low >= (3 << 24)) { // 3<<24 = 50331648
            output(((enc->low >> 24) + 1) & 0xFF); // Propagate carry
            for (int i = 0; i < enc->pending; i++) output(0x00); // Emit 0x00 for pending
            enc->pending = 0;
        } else {  // Pending carry case: low in [1<<24, 3<<24)
            enc->pending++;
            enc->low -= (1 << 24);
        }
        enc->low <<= 8;
        enc->range <<= 8;
    }
}

// Probability update (LPS = less probable symbol, MPS = more probable symbol)
typedef struct {
    uint16_t probLPS;  // Probability of LPS (0..32767, scaled to 2^15)
    uint8_t  mps;      // More probable symbol value (0 or 1)
} CabacContext;

// Update probability after encoding a symbol
void cabac_update(CabacContext *ctx, uint8_t encoded_symbol) {
    if (encoded_symbol == ctx->mps) {
        // Increase MPS probability: probLPS *= (1 - alpha) where alpha ~ 0.05
        ctx->probLPS -= ((ctx->probLPS) >> 5);  // multiply by 31/32
    } else {
        // LPS occurred: increase probLPS, swap MPS if necessary
        ctx->probLPS += ((32768 - ctx->probLPS) >> 5);  // increase toward 0.5
        if (ctx->probLPS > 16384) {  // > 0.5
            ctx->mps ^= 1;  // swap MPS/LPS
            ctx->probLPS = 32768 - ctx->probLPS;
        }
    }
}

Precision Budgeting: Your CPU Isn't Infinite

Arithmetic coding decimates Huffman on compression ratio, but it's a filthy resource hog if you don't manage precision. Every symbol update multiplies a range. Without integer arithmetic, your intervals bleed into floating-point noise and you get garbage decoded. Production systems don't use doubles. They use scaled integers with a fixed precision budget — usually 32 or 64 bits. You track the total range in a fixed-point register. When it shrinks below half, you renormalize. This is non-negotiable. If your codec uses floats in a core loop, your deployment will corrupt silently on edge cases. Why? Floating point loses precision progressively as intervals narrow. Integer arithmetic guarantees exact reproducibility across platforms. You trade a few cycles per symbol for correctness. Worth it. The industry learned this lesson the hard way with early JPEG-LS implementations. Don't re-learn it.

// io.thecodeforge — dsa tutorial

public class PrecisionBudget {
    private static final long PRECISION = 1L << 32; // 32-bit range
    private long low = 0;
    private long high = PRECISION;

    public void update(int total, int countBelow, int countCurrent) {
        long range = high - low;
        high = low + range * countBelow / total + range * countCurrent / total;
        low = low + range * countBelow / total;
        
        // Renormalize when interval is too small
        while ((high - low) < PRECISION / 4) {
            low = low << 1;
            high = high << 1;
            // Emit bit here in real code
        }
    }
}

Why Adaptive Models Aren't Optional

Static probability tables are a beginner trap. They assume you know the symbol distribution upfront. In real data — network packets, log streams, video frames — the distribution shifts constantly. A static coder wastes bits on improbable symbols or blows interval precision on sudden runs. Adaptive coding solves this. You start with a flat model (all symbols equally likely). After encoding each symbol, you update the frequency count. The model learns. It chases the real distribution. Why does this matter for your DSA bag of tricks? Because it turns a math-heavy algorithm into a practical streaming tool. Huffman needs a whole new tree on distribution change. Arithmetic coding just increments a counter. The cost is minimal: one integer increment per symbol, one cumulative total update. The gain is 5-15% better compression on real-world data. Implement adaptive models first. Static is only useful when you control the data format, like MP3 fixed codebooks.

// io.thecodeforge — dsa tutorial

public class AdaptiveModel {
    private int[] counts = new int[256];
    private int total = 0;

    public AdaptiveModel() {
        for (int i = 0; i < 256; i++) counts[i] = 1; // Prevent zero
        total = 256;
    }

    public int[] getCumulative(int symbol) {
        int below = 0;
        for (int i = 0; i < symbol; i++) below += counts[i];
        return new int[]{total, below, counts[symbol]};
    }

    public void update(int symbol) {
        counts[symbol]++;
        total++;
    }
}

Arithmetic vs. Huffman: The 'When to Fight' Matrix

Stop treating arithmetic coding as a universal upgrade over Huffman. It's not. Huffman wins on CPU budget. On an ARM Cortex-M0 or a web decoder parsing 4K video, Huffman's bit-by-bit tree walk is cheaper than arithmetic's multiply-and-renormalize loop. Arithmetic wins on skewed distributions — where one symbol appears 99% of the time. Huffman emits at least 1 bit per symbol. Arithmetic can emit 0.01 bits. That adds up. Your call? If compression ratio is the priority (archival, network-limited IoT), go arithmetic. If latency or battery life matters (streaming, real-time), stick with Huffman. I've seen teams throw arithmetic at a JSON log compressor and get 3% better ratio but 10x slower throughput. Their ops team burned them alive. Use the matrix: symbol count under 256? Huffman can be table-driven fast. Over 256 with sparse distribution? Arithmetic with context modeling dominates. Know your deployment, not the textbook.

// io.thecodeforge — dsa tutorial

public class WhenToFightMatrix {
    // Decision: Huffman if symbols < 32 OR speed critical, else Arithmetic
    public static boolean useArithmetic(double entropyBits, int distinctSymbols, boolean speedCritical) {
        if (speedCritical && distinctSymbols < 32) {
            return false; // Huffman table fits in cache
        }
        // Arithmetic saves when entropy < 1 bit per symbol
        return entropyBits < 0.8;
    }
}

// Output: true if arithmetic wins ratio, false for Huffman

Step by Step Learning: Why Scalar Math Is a Dead End

Most textbooks teach arithmetic coding with die rolls and coin flips. That's trader bait. In production, you're encoding byte streams with adaptive models that shift probabilities every symbol. You need integer arithmetic on a fixed range — nothing else works.

The machine doesn't care about your fractions. CPUs hate division. So we use integer intervals: low and high, scaled to 32-bit precision. Each symbol splits the range proportionally. When low and high converge on the most significant bit, you emit that bit and double the range back out. That's the core loop. No floating point. No recursion. Just integer math with careful overflow guards.

If your encoder and decoder don't agree on the exact same probability table for each step, your output is garbage. That's why you synchronize the model state before every symbol. This isn't theory — it's the difference between shipping and a pager at 3 AM.

// io.thecodeforge — dsa tutorial

public class ArithmeticEncoder {
    private long low = 0;
    private long high = 0xFFFFFFFFL;
    private long pending = 0;

    public void encode(int symbol, int total, int[] cumFreq) {
        long range = high - low + 1;
        high = low + (range * cumFreq[symbol + 1] / total) - 1;
        low = low + (range * cumFreq[symbol] / total);
        while ((low ^ high) >>> 24 == 0) {
            emit((int)(high >>> 24));
            low <<= 8;
            high = (high << 8) | 0xFF;
        }
    }

    private void emit(int b) { /* send byte to output stream */ }
}

Fundamentals: The Interval Is Your State Machine

Forget coding trees. Arithmetic coding doesn't assign a codeword per symbol. It grows a single interval that represents the entire message. Every symbol narrows that interval. The narrower the interval, the more bits you need to distinguish it. That's directly proportional to the information content — Shannon would approve.

Your state is just two numbers: low and high. They define a fraction of the number line between 0 and 1. But in production, you scale that to 0 to 2^32 – 1. Each symbol splits the current range by its probability. The high-probability symbol gets a fat slice; the low-probability symbol gets a sliver. The encoder doesn't care about the symbol value — only its cumulative frequency in the model.

This is why arithmetic coding beats Huffman on skewed distributions: it can encode a 99% probable symbol with less than one bit. Huffman rounds up to at least one bit per symbol. Arithmetic doesn't round — it just narrows the interval. That's the mathematical advantage, not a gimmick.

// io.thecodeforge — dsa tutorial

public class IntervalState {
    private long low = 0;
    private long high = 0xFFFFFFFFL;

    public void update(int symbol, int total, int[] cumFreq) {
        long range = high - low + 1;
        high = low + (range * cumFreq[symbol + 1] / total) - 1;
        low = low + (range * cumFreq[symbol] / total);
    }

    public boolean needsRescale() {
        return (low ^ high) >>> 24 == 0;
    }

    public long getHigh() { return high; }
    public long getLow() { return low; }
}

Maths, Pattern & Recursion: The Link between Rescaling and Recursion

Every time you rescale the interval — low and high share the high byte — you emit a bit and double the range. That's a recursive pattern dressed in a while loop. The same operation repeats: narrow, emit, expand. The recursion isn't in function calls, it's in the math. Each rescaling step is a smaller instance of the same problem: encode the remaining symbols into a newly doubled range.

This pattern makes arithmetic coding fast. CPUs love tight loops. The rescaling happens naturally when the interval drifts into the safe zone. If you trace the bits emitted, you'll see a self-similar structure: each emitted bit represents a binary decision that halves the remaining uncertainty. That's pure Shannon. No Huffman tree traversal. No lookup tables.

The recursion is also why you need a terminating symbol. Without it, the decoder can't know when to stop. Pad the input with a high-probability EOF symbol, or emit the final state as an explicit flush. Production code always does both.

// io.thecodeforge — dsa tutorial

public class RescaleLoop {
    private long low = 0;
    private long high = 0xFFFFFFFFL;
    private long pending = 0;

    public void rescale() {
        while ((low ^ high) >>> 24 == 0) {
            int bit = (int)(high >>> 24);
            // emit bit + (pending++) for carry propagation
            low = (low << 8) & 0xFFFFFFFFL;
            high = ((high << 8) | 0xFF) & 0xFFFFFFFFL;
        }
    }
}

Bit Manipulation: The Backend of Interval Arithmetic

Huffman coding and fixed-point arithmetic fail at long precision because they rely on integer boundaries. Bit manipulation solves this by treating the encoder's interval as a fixed-width register where multiplication and division are replaced with shifts and masks. Why this matters: At each coding step, you split the interval proportionally to symbol probabilities. With a 32-bit register, you halve the range using a right shift instead of floating-point division. The low and high bounds become bit patterns you scan for leading zeros—when both share the same leading bits, you emit them as output. This is how real codecs like JPEG 2000 achieve streaming: they emit a bit the moment it becomes certain, not after the entire message. The price is careful overflow handling: because probability scaling requires multiplication without exceeding the register width, you use a status register and renormalization loops. Without bit manipulation, arithmetic coding remains a classroom abstraction.

// io.thecodeforge — dsa tutorial

public class BitScaleEncoder {
    private int low = 0;
    private int range = 0x7FFFFFFF;

    public void encode(int probabilityNumerator, int total) {
        int step = range / total;
        int cutoff = step * probabilityNumerator;
        range = cutoff;
        // Renormalize when leading bits match
        while ((low & 0x40000000) == ((low + range) & 0x40000000)) {
            System.out.print((low >> 30) & 1);
            low <<= 1;
            range <<= 1;
            low &= 0x7FFFFFFF;
            range &= 0x7FFFFFFF;
        }
    }
}

Prefix Sum: Accelerating Adaptive Probability Tables

Adaptive arithmetic coding updates symbol frequencies after each encoded symbol. A naive implementation recomputes cumulative probability sums in O(alphabet size) per symbol, crippling throughput on large alphabets. The prefix sum structure—a Fenwick tree or binary indexed tree—cuts that to O(log alphabet). Why this works: The cumulative count for any symbol is the sum of all frequencies before it. A Fenwick tree stores partial sums in an array where index i covers frequencies from i - LSB(i) + 1 to i. After encoding symbol s, you increment its frequency by adding 1 at position s in the tree. The total range (needed for interval split) is the sum of all frequencies—stored at the tree root. The split point for symbol s becomes prefix_sum(s-1) plus the current symbol's count. This reduces per-symbol cost from O(256) for byte alphabets to O(8), and scales to Unicode or adaptive contexts. Without prefix sums, adaptive coding with large alphabets becomes impractical.

// io.thecodeforge — dsa tutorial

class FenwickProbTable {
    private int[] tree = new int[256];

    public void add(int idx, int delta) {
        for (; idx < tree.length; idx += idx & -idx)
            tree[idx] += delta;
    }

    public int sum(int idx) {
        int s = 0;
        for (; idx > 0; idx -= idx & -idx)
            s += tree[idx];
        return s;
    }


    public int total() { return sum(tree.length - 1); }
}

Dynamic Programming: Optimal Probability Granularity

Arithmetic coding's compression ratio depends on how precisely probabilities are represented. Fixed-point integers with 16 bits give 65536 distinct intervals—enough for text but wasteful for binary data. Dynamic programming finds the optimal bit budget for each symbol's probability to minimize total code length. Why it's needed: Given an alphabet with frequencies, the problem is to assign each symbol a probability granularity (e.g., 8 vs 12 bits) such that the sum of all granularities fits a fixed total (e.g., 32 bits) and the redundancy—the gap between actual entropy and coded length—is minimized. This is a knapsack where each symbol's 'cost' is extra bits used per coding step and 'weight' is the bits added to the probability denominator. Solve with DP over symbols and remaining bit budget: dp[i][b] = min redundancy for first i symbols with b bits left. The recurrence is dp[i][b] = min over granularity g of dp[i-1][b-g] + freq[i] * (log2(total) - log2(granularity)). Without this optimization, codecs waste 10–30% bits on over-precise rare symbols.

// io.thecodeforge — dsa tutorial

public class ProbGranularityDP {
    static double minRedundancy(int[] freq, int totalBits) {
        int n = freq.length;
        double[][] dp = new double[n+1][totalBits+1];
        for (int i = 1; i <= n; i++) {
            for (int b = 1; b <= totalBits; b++) {
                dp[i][b] = Double.MAX_VALUE;
                for (int g = 2; g <= b; g+=2) {
                    double red = freq[i-1] * (Math.log(totalBits) - Math.log(g));
                    dp[i][b] = Math.min(dp[i][b], dp[i-1][b-g] + red);
                }
            }
        }
        return dp[n][totalBits];
    }
}

List & Dictionary: The Polymorphic Pair

In arithmetic coding, you rarely store a flat list of symbols. When building adaptive probability tables, your dictionary (or map) from symbol to frequency count must support fast lookups and updates. A HashMap offers O(1) average complexity, but can fragment memory. For small alphabets like ASCII text, an array-backed list indexed by character code is faster and cache-friendly. The structural difference matters: dictionaries excel at sparse, arbitrary symbol sets (e.g., words in natural language), while lists are optimal for dense, continuous ranges. Your choice directly impacts compression speed: every encoding step queries the probability of the next symbol. Use a list when the symbol space is contiguous and bounded; use a dictionary when symbols are unpredictable or dynamically added. In Java, you can switch between HashMap and int[] for the same interface, letting you benchmark memory vs. throughput without changing core logic.

// io.thecodeforge — dsa tutorial
public class ProbTable {
    private int[] freqs;        // list for dense alphabet
    private int total;
    public ProbTable(int size) {
        freqs = new int[size];
    }
    public void update(int symbol) {
        freqs[symbol]++;
        total++;
    }
    public double getProb(int symbol) {
        if (total == 0) return 0.0;
        return (double) freqs[symbol] / total;
    }
}

Searching & Sorting: The Order of Probability

Arithmetic coding depends on maintaining cumulative probability intervals. After building a frequency table, you need to locate the interval for a given symbol—a search over cumulative sums. A naive linear scan is O(n) per symbol, fine for tiny alphabets. But for large alphabets (e.g., Unicode), you need binary search on a prefix sum array, reducing lookup to O(log n). Sorting becomes critical when you want to encode symbols in descending probability order: it minimizes the number of interval subdivisions, slightly improving compression. More importantly, sorted symbols enable logarithmic-time interval search when combined with a binary search tree (like java.util.TreeMap). Use Java's Arrays.binarySearch on a precomputed cumulative array for fast encoding, but keep the table sorted only when rebuilding intervals, not every step. This intersection of sorting and searching is what makes adaptive arithmetic coding practical for non-toy applications.

// io.thecodeforge — dsa tutorial
public class SearchInterval {
    private int[] cumFreq;
    public SearchInterval(int[] cumFreq) {
        this.cumFreq = cumFreq;
    }
    public int findSymbol(double point) {
        int idx = Arrays.binarySearch(cumFreq, (int)(point * cumFreq[cumFreq.length-1]));
        if (idx < 0) idx = -idx - 1;
        return idx;
    }
}

Stack & Linked List: Memory Sequence Control

Arithmetic coding doesn't borrow stacks or linked lists directly, but they appear in two hidden hotspots. First, decoding recursively consumes a stream of bits; a stack mirrors the recursion depth when you must buffer pending intervals during model adaptation. If your model updates mid-stream, you push old states onto a stack to restore them after resolving a carry. Second, linked lists become essential when you implement a multi-symbol probability table with dynamic insertion—like adding new symbols without resizing a fixed array. Each node holds (symbol, frequency) and a pointer; encoding visits nodes sequentially until it finds the input symbol. For small alphabets (< 64 symbols), a linked list is slower than an array but more memory-flexible. In Java, avoid LinkedList due to node overhead; use ArrayDeque for stack operations. Real code rarely uses a pure linked list for interval tracking, but understanding its trade-offs helps when building external APIs that stream symbols.

// io.thecodeforge — dsa tutorial
import java.util.ArrayDeque;
public class AdaptiveStack {
    private ArrayDeque<int[]> stateStack = new ArrayDeque<>();
    public void saveState(int[] freqs) {
        stateStack.push(freqs.clone());
    }
    public void restoreState() {
        int[] saved = stateStack.pop();
        System.arraycopy(saved, 0, freqs, 0, saved.length);
    }
    private int[] freqs;
}