Skip to content

LZ76 factorization

The 1976 definition, the counting convention this library uses, and how the parse is computed.

lzcomplexity computes the Lempel–Ziv 1976 complexity: the number of components in the unique exhaustive history of a sequence, built from self-referential (overlapping) recursive copies. The result is an integer, not a compression ratio and not an estimate. Same bytes in, same integer out.

Two things this page settles, because they cause more confusion than anything else in the library. LZ76 is a complexity measure, not a compression algorithm (§ LZ76 is not LZ77 or LZ78). And this library counts complete components only, which is one fewer than the textbook count whenever the sequence ends mid-component (§ The counting convention).

The definitions

Fix a finite alphabet Σ with |Σ| = α. Let S = s1s2…sn, and write S(i, j) for the subword si…sj (empty when i > j). Indices in this section are 1-based, following the paper; the library's factors array is 0-based.

Reproducibility

S is reproducible from its prefix S(1, j) when the rest of the sequence can be copied out of what has already been written.

S(1, j) → S  ⟺  ∃ p ≤ j : sj+k = sp+k−1   for k = 1, 2, …, n − j

p
the copy pointer — it must start inside the prefix, p ≤ j
k
copy step; the copy may run past position j
n − j
number of symbols still to be written

Lempel & Ziv (1976), § II.

The pointer must lie in the prefix, but the copy may run past position j and read symbols it has itself written. Copying is recursive. 0000000000000000 is reproducible from 0 in one step; 0101010101… is reproducible from 01.

Prose restatements of this definition are usually wrong

Implementing "S(j+1, n) is a subword of S(1, j)" forbids overlap, and so gives a different, larger complexity on every sequence in which some copy has to overrun its own start — 1 647 of 2 000 random binary strings of length 2–60, running the two rules side by side. The correct condition is the ∃ p ≤ j form above: the earlier occurrence only has to start earlier. This library allows overlap — banana factorises as b · a · n · ana, where the final ana is copied from position 2 and overlaps its own destination.

Production

S is producible from S(1, j), written S(1, j) ⇒ S, when S with its last symbol removed is reproducible from S(1, j). In words: copy as before, then you are allowed exactly one free symbol. That free symbol is the innovation, and every production costs exactly one new symbol of information.

History, exhaustive history, and c(S)

A history of S is a factorisation in which each prefix is produced from the previous one.

H(S) = S(1, h1) · S(h1+1, h2) · … · S(hm−1+1, hm),   hm = n

Hi(S)
the i-th component, S(hi−1+1, hi)
condition
S(1, hi−1) ⇒ S(1, hi) for every i
c(S)
the number of components of the exhaustive history

A history is exhaustive when every component is as long as possible — each hi is maximal subject to the production condition. Equivalently, in Constantinescu & Ilie's vocabulary, every component except possibly the last is innovative (it is not a factor of everything that precedes it) rather than merely reproductive. The last component is explicitly exempt, because a sequence need not end on an innovation. That exemption is where every implementation disagreement lives.

Why the measure is canonical, not merely greedy

Every sequence has exactly one exhaustive history, and it is the shortest of all histories: |E(S)| ≤ |H| for any history H of S. So c(S) is a genuine minimum over all admissible parsings, not an artefact of the parser that happened to be used. The minimality statement is Lempel & Ziv's; it appears as Lemma 3 of Constantinescu & Ilie (2007), where uniqueness is noted as immediate from the definition. Citations on References.

A worked decomposition

010011101101100 — the full parse

This is the example from Estevez-Rams et al. (2013), § II. The library reproduces both the published factor boundaries and the published count.

import lzcomplexity as lz

seq = "010011101101100"
c, factors = lz.factorization(seq)

print(c)                                              # 6
print(factors)                                        # [0, 1, 2, 4, 6, 9, 15]
print(" . ".join(seq[a:b] for a, b in zip(factors, factors[1:])))
# 0 . 1 . 00 . 11 . 101 . 101100

Component by component. LPF[i] is the length of the longest factor starting at position i that also starts at some earlier position; each component is that copy plus one innovation symbol. Positions in this table are 0-based.

# span symbols LPF copy copied from innovation
1 [0,1) 0 0 — — 0 (first symbol)
2 [1,2) 1 0 — — 1
3 [2,4) 00 1 0 position 0 0
4 [4,6) 11 1 1 position 1 1
5 [6,9) 101 2 10 position 1 1
6 [9,15) 101100 5 10110 position 6, overlapping 0

The sixth component copies five symbols from position 6, which overlaps its own destination at position 9 — the recursive copy of § Reproducibility, in the one place it matters.

