Skip to content

Lempel–Ziv 76 · Rust core · v1.0

Measure the structure
in the noise.

lzcomplexity factorises any symbolic sequence with Lempel–Ziv 76 and returns complexity, entropy rate, effective measure complexity and information distance. A Rust core, a Python API of five functions, and two command-line tools — linear-time and reproducible run to run.

Get started API reference GitHub

$pip install lzcomplexity
LZ76 factorization of a 72-symbol binary sequence A sequence that begins perfectly periodic and ends random. LZ76 cuts it into 10 factors: long factors of 20 and 18 symbols on the ordered left side, then progressively shorter factors of 8, 3, 5, 9 and 5 symbols as the sequence becomes random. Complexity c(S) = 10, entropy density h = 0.857. ordered random 0 1 01010101010101010100 11 001100110011001101 10100111 000 10111 010011101 10010 1 2 3 · 20 symbols 4 5 · 18 symbols 6 · 8 7 8 9 10 n = 0 24 48 72
c(S) 10 LZ76 factors
h 0.857 entropy density
n 72 symbols, alphabet 2

Four measures, one factorization

Complexity

The number of LZ76 factors — how many distinct "new" pieces it takes to build the sequence from its own past. Computed from a suffix array and a longest-previous-factor table, so the answer is an exact integer, not a sample.

lz.factorization(seq)

Entropy rate

A non-parametric estimator of the source's entropy rate. No model, no bin count, no window — the factor count and the length are enough. Converges for stationary ergodic sources.

lz.h(seq)

Effective measure complexity

Structure that is neither periodic nor random. Compares the sequence against block-shuffled versions of itself at a ladder of scales, and reports the excess over the entropy rate.

lz.emc(seq)

Information distance

How much of one sequence you still need after you already have the other. A compression-based distance in the normalized-information-distance family — no alignment, no feature engineering.

lz.nid(a, b)

h ≈ c(S) · logk n ⁄ n

c(S)
number of LZ76 factors
n
sequence length, in bytes
k
alphabet size, auto-detected, minimum 2

Converges to the entropy rate of a stationary ergodic source — Ziv & Lempel (1978), Kontoyiannis et al. (1998).

Thirty seconds

import lzcomplexity as lz

lz.factorization("banana")
# (3, [0, 1, 2, 3, 7])          complexity, then factor boundaries

lz.h("01010101")
# 0.75                           normalised entropy density

lz.nid("ABRACADABRA", "ABRACADABRZ")
# 0.3333333333333333             one symbol apart, so most information is shared

lz.lz76("ABRACADABRA")["emc"]["value"]
# 0.5417804008745377             effective measure complexity

Every function takes str, bytes, list[str], list[int], or any iterable of ints. Read Input types before you feed it numeric data — the conversion rule surprises people.

5Python functions
O(n)factorization
12 MB/sincompressible data
2CLI tools
7input formats
MITlicence

Measured scaling is t ∝ n^1.01 on random binary input, from 10³ to 10⁶ symbols. See Performance for the full table and the methodology.

Where to go next

I have data and want a number

Start at Install, then Your first factorization. Read Reading the numbers before you interpret anything.

I want to know what it computes

LZ76 factorization defines the measure, Entropy density and EMC build on it, and Sequence length and convergence tells you when to trust the result.

I work with EEG, DNA, or time-series

The recipes are written for you: EEG and neural time-series, DNA and FASTA, the route to chaos, and comparing many sequences.

I want the reference

Python API, the Rust crate, and the two command-line tools lzcomplexity and lzdistance.