lzcomplexity-core

The algorithmic core of lzcomplexity — information-theoretic complexity measures for symbolic sequences, based on Lempel–Ziv 76 (LZ76) factorization.

This is pure Rust with no Python or CLI dependencies. It powers the lzcomplexity Python package (via PyO3) and the lzcomplexity / lzdistance standalone binaries, and can be used directly as a Rust library.

What it computes

LZ76 factorization — the complexity c(S) (factor count) and the factor boundaries, via a linear-time suffix array + longest-previous-factor.
Entropy density — the normalized entropy-rate estimator h ≈ c(S)·log_k(n)/n, which converges to the true entropy rate of ergodic sources.
Effective measure complexity (EMC) — a block-entropy (excess-entropy) estimator via random block shuffling.
Normalized information distance (NID) — an LZ76-based distance between two sequences.

Usage

[dependencies]
lzcomplexity-core = "1.0"

use lzcomplexity_core::{lz76, metrics, LzArgs, Sequence};

let args = LzArgs::new(); // auto-detect alphabet / log base

// Complexity + factor boundaries: the i-th factor spans [lzf[i], lzf[i+1]).
let r = lz76::lz76_factors(&Sequence::from_str("banana"), &args);
assert_eq!(r.factorization, 3);
assert_eq!(r.lzf, vec![0, 1, 2, 3, 7]);

// Normalized entropy density.
let h = lz76::lz76_entropy_density(&Sequence::from_str("01010101"), &args);
assert!((h - 0.75).abs() < 1e-12);

// Normalized information distance between two sequences.
let d = metrics::lz76_information_distance(
    &Sequence::from_str("abcd"),
    &Sequence::from_str("abce"),
    &args,
);
assert!((d - 0.25).abs() < 1e-12);

See the API documentation for the full surface.

Notes

Inputs are raw byte sequences (Sequence::from_str / Sequence::from_bytes), so any alphabet works, including non-UTF-8 bytes.
The shuffle-based EMC is seeded deterministically from the input, so results are reproducible run-to-run.

References

Lempel, A., & Ziv, J. (1976). On the complexity of finite sequences. IEEE Transactions on Information Theory, 22(1), 75–81.
Kontoyiannis, I., et al. (1998). Nonparametric entropy estimation for stationary processes and random fields. IEEE TIT, 44(3), 1319–1327.

License