Rust crate¶

lzcomplexity-core is the algorithm crate. The Python package and both CLI tools are skins over it.

Everything the Python API returns is computed by lzcomplexity-core. Depending on it directly removes the PyO3 layer and hands you the result structs — including fields the Python dict never surfaces.

[dependencies]
lzcomplexity-core = "1.0"

Or cargo add lzcomplexity-core. Only this crate is published to crates.io; lzcomplexity-py ships inside the wheel and lzcomplexity-cli ships as GitHub release binaries.

1.75MSRV

2021edition

0cargo features

4direct dependencies

MITlicence


Crate name	`lzcomplexity-core`
Library name (what you `use`)	`lzcomplexity_core`
Crate type	rlib
Direct dependencies	`rayon 1.10`, `rand 0.8`, `rand_chacha 0.3`, `cdivsufsort 2.0`
Generated API docs	docs.rs/lzcomplexity-core
Registry	crates.io/crates/lzcomplexity-core

Cargo features¶

There are none. The manifest has no [features] table, so there is no way to opt out of any dependency — in particular rayon is unconditional and there is no serial-only build. To run single-threaded, size the thread pool instead (Threads).

A source build fails without a C compiler, not only a Rust toolchain

cargo build stops with a cc error on a machine that has rustc but no C compiler. cdivsufsort is a Rust binding that compiles Yuta Mori's vendored C libdivsufsort sources through a cc build dependency. On Windows that means the MSVC build tools. The repository README's "no C++ toolchain" line is true as written — but a C toolchain is required.

The MSRV is declared, not tested

rust-version = "1.75" is recorded in the workspace manifest and on crates.io for every published version. CI builds with dtolnay/rust-toolchain@stable only — there is no 1.75 job, so an accidental MSRV bump would not be caught. Treat 1.75 as a claim, not as a guarantee backed by a build.

Module map¶

Six public modules. The pipeline: sequence holds the bytes, suffix_array and lpf build the index, lz76 walks it, and shuffle and metrics build the derived measures on top. The table is ordered by how often you will reach for each one, not by pipeline order.

Module	Contains	Reach for it when you want
`sequence`	`Sequence`, `shuffle_in_place`, `shuffle_copy`, `shuffle_copy_seeded`	to construct input, or to slice / shift / concatenate bytes
`lz76`	`factorize`, `lz76_factorization`, `lz76_factors`, `lz76_entropy_density`, `entropy_density_from`, and every result struct	complexity, factor boundaries, entropy density
`lpf`	`lpf` — the Crochemore–Ilie longest-previous-factor pass	nothing, unless you are reimplementing the parse
`suffix_array`	`build`, `build_suffix_array`, `build_lcp`, `SuffixArray`	a suffix array or LCP array for your own purposes
`shuffle`	`lz76_random_shuffle_complexity`, `shuffle_factorization`, `max_block_size`, `merge_sequences`	EMC and the block-shuffle ladder
`metrics`	`lz76_information_distance`, `lz76`, `lz76_extras`, `mutual_information`, and the `_z` variants	NID, the full `LempelZiv` bundle, the extras

The crate root re-exports the types you need most, but not the functions:

pub use lz76::{LempelZiv, Lz76Result, LzArgs, LzExtra, LzShuffle};
pub use sequence::Sequence;
pub use suffix_array::{build_suffix_array, SuffixArray};

pub const NO_ALPHABET: u32 = u32::MAX;
pub const ALPHABET_SIZE: u32 = 2;

So LzArgs and Sequence come from the crate root, while lz76_entropy_density and lz76_information_distance have to be reached through lz76:: and metrics::.

Building a `Sequence`¶

Sequence is a byte vector plus a cached alphabet. Three constructors matter:

use lzcomplexity_core::Sequence;

let a = Sequence::from_str("banana");                          // &str, bytes copied
let b = Sequence::from_bytes(vec![0u8, 1, 0, 1, 1, 0, 0, 1]);  // raw bytes, any values
let c = Sequence::from_bytes_with_alphabet(vec![0, 1, 2], 3);  // bytes + a proposed alphabet size

All three run determine_alphabet(), which scans the bytes, counts distinct values and floors the result at 2. A constant string therefore reports alphabet_size() == 2, not 1.

assert_eq!(Sequence::from_str("aaaa").alphabet_size(), 2);
assert_eq!(Sequence::from_bytes(vec![0, 1, 0, 1, 1, 0, 0, 1]).alphabet_size(), 2);

from_bytes_with_alphabet proposes an alphabet size; the scan overrules it

