CONCEPT Cited by 1 source

Delta encoding¶

Definition¶

Delta encoding is a reversible transform that replaces each value in a sequence with the difference from its predecessor: x[i] → x[i] - x[i-1]. The first value is kept as-is (or encoded against a reference). It's lossless and trivially invertible: the decoder runs a prefix sum.

In the context of format-aware compression, delta encoding is a classic pre-entropy-coding transform: apply it before the entropy coder so that the entropy coder sees a much smaller-range, more-skewed distribution (mostly small deltas).

When it pays¶

Delta encoding wins when values are mostly sorted or locally correlated — the deltas are small and concentrated around zero, which entropy coders compress effectively. It loses when values are random or equidistributed — the deltas are as large as the values themselves and compression is no better than the original.

From the OpenZL post (Source: sources/2025-10-06-meta-openzl-an-open-source-format-aware-compression-framework):

"SRA0 is a position on the X axis. Due to the way the table is generated, the index is mostly sorted, inviting the use of delta to reduce the range of values represented. This mechanically makes the resulting stream easier to compress."

This is the canonical case: SRA0 is mostly sorted → small deltas → narrow entropy distribution → better compression ratio.

Contrast: the SDEC0 case¶

In the same sao example, SDEC0 (Y-axis position) is bounded but not sorted. Meta doesn't apply delta to it — instead it applies a transpose so the higher (more predictable) bytes group together. This illustrates that transform choice is a function of stream shape, not a per-field default — and it's exactly the choice OpenZL's trainer is responsible for making.

Broader family on the wiki¶

Delta encoding is one instance of delta-compression-ish techniques on the wiki; each operates on a different axis:

Delta encoding (this page) — within-stream differencing for numeric sequences during lossless compression.
concepts/git-delta-compression — inter-object deltas (diff a file against a similar file) as the core Git pack-file primitive.
concepts/delta-compression-http — inter-response deltas over HTTP using shared dictionaries (RFC 9842).

All three exploit redundancy, but along different axes (time, object graph, request history).

Seen in¶

sources/2025-10-06-meta-openzl-an-open-source-format-aware-compression-framework — OpenZL's canonical wiki example of delta encoding as a trained transform choice.

systems/openzl — where delta encoding is one transform in the trained sequence.
concepts/reversible-transform-sequence — the pattern delta encoding fits into.
concepts/format-aware-compression — the parent category.
concepts/structure-of-arrays-decomposition — SoA decomposition typically precedes delta encoding (need a homogeneous per-field stream for delta to be meaningful).
concepts/git-delta-compression · concepts/delta-compression-http — sibling delta techniques on different axes.