Your first factorization¶
From a six-letter word to four factors, three counted, and the numbers that follow.
lz.factorization is the one call that shows you the whole machine. Everything else in the
library — the entropy density, the distance, the effective measure complexity — is derived
from the parse it returns. This page runs it on "banana" and takes the result apart
completely.
If import lzcomplexity fails, start at Install.
Run it¶
Two things come back: an integer complexity, and a list of integers that is not a list of substrings.
The gap between the last two tiles is the whole story of this page. Take the boundary vector first, then the count.
The boundary vector¶
factors holds half-open boundary indices. factors[0] is always 0; every later entry
is the exclusive end of one piece of the parse. So the pieces are the consecutive pairs, and
this is the exact expression that reconstructs them:
>>> seq = "banana"
>>> complexity, factors = lz.factorization(seq)
>>> [seq[start:end] for start, end in zip(factors, factors[1:])]
['b', 'a', 'n', 'ana']
Four pieces, from five boundaries. In general len(factors) - 1 is the number of pieces the
parser emitted — which, as the next section shows, is not the number it reports.
Warning
The last boundary can point one symbol past the end of the sequence, and for "banana" it
does: factors[-1] is 7 while len(seq) is 6. Python slicing clamps silently, so
seq[3:7] returns 'ana' and the comprehension above still works. Rust's &seq[3..7]
panics and C reads out of bounds. In any language that does not clamp, write
end = min(end, len(seq)).
The final boundary is always exactly n or n + 1 — never anything else. That is a
consequence of the parse rule, not a range check.
The b | a | n | ana decomposition¶
LZ76 walks left to right. At each position it takes the longest prefix of what remains that has already started somewhere earlier in the sequence, plus one more symbol. That extra symbol is the innovation: it is what makes the new piece impossible to copy from the past, and it is what forces the parse forward.
|fk| = LPF[pk] + 1
- pk
- start position of the k-th component
- LPF[p]
- longest prefix of S[p:] that also starts at some j < p
- + 1
- the innovation symbol
Lempel & Ziv (1976), the exhaustive history. The copy may overlap the region it is being written into — it only has to start earlier.
For "banana":
| # | span | piece | where it comes from |
|---|---|---|---|
| 1 | [0,1) |
b |
first symbol, pure innovation |
| 2 | [1,2) |
a |
nothing earlier starts with a, so LPF = 0, plus 1 innovation |
| 3 | [2,3) |
n |
LPF = 0, plus 1 innovation |
| 4 | [3,7) |
ana |
LPF = 3: ana already starts at index 1. The innovation symbol would be index 6 — past the end. |
Piece 4 is the interesting one, and it is where the overlap matters. S[3:6] is ana, and
the earlier occurrence starts at index 1 — but that occurrence is S[1:4], which runs into
the region being copied. LZ76 allows this; a non-overlapping matcher would find only an,
ending the component at index 6 instead of 7 — the same four visible pieces, but a complete
final component and therefore a count of 4. See How LZ76 works for why
the overlap is part of the definition rather than an optimisation.
Only complete components are counted¶
Four pieces are visible. The reported complexity is 3.
Warning
Compare lz.factorization("banana")[0] against a textbook and you are off by one: this
library says 3, Kaspar–Schuster-style implementations (antropy.lziv_complexity, most
MATLAB EEG toolboxes) say 4. Neither is a bug. The library counts only components whose
innovation symbol actually lands inside the sequence. ana's would have been index 6, past
the end, so that component is complete as a copy but not as a production, and is not
counted.
The test is exactly the final boundary. Landing on n means the last component is complete;
landing on n + 1 means it was truncated. So the conversion is one line:
>>> seq = "banana"
>>> complexity, factors = lz.factorization(seq)
>>> c_textbook = complexity + (1 if factors[-1] > len(seq) else 0)
>>> c_textbook
4
Checked against a reference Kaspar–Schuster counter on 500 random non-constant strings
(lengths 2–120, alphabets 01, 012, ACGT, ab): 500 / 500 agreement, and no other
correction was ever needed.
The parse itself does not need correcting. Clamp the final boundary to n and the pieces
are the LZ76 exhaustive history, symbol for symbol. Only the count differs, and only when the
sequence ends mid-component:
| sequence | parse | library c |
textbook c |
|---|---|---|---|
010011101101100 |
0 · 1 · 00 · 11 · 101 · 101100 |
6 | 6 |
banana |
b · a · n · ana |
3 | 4 |
ABRACADABRA |
A · B · R · AC · AD · ABRA |
5 | 6 |
01010101010101010101 |
0 · 1 · 010101010101010101 |
2 | 3 |
The first row is the worked example in Estevez-Rams et al. (2013) §II, reproduced exactly — boundaries and count, because that sequence happens to end on a component boundary. The other three overshoot, and there the counts diverge by one.
Note
Constant sequences skip the parser entirely, and the conversion above does not apply to
them. lz.factorization("aaaa") returns (1, [0, 1, 4]) from a special-case path — the
boundary vector is synthetic and ends at n, so the formula says 1 while a textbook
counter says 2. The same shortcut makes lz.factorization("") return (1, [0, 1, 0]):
a complexity of 1 and a decreasing boundary list, for an empty input. Guard empty input
yourself.
The difference is at most 1, always in the same direction. It shifts h by exactly
log_k(n) / n — about 0.0013 at n = 10⁴, k = 2 — so it is negligible at research lengths
and glaring on tutorial-length strings, which is exactly where readers compare numbers against
a paper.
Three more numbers from the same string¶
h — entropy density¶
h is the complexity normalised by the LZ76 asymptote, n / log_k n:
h = c(S) · logk n ⁄ n
- c(S)
- complexity as reported above — 3 for
banana - n
- sequence length in bytes — 6
- k
- log base; defaults to the auto-detected alphabet size, floored at 2
"banana" has three distinct bytes, so the default units are base-3 symbols per symbol, not
bits. Ask for bits explicitly:
That value is above 1, which is expected: h is a finite-n estimator with a large upward
bias at short lengths and it is not bounded by 1. Six symbols is far too short to read as an
entropy rate at all. See Entropy density for the estimator,
Alphabets and log bases for why auto-detection is a hazard in
comparative studies, and Convergence for how long a sequence has
to be before the number means anything.
nid — normalised information distance¶
nid measures how much one sequence fails to explain the other, by counting how many new
components appear when you concatenate them. Here c("banana") = 3, c("bandana") = 5,
c("bananabandana") = 5 and c("bandanabanana") = 6, so the value is
max(5 - 3, 6 - 5) / max(3, 5) = 2 / 5. Unrelated strings go to 1:
Warning
nid(x, x) is not always 0, so nid is not a metric on finite sequences.
lz.nid("banana", "banana") returns 0.3333333333333333, because appending banana to
itself still costs one new component. It reaches 0 only when a sequence is fully
reproducible from its own copy — lz.nid("abc", "abc") is 0.0. Details in
Information distance.
emc — effective measure complexity¶
That zero is not a result, it is a degenerate case: for n < 10 the automatic selector picks a
single block scale, and the block-size-1 shuffle of "banana" factorises into 3 components —
the same as the original — so the single term is exactly zero. Give it something longer:
emc returns (value, summands). Each summand belongs to one block scale, every summand is
non-negative, and the value is their sum.
Note
The summands are not raw per-scale measurements. Each block scale l gives a rung
Ê(l) = l · g · (C_LZ(shuffled at l) − C_LZ(original)), where g = log_k(n)/n — an estimate of
the excess entropy accumulated up to scale l. Because excess entropy is a mutual information
between past and future, the true ladder rises and never dips below zero, while the raw rungs do
both. emc projects the ladder onto that shape first, then reports the increments; the 0.0
above is a scale that the projection pooled with its neighbour, not a scale that was skipped.
The running sum of summands is often the more useful curve: it is the excess entropy
captured up to each scale, and where it flattens is where the sequence runs out of structure.
0.0 is a real reading; a small positive number often is not
A structureless sequence returns exactly zero, because its whole ladder sits at or below zero and the projection flattens it:
>>> import random
>>> r = random.Random(0)
>>> noise = "".join(r.choice("01") for _ in range(2000))
>>> lz.emc(noise)[0]
0.0
The trap is the other direction. Because the value cannot go negative, the noise on a
structureless input piles up above zero, so at n = 2 000 a value of a few tenths is still
consistent with no structure at all. Build a null before you read a small number as signal —
Effective measure complexity tabulates the floor by length.
Two other cautions carry over. emc scales with the largest block size, which is derived from
len(seq), so never compare values across lengths: the same period-2 structure gives
1.1345061249079327 at n = 400 (lz.emc("0101" * 100)[0]) and 2.664115272425268 at
n = 800 (lz.emc("01" * 400)[0]). And it overshoots the true excess entropy by 2–3× on
sources where that quantity is known, so report it as an ordinal index, never as a bit count.
Read Effective measure complexity before reporting any of this.
What to read next¶
Reading the numbers¶
Which of the four numbers to report, what each one is sensitive to, and which comparisons are invalid.
guide/reading-the-numbers
How LZ76 works¶
The exhaustive history, why it is unique and minimal, and how it differs from LZ77, LZ78 and the stringology "LZ-factorization".
concepts/lz76
Python API¶
All five functions and every parameter, including the two that are accepted and ignored.
lz.factorization · lz.h · lz.nid · lz.emc · lz.lz76
What counts as a sequence¶
str is analysed as UTF-8 bytes, bytearray is not treated as bytes, and list[int] is
concatenated as decimal text. Read this before passing anything but ASCII.
api/inputs