determine_alphabet() keeps the value you passed only when it already equals the distinct-byte count, and otherwise replaces it with max(2, distinct). So from_bytes_with_alphabet(vec![0, 1], 10).alphabet_size() is 2, not 10. To override the alphabet for a measurement, set LzArgs::alphabet — that value is not re-derived — or call set_alphabet_size after construction.

from_str is an inherent method, not the FromStr trait — it is infallible, so there is no Result to unwrap and no .parse() form.

A non-ASCII &str becomes more symbols than it has characters

Sequence::from_str("héllo") has len() == 6 and alphabet_size() == 5, because é is two UTF-8 bytes and each byte is a separate symbol. Every measure in this crate operates on bytes. If your alphabet has more than 256 members, or you want one symbol per Unicode scalar, map it to bytes yourself before constructing the Sequence. See Alphabets and log bases.

Beyond the constructors: as_bytes, len, take(l), drop(l), split_at(l), reverse_copy, right_shift / left_shift, granularity(gr), char_density, map(f), xor_with, and &a + &b for concatenation.

`LzArgs` — every field¶

Every measure entry point takes &LzArgs — the lz76* functions in lz76, shuffle and metrics. LzArgs::new() and LzArgs::default() are the same thing and are what you want unless you are deliberately overriding the alphabet, the log base or the EMC block-size ceiling.

LzArgs { chunks, max_context, block_size, get_shuffle_terms, alphabet, log_base } stable

Configuration for every lz76* entry point. Derives Clone and Debug; the hand-written PartialEq compares five of the six fields — log_base is not part of the equality.

chunks: i32, default 0 — inert. Never read by any algorithm in the workspace.
max_context: i32, default 0 — inert. Never read anywhere.
block_size: i32, default -1 — the EMC block-size ceiling mm. Any value <= 0 means auto-select. Read by shuffle::shuffle_factorization only.
get_shuffle_terms: bool, default false — populate LzShuffle::summands with the per-scale terms. Off by default in Rust; the Python emc() and lz76() bindings hard-code it to true.
alphabet: u32, default NO_ALPHABET — the effective alphabet size. Feeds epsilon and nothing else. Clamped to a floor of 2.
log_base: u32, default NO_ALPHABET — the logarithm base for entropy density and epsilon. Clamped to a floor of 2; pass 2 for bits.

The `NO_ALPHABET` sentinel¶

alphabet and log_base are u32, so there is no Option to hold "unset". The crate uses a sentinel instead:

pub const NO_ALPHABET: u32 = u32::MAX;   // 4294967295

A field equal to NO_ALPHABET means "take it from the sequence" — factorize substitutes seq.alphabet_size(). Any other value overrides the auto-detection, and is then clamped upward to 2, so 0 and 1 are silently equivalent to 2.

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

let seq = Sequence::from_str("banana");

let auto = LzArgs::new();                     // alphabet = log_base = NO_ALPHABET -> 3
assert_eq!(lz76::lz76_entropy_density(&seq, &auto), 0.8154648767857287);

let mut bits = LzArgs::new();
bits.log_base = 2;                            // report h in bits instead
assert_eq!(lz76::lz76_entropy_density(&seq, &bits), 1.292481250360578);

Two of the six fields do nothing, and do it silently

Setting chunks or max_context changes no returned value. Neither field is read by any code path in the workspace. chunks is what the CLI's --partitions flag and the Python partitions= argument write to, so a caller who "tunes" it gets identical numbers and identical timings. They exist because the struct mirrors the C++ LZ_Args; treat them as reserved.

alphabet moves epsilon only

Inside factorize, alphabet and log_base feed only the epsilon expression. The factor count, the boundary vector and factors_stddev depend on neither. log_base re-enters downstream in entropy_density_from, which applies its own independent floor-of-2 clamp; alphabet does not re-enter at all.

Worked examples¶

One program, four entry points. These are the same values the Python API returns for the same inputs — the binding does not round, rescale or reorder anything.

src/main.rs

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

fn main() {
    let args = LzArgs::new();

    // 1 — complexity and factor boundaries
    let r = lz76::lz76_factors(&Sequence::from_str("banana"), &args);
    println!("c = {}  factors = {:?}", r.factorization, r.lzf);

    // 2 — normalised entropy density
    let h = lz76::lz76_entropy_density(&Sequence::from_str("01010101"), &args);
    println!("h = {h}");

    // 3 — normalised information distance
    let d = metrics::lz76_information_distance(
        &Sequence::from_str("abcd"),
        &Sequence::from_str("abce"),
        &args,
    );
    println!("nid = {d}");

    // 4 — effective measure complexity (ask for the per-scale terms)
    let mut emc_args = LzArgs::new();
    emc_args.get_shuffle_terms = true;
    let s = shuffle::lz76_random_shuffle_complexity(
        &Sequence::from_str(&"01".repeat(64)),
        &emc_args,
    );
    println!("emc = {}  mm = {}", s.emc_value, s.max_block_size);
    println!("summands = {:?}", s.summands);
}

