Variable-Length Markov Chains for Python

vlmc fits variable-length Markov chains to discrete sequences. It provides one Python model class with three context-tree selection methods:

Method	Purpose	Main control
bct	Exact Bayesian context-tree MAP estimator; the default	beta
bic	Penalized maximum-likelihood / MDL baseline	penalty
peres_shield	Peres–Shields maximal-fluctuation estimator	sample size

The implementation is written in Rust and exposed through Python bindings.

Installation

Published wheels can be installed with:

pip install vlmc

To build this checkout, install Rust and Maturin, activate a Python environment, and run:

pip install maturin
maturin develop --release

Quick start

import vlmc

rows = [
    [0, 1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 0],
]

model = vlmc.VLMC(
    alphabet_size=2,
    max_depth=2,
    method="bct",       # default
)
model.fit(rows)

contexts = model.get_contexts()
context = model.get_suffix([1, 0, 1])

model.get_counts(context)            # observations following this context
model.get_transition_counts(context) # raw next-symbol counts
model.get_distribution(context)      # Jeffreys-smoothed probabilities
model.predict_proba([1, 0, 1])       # suffix lookup + probabilities

Symbols must be integers in 0 <= symbol < alphabet_size. Invalid symbols raise a ValueError instead of panicking.

Constructor

vlmc.VLMC(
    alphabet_size,
    max_depth=10,
    method="bct",
    beta=None,
    penalty=None,
    boundary="condition",
)

• alphabet_size must be at least two.
• max_depth is the largest candidate history length.
• method is "bct", "bic", or "peres_shield".
• beta is BCT-only and must satisfy 0.5 <= beta < 1, the range in which the algorithm identifies the exact MAP tree. When omitted it is 1 - 2 ** (-(alphabet_size - 1)), the value recommended by the BCT paper.
• penalty is BIC-only and multiplies the standard BIC penalty. It defaults to 1.
• boundary="condition" treats every row as an independent realization. For a depth D, its first D symbols form the conditioned initial history and only later symbols are fitted. Rows are never concatenated. A row of length at most D therefore contributes no fitted outcomes.

The fitted sample_size property reports the exact number of outcomes used by every node comparison. node_count and context_count report the retained model size. effective_max_depth equals max_depth for BCT/BIC and the data-dependent ln(ln(sample_size)) cap for Peres–Shields.

Selection methods

BCT (default)

BCT selects a maximum a posteriori context tree using a Dirichlet-1/2 (Jeffreys) prior for transition probabilities. It is the recommended general-purpose default.

BIC

BIC maximizes

log maximum likelihood - penalty * leaves * (alphabet_size - 1) / 2 * log(sample_size)

This is useful when a conventional penalized maximum-likelihood model is preferred.

Peres–Shields

For an extension v and suffix w, this method uses the paper's raw-count fluctuation

max_a |N(va) - N(wa) * N(v) / N(w)|

and the asymptotic threshold sample_size ** (3/4). Eligible extensions have absolute depth at most min(max_depth, floor(ln(ln(sample_size)))). Because this is an asymptotic criterion, it can be conservative for moderate samples.

Probability and context semantics

get_contexts() returns selected predictive contexts, ordered by length and then lexically. BCT and BIC return leaves of a proper context tree. Peres–Shields may also return an internal sparse fallback context together with deeper exceptional contexts, as allowed by its prediction suffix tree construction.

get_distribution(context) always returns probabilities, using Jeffreys smoothing:

P(a | context) = (N(context, a) + 1/2) /
                 (N(context) + alphabet_size / 2)

Use get_transition_counts(context) when raw next-symbol counts are required. get_counts(context) returns N(context), the number of usable outcomes following that context.

References

• Kontoyiannis et al., Bayesian Context Trees: modelling and exact inference for discrete time series.
• Csiszár and Talata, Context tree estimation for not necessarily finite memory processes, via BIC and MDL.
• Dalevi and Dubhashi, The Peres–Shields Order Estimator for Fixed and Variable Length Markov Models.