GZIP Information (IGZIP)

What is GZIP Information?

IGZIP is a practical, length-based information measure that assigns information content to data by running real-world GZIP compression (DEFLATE: LZ77 + Huffman) and taking the compressed size in bits. Intuitively, more regular and repetitive data compresses better and yields a smaller IGZIP value, while random-looking data compresses poorly and yields a larger IGZIP value.

Short history

GZIP builds on the DEFLATE format, which combines LZ77 (1977) dictionary sliding-window parsing with Huffman coding. The .gzip container and DEFLATE became widely adopted in the 1990s for fast, lossless, general-purpose compression across operating systems and network tools. Because DEFLATE is deterministic and ubiquitous, IGZIP is straightforward to implement and compare across platforms.

Physical meaning

IGZIP operationalizes the idea that “structure is compressible.” If a dataset contains patterns, repetitions, or predictable motifs, GZIP can represent it with fewer bits; if it is pattern-poor, it needs more bits. Thus, IGZIP reflects the minimum number of bits needed by this specific compressor to reproduce the original data, capturing practical regularities that a real-world algorithm can exploit.

Mathematical properties

Definition (raw, in bits)

\[ I_{\mathrm{GZIP}}(x) = 8 \,\lvert \mathrm{GZIP}(x) \rvert \]

Here \(\lvert \mathrm{GZIP}(x) \rvert\) is the compressed length in bytes of the byte sequence \(x\); multiplying by 8 converts to bits.

Reference baselines (implementation-aligned)

\[ I_{\mathrm{GZIP}}^{\mathrm{min}}(n) = 8\,\lvert \mathrm{GZIP}(0^{n}) \rvert \]
\[ I_{\mathrm{GZIP}}^{\mathrm{max}}(x) = 8\,\lvert \mathrm{GZIP}(\mathrm{Rand}(x)) \rvert \]

Explanation. \(I_{\mathrm{GZIP}}^{\mathrm{min}}(n)\) is the compressed size of an all-zero byte array of the same length \(n\) (best-case structure). \(I_{\mathrm{GZIP}}^{\mathrm{max}}(x)\) is the compressed size of a length-matched pseudorandom array (worst-case, near-incompressible).

Normalized IGZIP (mapping the raw value into a target range set by separate lower/upper information baselines \(I_{\min}(x)\), \(I_{\max}(x)\) computed by your MinInfo and MaxInfo components):

\[ \widetilde{I}_{\mathrm{GZIP}}(x) = \mathrm{scale}\!\bigl(I_{\mathrm{GZIP}}(x);\ I_{\mathrm{GZIP}}^{\mathrm{min}}(n),\ I_{\mathrm{GZIP}}^{\mathrm{max}}(x)\ \rightarrow\ I_{\min}(x),\ I_{\max}(x)\bigr) \]

where the scaling function is the standard affine map with capping at the upper bound:

\[ \mathrm{scale}(v;\ a,b \rightarrow c,d) = \min\!\Bigl(d,\ c + \frac{(v – a)}{(b – a)} (d – c)\Bigr) \]

Basic bounds. For an \(n\)-byte input, \(I_{\mathrm{GZIP}}(x)\) is finite and upper bounded by the trivial encoding plus container overhead. Typical implementations satisfy

\[ 0 \le I_{\mathrm{GZIP}}(x) \le 8n + O(1) \]

Non-additivity. IGZIP is not strictly additive: \(I_{\mathrm{GZIP}}(xy)\) need not equal \(I_{\mathrm{GZIP}}(x)+I_{\mathrm{GZIP}}(y)\) because cross-boundary matches in LZ77 create shared structure upon concatenation.

Monotone preprocessing sensitivity. Simple, invertible transformations (e.g., byte reordering, container headers) can change IGZIP by affecting dictionary matches and literal distributions; thus IGZIP is compressor- and parameter-dependent.

Relation to Kolmogorov complexity

Conceptually, \(K(x)\) (Kolmogorov complexity) is the length of the shortest program that outputs \(x\) on a fixed universal machine. Because \(K(x)\) is uncomputable, IGZIP serves as a computable upper bound proxy: a smaller IGZIP suggests more structure and potentially lower \(K(x)\), while a larger IGZIP suggests greater algorithmic randomness. However, IGZIP depends on a specific compressor (DEFLATE), window size, and headers, so it is only a practical estimate, not a machine-invariant quantity like \(K(x)\).

Limitations and remarks

Compressor dependence. Results depend on GZIP implementation details (window size, strategy, header/footer), so values are comparable only under consistent settings.

Short-input effects. Very small inputs are dominated by header overhead; your implementation handles length-1 inputs specially (returns 1) to avoid degenerate scaling.

Normalization choice. The min (all-zeros) and max (random) GZIP baselines reflect “best” and “worst” compressibility for length-matched data. Mapping the raw value into a problem-specific target range via MinInfo/MaxInfo improves interpretability across domains, but the normalization remains heuristic and task-dependent.

Concatenation and context. Because LZ77 reuses earlier substrings, IGZIP for a segment may change when measured in isolation vs. embedded within a larger stream.

Not an entropy estimator. IGZIP is not the Shannon entropy (IS); it measures achieved codelength under DEFLATE on a specific instance, not the expected code length under the true source distribution.

Pseudocode

# IGZIP: GZIP-based information measure with normalization

function IGZIP_value(input):
    # Handle null/empty
    if input is null or length(input) < 1:
        return 0

    # Length-1 shortcut (implementation detail)
    if length(input) == 1:
        return 1

    # Ensure bytes
    bytes = toBytes(input)  # strings: UTF-8, collections: serialize

    # Raw GZIP info in bits
    gzip_bits = length(GZIP(bytes)) * 8

    # Baselines for this length
    n = length(bytes)
    min_gzip_bits = length(GZIP(zeros(n))) * 8
    max_gzip_bits = length(GZIP(randomBytesLike(bytes))) * 8

    # Compute target bounds via MinInfo/MaxInfo (domain-specific)
    Imin = MinInfo.value(input)  # lower target
    Imax = MaxInfo.value(input)  # upper target

    # Normalize by affine scaling from [min_gzip_bits, max_gzip_bits] to [Imin, Imax]
    if max_gzip_bits == min_gzip_bits:
        return (Imin + Imax) / 2

    scaled = Imin + ( (gzip_bits - min_gzip_bits) / (max_gzip_bits - min_gzip_bits) ) * (Imax - Imin)

    # Cap at upper bound (mirrors implementation)
    return min(Imax, scaled)