$ cargo run --release
c = 3  factors = [0, 1, 2, 3, 7]
h = 0.75
nid = 0.25
emc = 2.4609375  mm = 15
summands = [0.51953125, 0.0, 0.13671875, 0.0, 0.1640625, 0.0, 0.13671875, 0.0,
            0.02734375, 0.0, 0.478515625, 0.0, 0.0, 0.0, 0.998046875]

The same four calls from Python:

Rust	Python	Value
`lz76::lz76_factors(&s, &args)` → `.factorization`, `.lzf`	`lz.factorization("banana")`	`(3, [0, 1, 2, 3, 7])`
`lz76::lz76_entropy_density(&s, &args)`	`lz.h("01010101")`	`0.75`
`metrics::lz76_information_distance(&a, &b, &args)`	`lz.nid("abcd", "abce")`	`0.25`
`shuffle::lz76_random_shuffle_complexity(&s, &args)`	`lz.emc("01" * 64)`	`2.4609375` and 15 summands
`metrics::lz76(&s, &args)`	`lz.lz76(seq)`	the full bundle

Set get_shuffle_terms if you want the summands — Rust leaves it off

LzArgs::new() leaves get_shuffle_terms = false, so LzShuffle::summands comes back empty and summands.len() == 0. The Python emc() and lz76() bindings force it to true, which is why len(summands) == max_block_size always holds from Python and not from Rust. emc_value is identical either way — 2.4609375 for "01" * 64 with the flag on and with it off — so the flag costs nothing but the allocation.

Cheaper variants when you already have the count¶

Three functions take a pre-computed complexity so you do not pay for a second factorization:

Function	Signature	Saves
`lz76::entropy_density_from`	`(count: u32, &Sequence, &LzArgs) -> f64`	one `factorize`
`shuffle::lz76_random_shuffle_complexity_with`	`(&Sequence, &LzArgs, complexity: i32) -> LzShuffle`	one `factorize`
`metrics::lz76_extras_with`	`(&Sequence, &LzArgs, c_lz: f64) -> LzExtra`	one `factorize`

metrics::lz76 uses all three internally: it factorizes the sequence once and threads the count through the entropy, EMC and extras stages.

Result structs¶

`Lz76Result` — from `lz76_factors`¶

Field	Type	Meaning
`factorization`	`u32`	the complexity `c(S)` — complete LZ76 components only
`epsilon`	`f64`	the Lempel–Ziv finite-size correction term
`lzf`	`Vec<u32>`	half-open factor boundaries; factor k is `S[lzf[k-1] .. min(lzf[k], n)]`

`LzShuffle` — from `lz76_random_shuffle_complexity`¶

Field	Type	Meaning
`max_block_size`	`i32`	the block-size ceiling mm actually used
`emc_value`	`f64`	the effective measure complexity — the top of the projected ladder, always `>= 0.0`
`multi_information`	`f64`	the raw, unprojected `l = 1` rung `H_1 − ĥ`, kept separately. May be slightly negative
`summands`	`Vec<f64>`	the mm per-scale terms, all `>= 0.0`, summing to `emc_value` — empty unless `get_shuffle_terms` is set

`LzExtra` — from `lz76_extras`¶

Five ratios computed by splitting one sequence at len() / 2 and comparing the two halves. They are not a comparison of two inputs.

Field	Type	Formula
`lz_rajski_distance`	`f64`	`2 − (fh + lh) / c`
`redundancy`	`f64`	`mi / (fh + lh)`
`fh_uncertainty`	`f64`	`mi / fh`
`lh_uncertainty`	`f64`	`mi / lh`
`lz_pearson_coefficient`	`f64`	`mi / sqrt(fh · lh)`

fh and lh are the complexities of the first and second half, and mi = fh + lh − c. For odd lengths mid = len() / 2 rounds down, so the second half is one symbol longer.

`LempelZiv` — from `metrics::lz76`¶