The parse lands exactly on n = 15, so the sixth component is complete and is counted: c = 6, the same value published for this string. The normalised entropy density is lz.h(seq) == 1.5627562382434075 — greater than 1, and correctly so at n = 15. See Entropy density.

Component k spans [factors[k], factors[k+1]). The final entry of factors is either n or n + 1, never anything else, because LPF[i] ≤ n − i bounds the last step's overshoot to a single symbol. Which of the two it is decides the count — see below.

LZ76 is not LZ77 or LZ78

Three papers, three consecutive years, the same two authors, the same journal. They do different things, and the conflation is endemic.

LZ76 — a complexity measure

Output is an integer c(S): the number of components in the unique exhaustive history. No codewords, no bitstream, no decoder. The only operation is the recursive copy, over an unbounded prefix.

lz.factorization(seq)

LZ77 — a compression algorithm

A bounded sliding window; output is a stream of (offset, length, next-symbol) triples with a real encoder and decoder, and a compression ratio in bits per symbol. Ancestor of DEFLATE, gzip, zip, zstd.

LZ78 — a different compression algorithm

An incrementally built dictionary; each phrase is an existing entry plus one new symbol; output is (index, symbol) pairs. Ancestor of LZW, and so of GIF and compress.

"LZ-factorization" — a fourth thing

In the suffix-array literature this names the greedy parse with step max(LPF[i], 1) — no innovation symbol. It differs from LZ76 at every position where LPF > 0.

LZ76 (this library) LZ77 (1977) LZ78 (1978) Stringology "LZ-factorization"
Output integer c(S) bitstream bitstream factor list
Window unbounded bounded, sliding dictionary unbounded
Factor rule longest recursive copy + 1 innovation symbol longest match in window + next symbol dictionary entry + 1 symbol longest recursive copy, no +1
Self-referential yes yes no yes
Purpose complexity, entropy rate compression compression indexing, repetition analysis

LZ76 is the theoretical parent: the recursive-copy parsing it defines is the mechanism LZ77 turns into a codec, and LZ78's incremental parsing is a dictionary-restricted cousin. The three parsings give different numbers on the same string. They agree only in the asymptotic sense that, after the appropriate scaling, each converges to the entropy rate of an ergodic source.

A gzip ratio is not Lempel–Ziv complexity

Reporting a compressed file size as "Lempel–Ziv complexity" measures a bounded-window codec with an entropy coder attached — not c(S). The two are different quantities with different finite-size behaviour, and a result derived from one does not transfer to the other. Estevez-Rams et al. make this point explicitly about entropy-rate estimation from encoded lengths.

The name is overloaded even inside stringology: Constantinescu & Ilie use "Lempel–Ziv factorization" for the exhaustive history (the +1 variant) and reserve "maximal reproductive history / Crochemore factorization" for the max(LPF, 1) variant. So "LZ factorization" alone identifies nothing — always state whether the innovation symbol is included. This library includes it.

The bound, εn, and the normalisation

Lempel & Ziv prove a universal upper bound on the number of components.

c(S) < n ⁄ [ (1 − εn) · logα n ] ,    εn = 2 · (1 + logα logα(αn)) ⁄ logα n

n
sequence length in symbols
α
alphabet size (auto-detected here, floored at 2)
εn
the bound's slack term; → 0 as n → ∞

Lempel & Ziv (1976); reproduced as eqs. (1)–(2) of Estevez-Rams et al. (2013).

The code generalises the formula slightly: the base of every logarithm above is log_base, and α inside logα(αn) is the alphabet size. They coincide by default, which is the case written above; pass log_base explicitly and the two decouple.

Since εn → 0, this yields the familiar asymptotic form c(S) < n / logα n, and it motivates the normalisation the library actually computes.

h = c(S) ⁄ ( n ⁄ logk n ) = c(S) · logk n ⁄ n

k
log_base; defaults to the auto-detected alphabet size, minimum 2
h
returned by lz.h(seq), and the h key of lz.lz76(seq)

The n / log n normaliser is the one Kaspar & Schuster (1987) fixed; the α-ary form is eq. (4) of Aboy et al. (2006).

Note the plain n / logk n: no (1 − ε) correction enters the computation anywhere. Leaving it out is universal practice. Full treatment on Entropy density.

ε stays large at every length you will ever run

The bound is meaningful only while εn < 1. As ε → 1 the right-hand side diverges; above 1 it goes negative and the bound says nothing. Computed from the library's own formula:

361smallest binary n with ε < 1
9 882same, 26-symbol alphabet
0.48ε at n = 10⁷, binary
n (binary) 10 10² 10³ 10⁴ 10⁵ 10⁶ 10⁷
εn 1.873 1.184 0.894 0.728 0.619 0.541 0.482

So ε exceeds 1 — and the bound is vacuous — for every binary sequence shorter than 361 symbols, and for every 26-symbol sequence shorter than 9 882. Above those lengths the decay is glacial: for a binary alphabet ε does not reach 0.1 until n ≈ 4 × 10⁵⁰. The clean c < n / log n regime is unreachable for any real dataset.

epsilon looks absurd on short sequences, and that is correct

lz.lz76("010011101101100")["epsilon"] is 1.686665661451639 — greater than 1, which makes the bound it belongs to vacuous at that length. epsilon is the slack term of the LZ76 upper bound, not a correction that has been applied to anything: nothing in the library divides by (1 − ε), and the value is reported and never consumed. It is forced to 0.0 for a constant sequence, as a sentinel rather than a computed quantity.

Kaspar & Schuster, and the "LZc" of neuroscience

Kaspar & Schuster (1987) took LZ76 out of information theory and into physics, and fixed the normaliser b(n) = n / log2 n for binary sequences — generalised in the biomedical literature to n / logα n. With log_base=2 on a binary sequence, this library's h is literally the Kaspar–Schuster normalised complexity.

LZc in the neuroscience literature is LZ76 applied to a binarised EEG or MEG signal: symbolise, factorise, normalise. There are two normalisation schools and they are not interchangeable.

Scheme Normaliser Consequence
Casali et al. (2013), PCI the asymptotic value for a random sequence of the same length and the same average activation rate p, i.e. H(p)·L/log2L — not the bare L/log2L the H(p) factor makes the index depend on pattern formation rather than on how much activity there is
Schartner et al. (2015) the LZ76 complexity of the same binary input, randomly shuffled values land on a 0–1 scale, and the finite-n and alphabet-size biases largely cancel, because the surrogate has the same n and the same symbol histogram

The binarisation step changes the result more than anything downstream of it, and there is no canonical choice: Schartner et al. threshold at the mean of the Hilbert amplitude, while Aboy et al. report the median as prevailing practice, being less sensitive to outliers. Whichever you use, report it.

There is no one-call surrogate normaliser here

lzcomplexity ships the raw c(S), the n/logkn normalisation (lz.h), and a deterministic block shuffle used by the EMC estimator. It does not ship a "divide by shuffled surrogate" helper. Build the Schartner-style normalisation from lz.factorization plus your own shuffle — see EEG and neural time-series.

The counting convention

A published c(S) will often be exactly one larger than what this library returns

lz.factorization("banana") returns 3; textbooks, antropy, NeuroKit2 and the EEG toolboxes that reimplement the same Kaspar–Schuster loop return 4 for the same string. The factor boundaries agree exactly. Only the count differs, and only ever by one.

The library counts complete components only. When the trailing component is purely reproductive — when its innovation symbol would fall past the end of the sequence — it is still parsed and still returned in factors, but it is not counted.

Operationally the test is the final boundary: equal to n → counted; equal to n + 1 → dropped. The exact conversion:

c, factors = lz.factorization(seq)
c_textbook = c + (1 if factors[-1] > len(seq) else 0)
Sequence Parse (identical under both conventions) This library Textbook c(S)
010011101101100 0 · 1 · 00 · 11 · 101 · 101100 6 6
1001111011000010 1 · 0 · 01 · 1110 · 1100 · 0010 6 6
banana b · a · n · ana 3 4
ABRACADABRA A · B · R · AC · AD · ABRA 5 6
1011010100010 1 · 0 · 11 · 010 · 100 · 010 5 6
0001101001000101101110100 0 · 001 · 10 · 100 · 1000 · 1011 · 0111 · 0100 7 8
01010101010101010101 0 · 1 · 010101010101010101 2 3

How this was checked

Against a naive reference implementation of the exhaustive history, over 4 000 random strings (alphabets 01, 012, ACGT, ab; lengths 1–120), of which 3 943 contained at least two distinct symbols:

  • boundary vectors: 0 mismatches. The parse is the LZ76 exhaustive history.
  • count difference naive − library: 0 in all 826 exact-landing cases, +1 in all 3 117 overshoot cases. No other value occurred, and the conversion above held on every string.

The rule was checked exhaustively over all 524 284 binary strings of length 2–18 as well. On the 524 250 of them with at least two distinct symbols: boundary vectors identical, Δ ∈ {0, 1}, and Δ = 1 if and only if the final walk boundary exceeds n, with zero counter-examples. Δ = 0 in 18.8 % of them. The remaining 34 are the constant strings, which bypass the parser — the exception documented below.