Field	Type	Notes
`complexity`	`u32`
`entropy_density`	`f64`	`0.0` for `len() <= 1`
`random_shuffle_complexity`	`LzShuffle`	the EMC bundle
`paired_shuffle_complexity`	`LzShuffle`	always `Default::default()` — hard-wired, never populated
`lz_normal_errors`	`f64`	`sqrt(h³) · factors_stddev / sqrt(n / log_b n)`
`lz_poison_errors`	`f64`	`h / n`
`epsilon`	`f64`
`factors_stddev`	`f64`	see below
`factors`	`Vec<u32>`	the boundary vector
`extras`	`LzExtra`

factors_stddev is not a standard deviation, and lz_normal_errors inherits that

Reading lz_normal_errors as an error bar will misstate your uncertainty. factors_stddev divides the sum of squares by the largest factor length instead of the sample count, and centres on (lzf.last() − 1) / lzf.len() instead of the mean factor length. It is non-zero even for a perfectly uniform factorization: "abc" gives 0.8660254037844386 where a genuine σ would be 0. Both it and lz_normal_errors are heuristic dispersion indicators with no sampling interpretation.

paired_shuffle_complexity is always zero

Reading it gives LzShuffle::default() — max_block_size: -1, emc_value: 0.0, multi_information: 0.0, empty summands — for every input. metrics::lz76 assigns Default::default() to it unconditionally. The function that would fill it, shuffle::lz76_paired_shuffle_complexity, exists and works; nothing calls it. Call it yourself if you want the value.

Threads and the rayon pool¶

The crate uses rayon in three places, and factorize is not one of them.

Entry point	Parallelism	Shape
`lz76::factorize`, `lz76_factorization`, `lz76_factors`, `lz76_entropy_density`	none	single-threaded end to end: suffix array, LCP, LPF, factor walk
`metrics::lz76_information_distance`	nested `rayon::join`	the 4 independent factorizations `C(X)`, `C(Y)`, `C(XY)`, `C(YX)`
`metrics::lz76_extras_with`	`rayon::join`	the 2 half-sequence factorizations
`shuffle::shuffle_factorization`	`into_par_iter`	the mm block-shuffle factorizations of the EMC ladder

A single lz76_factors or lz76_entropy_density call therefore saturates exactly one core no matter how large the pool is — the throughput figures on Performance are single-core figures for that reason. EMC and NID are where the pool earns its keep.

The crate never builds its own pool; it inherits rayon's global one. Three ways to control it:

// 1. Environment, no code change:  RAYON_NUM_THREADS=2 cargo run --release

// 2. Size the global pool once, before any parallel call.
rayon::ThreadPoolBuilder::new().num_threads(4).build_global().unwrap();

// 3. Scope a pool to one call site — composes with other libraries in the process.
let pool = rayon::ThreadPoolBuilder::new().num_threads(4).build().unwrap();
let s = pool.install(|| shuffle::lz76_random_shuffle_complexity(&seq, &args));

$ cargo run --release --bin threads
default pool = 16
in 4-thread pool: emc = 2.4609375
pool threads = 4

$ RAYON_NUM_THREADS=2 cargo run --release --bin threads
default pool = 2
in 4-thread pool: emc = 2.4609375
pool threads = 4

Thread count changes timing and nothing else. Every parallel section computes independent pure functions and reduces them in a fixed order, so results are bit-identical across pool sizes — including the EMC value above, unchanged at 16, 4 and 2 threads. See Determinism.

Two conventions that will bite you¶

`complexity` counts complete components only¶

The greedy parse advances i += LPF[i] + 1, so the final boundary is always exactly n or n + 1. When it is n + 1 the last production ran past the end of the sequence — its innovation symbol is not there — and the crate does not count it. The textbook exhaustive-history count — the Kaspar–Schuster loop that antropy and NeuroKit2 implement — does count it, so it is 0 or +1 above this crate's number.

The conversion is exact for any sequence with at least two distinct symbols. Re-checked against a naive O(n³) reference implementation of the exhaustive history over a 4000-string sweep (n = 2…60, alphabets 01, 012, ACGT): of the 3955 non-constant cases, the boundary vectors matched with zero mismatches and the converted count matched the reference in all 3955. The 45 constant cases are the exception below.

c_textbook = c + [ lzf.last() > n ]

c: Lz76Result::factorization as returned by this crate
lzf.last(): the final entry of Lz76Result::lzf, always n or n + 1
n: seq.len()

let r = lz76::lz76_factors(&seq, &args);
let overshoot = (*r.lzf.last().unwrap() as usize) > seq.len();
let c_textbook = r.factorization + overshoot as u32;

Sequence	`factorization`	`lzf.last()`	`n`	textbook
`banana`	3	7	6	4
`1011010100010`	5	14	13	6
`1001111011000010`	6	16	16	6
`010101010101`	2	13	12	3

The conversion does not hold for a constant sequence

lz76_factorization and lz76_factors short-circuit when the input has fewer than two distinct symbols: they return factorization = 1, epsilon = 0.0 and a fabricated lzf = [0, 1, n] without running the parse at all. Because that vector never overshoots, the formula returns 1 — but the exhaustive history of "aaaa" is a | aaa, so the textbook count is 2. The empty sequence takes the same branch and yields lzf = [0, 1, 0], a descending vector. Guard on "fewer than two distinct bytes" before converting. Background: LZ76 factorization.

lzf.len() - 1 is not the complexity, and lzf.last() can index past the end

Slicing with the raw boundary vector reads out of bounds and panics. lzf.len() - 1 is the number of parsed factors, which exceeds factorization by one whenever the parse overshoots — the common case. Clamp every span: factor k is &seq.as_bytes()[lzf[k-1] as usize .. (lzf[k] as usize).min(n)]. Python slicing happens to clamp for you; Rust does not.

The EMC ladder is projected, not summed¶

shuffle_entropy_calculation builds one rung per block size and then projects the ladder:

Ê(l) = l · g · ( C_LZ(u^RS(l)) − C_LZ(u) ), g = log_k(N) ⁄ N

Ê_fit = non_negative_isotonic( Ê(1), …, Ê(mm) ) · summands[l−1] = Ê_fit(l) − Ê_fit(l−1) · emc_value = Ê_fit(mm)

mm: LzShuffle::max_block_size — the largest block size in the ladder
u^RS(l): the sequence block-shuffled at scale l
k: the log base: the detected alphabet size, or LzArgs::log_base
N: seq.len()

Every block size reaches the total. non_negative_isotonic is pool-adjacent-violators plus a positive-part clamp — the least-squares projection onto {0 ≤ v₁ ≤ … ≤ v_mm}, which is the shape Crutchfield & Feldman's Lemma 1 guarantees for the true finite-scale excess entropy.

The projection is the identity on a ladder that is already non-negative and non-decreasing, so in that case emc_value is just the top rung. "01" * 64 is one: N = 128, k = 2, mm = 15, C_LZ(u) = 2, and C_LZ of the scale-15 shuffle is 5, so 15 · (7/128) · (5 − 2) = 2.4609375 — exactly the emc_value printed above, bit for bit. Do not read that as a general closed form: the top rung survives unpooled here only because the rung below it is lower. When the top rungs pool, emc_value is their mean and the closed form is wrong.

Every summand is non-negative, and they sum to emc_value

summands holds the increments of the fitted ladder, so summands[l-1] >= 0.0 for every l, the running sums climb monotonically, and the total equals emc_value to floating-point rounding. A 0.0 entry means scales l−1 and l were pooled into one block by the projection — the surrogate at scale l was still computed. The mm surrogate factorizations happen regardless of get_shuffle_terms.

Up to 1.0.2 this vector held the raw first differences and its signs alternated ([+1.0390625, −1.0390625, +1.3125, −1.3125, …] for "01" * 64), because the sum telescoped: Σ_l [(H_l − H_{l−1}) − ĥ] collapses to Ê(mm) and the intermediate scales cancelled out of the total. They no longer do.

An emc_value of 0.0 means the whole ladder sat at or below zero

Zero is now a single, readable outcome: no scale showed a monotone rise, which is what structureless input looks like. It is no longer produced by resonance between the block grid and the source period — under 1.0.2, "0011" * 128 returned 0.0 and "01" * 1000 returned -4.440892098500626e-16 purely because the scale-mm shuffle happened to be the identity; they now return 2.70263671875 and 1.040835691685843. A 512-symbol pseudorandom binary string (random.Random(3), random.choice("01")) returned -0.28125 and now returns 0.205078125.

emc_value can never be negative. If you are comparing against a value from 1.0.2 or earlier, see Releases.

The derivation, the two remaining biases and the surrogate-quality caveats are on Effective measure complexity.

Where to go next¶

Generated API reference¶

Every signature, field and module, rendered from the source doc-comments and versioned per release on docs.rs.

docs.rs/lzcomplexity-core

Performance numbers¶

Wall-clock timings, scaling exponents, throughput and the EMC cost model, all measured on the core entry points documented here: Performance.

~12 MB/s on incompressible data

The Python surface¶

Five functions mapping onto the calls above, with the coercion rules for non-str inputs: Python API and Input types.

import lzcomplexity as lz

Rust vs C++¶

What the port changed, what it kept bit-identical and where the two libraries diverge: Rust vs C++.

289/289 differential sweep