This behaviour is inherited verbatim from the C++ implementation and is not a Rust regression — see Rust vs C++.

The difference is at most 1, so it is asymptotically irrelevant for sequences whose complexity grows: a random binary sequence at n = 10⁴ has c = 769, where 1 is 0.13 % of the count and invisible in h. On a highly repetitive sequence it is not negligible at any length — 01 repeated 5 000 times has c = 2. And it is highly visible on the short toy strings that appear in tutorials, where it will break an exact regression test against antropy or NeuroKit2.

Constant sequences bypass the parser, and the conversion formula does not apply

lz.factorization("0000000000") returns (1, [0, 1, 10]). The final boundary is n, not n + 1, so c + (1 if factors[-1] > len(seq) else 0) yields 1 — but the exhaustive history of 0000000000 is 0 · 000000000, so the textbook count is 2. Sequences with fewer than two distinct bytes skip the factorizer entirely and receive a synthetic boundary vector. Guard with len(set(seq)) < 2 before converting.

The empty sequence takes the same branch and returns (1, [0, 1, 0]) — a complexity of 1 and a descending boundary vector. Do not pass an empty sequence.

Consuming factors safely

Two traps follow from the convention.

  • len(factors) - 1 is the number of parsed components, which is not the reported complexity whenever the parse overshoots.
  • factors[-1] may be n + 1. Python slicing clamps, so seq[factors[-2]:factors[-1]] happens to work; the same indices panic in Rust and read out of bounds in C. Clamp with min(b, len(seq)).
seq = "banana"
c, factors = lz.factorization(seq)

print(c, factors)  # 3 [0, 1, 2, 3, 7]
print([seq[a:min(b, len(seq))] for a, b in zip(factors, factors[1:])])
# ['b', 'a', 'n', 'ana']

How the parse is computed

Four phases per call, over the raw bytes.

Phase Produces Algorithm Cost
1. Suffix array SA[0..n) cdivsufsort at n ≥ 2048; a plain comparison suffix sort below it O(n log n) worst case, near-linear in practice; the comparison sort is O(n² log n) worst case, capped at 2 047 bytes
2. LCP array LCP[i] = lcp(SA[i−1], SA[i]), LCP[0] = 0 Kasai et al. (2001) Θ(n)
3. LPF array LPF[i], the longest factor at i that also starts at some j < i Crochemore & Ilie (2008), stack form Θ(n)
4. The walk factors i += LPF[i] + 1 Θ(c(S))

The suffix array of a string is unique, so the 2048-byte cutoff between the two construction routines is a pure constant-factor optimisation and can never change a published number. An in-tree differential fuzz test asserts the two routines agree across the cutoff.

LPF is where the self-reference lives. LPF[i] requires only that the earlier occurrence start before i; it may overlap and run past i. That is what lets ana be copied from index 1 of banana (0-based) into index 3, and it is what makes the parse genuinely LZ76 rather than a non-self-referential imitation.

The walk, and why the step is + 1

let mut i: usize = 1;          // factors starts out as [0, 1]
while i < n {
    i += lpf[i] + 1;
    factors.push(i);
}

Condensed from crates/lzcomplexity-core/src/lz76.rs, which reads the previous boundary back out of factors instead of keeping it in i. Same recursion: p0 = 0, p1 = 1, pk+1 = pk + LPF[pk] + 1.

The copy part of an exhaustive component has length exactly LPF[i] — by definition, the longest prefix of S[i..] that already occurred. Appending one more symbol makes the component not reproducible from the past. That is the innovation, and it is what makes the production exhaustive. The step is LPF[i] + 1, never LPF[i].

The max(LPF[i], 1) step of the stringology LZ-factorization produces a different, generally larger factor count on the same string. If you are porting code from that literature, this single + 1 is the entire difference.

Where the time actually goes

Index construction is essentially all of the cost: suffix sorting plus LCP is 83 % of the runtime at n = 10⁵, rising to about 89 % at n = 10⁷, while the LZ76 walk itself is under 0.5 %. Replacing the quadratic Kaspar–Schuster loop with this pipeline buys a factor that grows with n. Measured numbers, and the caveats on them, are on Performance.

One wording correction, because the in-tree source comments get it wrong: only phases 2–4 are linear. libdivsufsort is O(n log n) worst case in 5n + O(1) bytes, per its own documentation — fast and near-linear in practice, but not a linear-time algorithm. The end-to-end bound is O(n log n).